[백준(JAVA)] 17413번: 단어 뒤집기 2

문제

✔ 난이도 - Silver 3

설명

[JAVA] 덱(Deque) 정리
태그 내부인지 아닌지를 판별하는 변수 tag
태그 내부로 들어가면 덱에 addLast로 하고 pop을 하여 순차대로 꺼낼 수 있게 한다.
태그 외부 즉, 단어이면 덱에 addFirst로 하고 pop을 하여 거꾸로 꺼내도록 한다.

<, >, 공백, tag 별 조건을 세세하게 잘 생각해서 넣어줘야 한다.

그리고 마지막이 단어로 끝나면 덱에 있는 단어를 꺼내 줄 if문을 타지 못하니까 for문 바깥에서 마지막에 한 번 더 덱에 값이 있는지 확인하고 꺼낸다.

단어 각각은 StringBuilder sb에 담고, sb2를 또 따로 만들어 최종 답변을 담도록 했다.

풀이

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringBuilder answer = new StringBuilder();

        String input = br.readLine();
        char[] list = input.toCharArray();
        Deque<Character> queue = new ArrayDeque<>();

        int tag = 0;
        for (int i = 0; i < list.length; i++) {
            Character c = list[i];

            if (c == '<' && tag == 0) {
                while (!queue.isEmpty()) {
                    sb.append(queue.pop());
                }
                answer.append(sb.toString());
                sb.setLength(0);

                queue.addLast(c);
                tag = 1;
                continue;
            }

            if (tag == 1 && c == '>') {
                queue.addLast(c);
                while (!queue.isEmpty()) {
                    sb.append(queue.pop());
                }
                tag = 0;
                answer.append(sb.toString());
                sb.setLength(0);
                continue;
            }

            if (tag == 1) {
                queue.addLast(c);
                continue;
            }

            if (tag == 0 && c == ' ') {
                while (!queue.isEmpty()) {
                    sb.append(queue.pop());
                }
                answer.append(sb.toString()).append(' ');
                sb.setLength(0);
                continue;
            }

            queue.addFirst(c);
        }

        while (!queue.isEmpty()) {
            sb.append(queue.pop());
        }
        answer.append(sb.toString());

        System.out.println(answer);
    }
}

⏰ 시간복잡도

O(N)

겉보기에는 for문 안에 while문이 있어서 $O(N^2)$처럼 보일 수 있지만, 이 코드의 동작 방식을 자세히 보면 $O(N)$이 맞습니다.

이런 방식을 분할 상환 분석(Amortized Analysis)이라고 부릅니다.

1. 메인 for문: for (int i = 0; i < list.length; i++)
   • 이 루프는 문자열의 길이 N 만큼, 정확히 N번 실행됩니다.
2. Deque 연산 (addFirst, addLast, pop)
   • ArrayDeque의 모든 add 및 pop 연산은 O(1)(상수 시간)입니다.
3. while 루프의 정체
   • while (!queue.isEmpty()) 루프는 특정 문자를 만났을 때(예: < 또는 ) 그동안 queue에 쌓아두었던 문자들을 한꺼번에 처리합니다.
   • 핵심: list에 있는 모든 문자는 queue에 단 한 번만 들어갔다가(addFirst 또는 addLast), 단 한 번만 나옵니다(pop).
   • N개의 문자가 각각 1번 들어가고 1번 나오므로, 모든 while 루프에서 pop이 호출되는 총 횟수를 다 합쳐도 N번을 넘지 않습니다.

결론적으로, 이 프로그램은 N개의 문자를 N번의 루프 동안 각각 상수 시간(O(1))의 연산(push, pop, append) 몇 번으로 처리하는 것과 같습니다. 따라서 총 시간 복잡도는 $O(N)$입니다.