[백준 JAVA] 3986 좋은 단어

3986 좋은단어

https://www.acmicpc.net/problem/3986

평석아 이상한 거 하지 말고 자라... 수면부족이다

문제설명

stack을 사용한 데이터 삽입, 추출

전에 풀었던 괄호와 비슷한 유형의 문제이다

https://gyummodiary.tistory.com/83

접근방식

O(T x N) 선형 시간복잡도

 

각 문자열은 한 번씩 순회하며 처리된다.

각 문자열의 길이를 n이라고 할때, 내부 루프에서 문자열을 순회하며 스택 연산을 수행한다.

각 문자열에 대해 스택 연산은 O(n)시간이 걸린다.

스택 연산은 상수 시간이 걸리는데, 스택의 연산이 각 O(1) 시간 복잡도를 가지기 때문에 O(n x 1) = O(n) 시간이다.

 

문자열 개수가 T라고 했을때, 모든 입력을 한 번씩 읽어오므로 시간 복잡도는 O(T x n)이 된다.

전체 테스트 케이스의 수를 T라고 하면, 전체 코드의 시간복잡도는 O(T×n)가 된다.

따라서 이 알고리즘의 시간 복잡도는 입력으로 주어지는 문자열 총 길이에 선형으로 비례하며

각 문자열은 스택을 이용한 단일 순회로 처리된다.

문제 조건 분석 과정

 

1. 처음에 아치형이라 막막했으나, 괄호처럼 A에는 B 한쌍이 이루어져야 된다고 단순하게 생각해보자.

2. stack에 A를 넣고 다음 문자가 없을 경우 B를 삽입하고 종료하거나

3. 있을 경우 반환한다.

 

자료구조

Stack<Character>

문자형 데이터를 저장하는 스택을 생성

• push: st.push(val)를 사용하여 스택의 맨 위에 문자 val을 추가.
• pop: st.pop()을 호출하여 스택의 맨 위에 있는 값을 제거하고 반환한다.
• peek: st.peek()을 호출하여 스택의 맨 위에 있는 값을 조회한다.
• 제거하지 않고 값을 가져오며, 스택이 비어있을 경우 예외를 발생시키지 않고 null을 반환한다.
• empty: st.empty()를 사용하여 스택이 비어있는지 여부를 확인한다.
• 비어있으면 true, 아니면 false를 반환한다

틀린이유

풀이방법, 자료구조 파악을 하는데 시간이 걸렸다.

올바른 접근 방식 및 해결 방식

문제를 이해하는데 시간이 걸렸던 것 같다.

문제를 파악하기 힘들때는 성공하는 케이스의 경우의 수를 그려보자.

전체코드

import java.util.*;
import java.io.*;

public class Main3982_stack2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //개수 입력
        int T = Integer.parseInt(br.readLine());

        int result = 0;

        //입력된 문자열 개수만큼 반복
        for (int i = 0; i < T; i++) {
            Stack<Character> st = new Stack<Character>();
            //문자열 입력
            String A = br.readLine();

            for (int j = 0; j < A.length(); j++) {
                //문자열을 하나씩 쪼갬
                char val = A.charAt(j);
                //스택이 비어있으면 현재 문자열을 넣음
                if (st.empty()) {
                    st.push(val);
                } else {
                    //스택이 비어있지 않으면 스택의 맨 위와 현재 문자 비교
                    if (st.peek() == val) {
                        //맨 위 문자와 현재 문자가 같으면 스택에서 제거
                        st.pop();
                    } else {
                        //맨 위 문자와 현재 문자가 다르면 현재 문자 삽입
                        st.push(val);
                    }
                }
            }
            if (st.empty()) {
                result++;
            }
        }
        System.out.println(result);

    }
}