🧑🏻‍💻 문제

---

💡문제 분석 요약

입력 받은 문장을 단어마다 잘라서 단어를 뒤집어 출력한다. 그냥 반복문만 사용해서 할 수 있겠지만 스택을 사용하면 시간제한에 걸릴 거 같다.

💡알고리즘 설계

1. 문장을 입력 받고, 스택을 초기화 한다. (여기서 스택을 생성한게 중요하다. 시간복잡도 해결을 위해)
2. 단어의 개수만큼 반복을 한다.
   2-1. 반복을 하며 각 단어마다 스택에 저장한다.
   2-2. 저장하는 중에 공백을 만나면 다시 스택을 출력한다.

💡코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            String sentence = br.readLine();
            Stack<Character> stack = new Stack<>();
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i <sentence.length() ; i++) {
                if (sentence.charAt(i) == ' ') {
                    while (!stack.isEmpty()) {
                        sb.append(stack.pop());
                    }
                    sb.append(" ");
                } else {
                    stack.add(sentence.charAt(i));
                }
            }
            while (!stack.isEmpty()) { // 마지막 단어는 뒤에 공백이 없으므로
                sb.append(stack.pop());
            }
            System.out.println(sb);
        }
    }
}

---

💡시간복잡도

입력받은 문자열의 길이 N에 대해 O(N)이다.

💡 틀린 이유

처음에 이중 for 문으로 시간 복잡도가 N^2 이 되어 틀렸다.

💡 틀린 부분 수정 or 다른 풀이

• 이중 for문으로 시간 복잡도 N^2 으로 틀린 코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine()); // 문장
            int N = st.countTokens();

            for (int i = 0; i < N; i++) {
                String str = st.nextToken(); // 단어
                Stack<Character> stack = new Stack<>();

                for (int j = 0; j < str.length(); j++) {
                    stack.add(str.charAt(j)); // 알파벳
                }

                while (!stack.isEmpty()) {
                    char c = stack.pop();
                    System.out.print(c);
                }
                System.out.print(" ");
            }
            System.out.println();
        }
    }
}

---

💡 느낀점 or 기억할정보

시간 제한 안에 완료되기 위해서 이중 반복문을 사용하지 않아야 했으며, StringBuilder 를 활용하여 출력했다. 출력하고 저장해야 하는 문자열이 많아질수록 System.out.println보다 StringBuilder의 시간복잡도가 더 작다는 것을 알게 되었다.