1221번 - GNS

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

숫자를 의미하는 문자열이 주어지고 그걸 정렬해서 출력하는 문제다.

완전 탐색을 돌아도 되고 숫자로 변환했다가 정렬해서 출력해도 되겠지만

굳이 그렇게 하지 않아도 가장 쉽게 풀 수 있는 방법이 있다.

 

• 데이터 값의 범위가 0~9이다.

우리는 이 점을 주목해야 한다.

나는 정렬 문제가 나왔을 때 가장 먼저 보는 것이 데이터의 범위이다.

값의 범위가 적을 때 카운팅 정렬을 사용할 수 있기 때문이다.

 

• 카운팅 정렬이란?

3 4 2 2 1 1 5 1

예를 들어 위와 같은 숫자들이 주어졌다고 하자.

 

1: 3개
2: 2개
3: 1개
4: 1개
5: 1개

각 숫자들이 몇 개씩 있는지 세보자.

말 그대로 카운트하는 것이다.

 

1 1 1 2 2 3 4 5

이제 낮은 숫자부터 카운트한 개수만큼 출력하면 정렬이 끝난다.

정말 미친듯한 속도로 정렬이 끝이 난다.

 

단, 카운팅 정렬은 앞서 말했듯이 값의 범위가 적어야 한다는 단점이 있다.

만약 값의 범위가 10,000을 넘어가고 100,000을 넘어가면

사용하지 않을 공간까지 선언해야 하고 효율이 뚝뚝 떨어지게 된다.

또, 숫자 정렬만 가능하다는 단점이 있다.

 

사용할 수 있는 문제가 자주 있는 편은 아니지만

이번 GNS 같은 문제에서는 아주 유용한 알고리즘이다.

 

• 문제에선 숫자가 아닌 문자열이 주어졌는데?

HashMap 구조를 이용해서 문자열을 Key로, 숫자를 Val로 잡으면 된다.

이렇게 하면 문자열이 주어졌을 때 매번 포문을 돌며 그에 대응하는 숫자를 찾지 않아도 된다.

해쉬 구조는 O(n)의 시간 복잡도를 가지기 때문에 굉장히 효율적이다.

만약 해쉬를 사용하지 않으면 대응하는 숫자를 찾기 위해서

(주어진 문자열 개수) x 10 만큼 더 시간 낭비를 하게 된다. 

 

2. 코드

package algorithm;

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

public class Day13_1221_GNS {

	public static void main(String[] args) throws Exception {
		// IO 관련
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
        
		StringTokenizer st;
		int testCase = Integer.parseInt(br.readLine());
		
		// 각 문자열을 key로 잡고 val에 숫자를 넣어 map에 저장
		HashMap<String, Integer> map = new HashMap<>();
		String[] nums = { "ZRO", "ONE", "TWO", "THR", "FOR", "FIV", "SIX", "SVN", "EGT", "NIN" };
		for (int i = 0; i < nums.length; i++) {
			map.put(nums[i], i);
		}

		for (int tc = 1; tc <= testCase; tc++) {
			int[] counting = new int[10];
			st = new StringTokenizer(br.readLine());
			sb.append(st.nextToken()).append("\n");
			
			// 카운팅 정렬
			st = new StringTokenizer(br.readLine());
			while(st.hasMoreTokens()) {
				counting[ map.get(st.nextToken()) ]++;
			}
			
			// 출력
			for(int i=0; i<10; i++) {
				for(int j=0; j<counting[i]; j++) {
					sb.append(nums[i]).append(' ');
				}
			}
			
			sb.append("\n");
		}
        bw.write(sb.toString());
        bw.flush();
        bw.close();
	}
}

BufferedReader, BufferedWriter, StringBuilder, StringTokenizer는 실행 시간을 최대한으로 단축하기 위해 사용한 거라

사용법이 익숙하지 않다면 Scanner나 split 등을 사용해도 된다.

 

3. 실행시간

만년 2등

 

싸피 전체 순위가 544명 중에 25등 정도 되길래 기대했는데

또 2등 😭

 

 

 

 

 

---

💡 느낀 점

• 문제 카테고리가 문자열이던데 내가 야매로 푼 게 아닌가 의심이 든다.
• 숫자 범위가 한 10,000 이하면 카운팅 정렬로 접근해볼 만한 것 같다.

---