[백준] 1599번. 민식어(JAVA)

문제

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

---

풀이(11분)

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

public class Main {
    private static HashMap<Character, Integer> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        map.put('a', 1);
        map.put('b', 2);
        map.put('k', 3);
        map.put('d', 4);
        map.put('e', 5);
        map.put('g', 6);
        map.put('h', 7);
        map.put('i', 8);
        map.put('l', 9);
        map.put('m', 10);
        map.put('n', 11);
        map.put('c', 12);
        map.put('o', 13);
        map.put('p', 14);
        map.put('r', 15);
        map.put('s', 16);
        map.put('t', 17);
        map.put('u', 18);
        map.put('w', 19);
        map.put('y', 20);

        String[] arr = new String[n];

        for(int i = 0; i < n; i++){
            String input = br.readLine();
            input = input.replaceAll("ng", "c");
            arr[i] = input;
        }

        Arrays.sort(arr, ((o1, o2) -> {
            for(int i = 0; i < Math.min(o1.length(), o2.length()); i++){
                int o1Num = map.get(o1.charAt(i));
                int o2Num = map.get(o2.charAt(i));
                if(o1Num != o2Num){
                    return o1Num - o2Num;
                }
            }
            return o1.length() - o2.length();
        }));

        for(String s : arr){
            s = s.replaceAll("c", "ng");
            System.out.println(s);
        }
    }
}

---

문제 풀이 전략

 

민식이의 각 알파벳에 대한 사전순 번호를 map에 저장한다. 이때 ng -> c로 변경하여 저장해 둔다.

반복문을 돌며 배열에 입력을 저장할 때 ng -> c로 바꾸어 저장한다.

 

정렬을 할 때는 다음과 같다.

1. 알파벳을 하나씩 검사하며 사전순으로 정렬한다.

2. 길이가 짧은 문자열의 길이까지 같다면, 길이가 짧은 것을 우선한다.(사전순인 경우 abc가 abcd보다 우선이다.)

 

최종적으로 출력할 때 다시 c -> ng로 바꾸어 출력한다.