[SWEA] 1221번 - GNS 풀이 및 코드 분석 (Java)

문제 링크

1. 문제 분석

📌 문제 개요

• 외계 숫자 체계를 사용하여 정렬하는 문제
• 숫자를 "ZRO", "ONE", "TWO" 등으로 표현
• 주어진 문자열을 숫자로 변환하여 정렬한 후, 다시 문자열로 변환하여 출력해야 한다.

🎯 요구사항

1. 문자열을 숫자로 변환 후 정렬
2. 정렬된 숫자를 다시 외계 숫자로 변환하여 출력
3. 입력 형식에 맞게 출력 (#테스트케이스번호를 앞에 추가)

---

2. 해결 방법

🔹 핵심 개념

• 문자열을 숫자로 변환하여 정렬하는 문제
• HashMap을 사용하여 빠르게 숫자로 변환 가능
• Arrays.sort()로 정렬 후 다시 변환하여 출력

🔑 해결 절차

1. 문자열 → 숫자로 변환 (HashMap 활용)
   • "ZRO" → 0, "ONE" → 1 등 매핑
2. 숫자를 정렬 (Arrays.sort())
3. 정렬된 숫자 → 문자열로 변환하여 출력

---

3. 코드 구현 (Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Solution {
    static int len;
    static int[] board;

    static String[] nums = {"ZRO", "ONE", "TWO", "THR", "FOR", "FIV", "SIX", "SVN", "EGT", "NIN"};
    static Map<String, Integer> map = new HashMap<>();

    public static void main(String[] args) throws Exception {
        for (int i = 0; i < 10; i++) {
            map.put(nums[i], i);
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine().trim());

        for (int t = 1; t <= T; t++) {
            sb.append("#").append(t).append("\n");

            st = new StringTokenizer(br.readLine());
            st.nextToken(); // 테스트케이스 번호 제거
            len = Integer.parseInt(st.nextToken());

            board = new int[len];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < len; i++) {
                board[i] = map.get(st.nextToken());
            }

            Arrays.sort(board); // 숫자로 변환된 배열 정렬

            for (int i = 0; i < len; i++) {
                sb.append(nums[board[i]]).append(" ");
            }

            sb.append("\n");
        }

        System.out.println(sb);
    }
}

---

4. 코드 분석

🔹 주요 알고리즘

1. HashMap을 이용한 문자열-숫자 변환
   • "ZRO" -> 0, "ONE" -> 1, ..., "NIN" -> 9
   • O(1)로 숫자로 변환 가능
2. 배열 정렬 (Arrays.sort())
   • O(N log N)의 정렬 수행
3. 숫자를 다시 외계 숫자로 변환 후 출력
   • O(N)

---

5. 시간 복잡도 분석

• 입력 변환 (O(N))
• 정렬 (O(N log N))
• 출력 변환 (O(N))
• 총 시간 복잡도: O(N log N) → 충분히 해결 가능!

---

6. 개선할 점 및 대체 방법

✅ 개선할 점

1. 계수 정렬(Counting Sort) 사용 가능
   • 숫자의 범위가 0~9로 고정 → 계수 정렬 (O(N)) 가능!
   • count[10] 배열을 활용하여 각 숫자의 개수를 세고 출력

🔄 대체 방법 (Counting Sort 활용)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    static String[] nums = {"ZRO", "ONE", "TWO", "THR", "FOR", "FIV", "SIX", "SVN", "EGT", "NIN"};

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

        int T = Integer.parseInt(br.readLine().trim());

        for (int t = 1; t <= T; t++) {
            sb.append("#").append(t).append("\n");

            st = new StringTokenizer(br.readLine());
            st.nextToken(); // 테스트 케이스 번호 제거
            int len = Integer.parseInt(st.nextToken());

            int[] count = new int[10]; // 0~9 숫자의 개수 저장

            st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                String num = st.nextToken();
                for (int i = 0; i < 10; i++) {
                    if (num.equals(nums[i])) {
                        count[i]++;
                        break;
                    }
                }
            }

            // 결과 출력
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < count[i]; j++) {
                    sb.append(nums[i]).append(" ");
                }
            }

            sb.append("\n");
        }

        System.out.println(sb);
    }
}

✔ O(N)으로 빠르게 정렬 가능!
✔ 숫자 범위가 0~9로 한정되어 계수 정렬이 최적