[ 백준 - 29701 ] 모스 부호

모스 부호 문제입니다.

매우 간단한 문제이며, 우선 시간제한과 메모리 제한을 확인해 보겠습니다.

 

입력 예제를 보면  N은 최대 100 이하의 개수가 주어진다 합니다.

그럼 이 문제를 접할 때 최악의 경우 모스부호 100개를 문자열로 변환해야 하는 문제라고 볼 수 있습니다.

 

예제로 준 모스 부호표를 보면 41개를 명시한 표를 통해 답을 만들 수 있습니다.

최악의 경우 100개의 모스 부호를 41개 중 찾기 위해 반복문을 돌린다 하면 4100번 돌려 해결을 할 수 있습니다.

 

다만, 4100번 돌려 답을 찾는 것은 O(n)의 복잡도를 가지게 되지만 41이란 상수는 빅오표기법상 표기를 안 하니 딱히 효율적인 알고리즘은 아니라 생각합니다.

거기서 우리는 Map이라는 자료구조를 활용하여 O(1) 시간복잡도로 모스 부호를 검색할 수 있는 방법을 떠올릴 수 있습니다.

public class Problem29701 {

    public static Map<String, String> initMorseCodeMap() {
        Map<String, String> morseCodeMap = new HashMap<>();
        morseCodeMap.put(".-", "A");
        morseCodeMap.put("-...", "B");
        morseCodeMap.put("-.-.", "C");
        morseCodeMap.put("-..", "D");
        morseCodeMap.put(".", "E");
        morseCodeMap.put("..-.", "F");
        morseCodeMap.put("--.", "G");
        morseCodeMap.put("....", "H");
        morseCodeMap.put("..", "I");
        morseCodeMap.put(".---", "J");
        morseCodeMap.put("-.-", "K");
        morseCodeMap.put(".-..", "L");
        morseCodeMap.put("--", "M");
        morseCodeMap.put("-.", "N");
        morseCodeMap.put("---", "O");
        morseCodeMap.put(".--.", "P");
        morseCodeMap.put("--.-", "Q");
        morseCodeMap.put(".-.", "R");
        morseCodeMap.put("...", "S");
        morseCodeMap.put("-", "T");
        morseCodeMap.put("..-", "U");
        morseCodeMap.put("...-", "V");
        morseCodeMap.put(".--", "W");
        morseCodeMap.put("-..-", "X");
        morseCodeMap.put("-.--", "Y");
        morseCodeMap.put("--..", "Z");
        morseCodeMap.put(".----", "1");
        morseCodeMap.put("..---", "2");
        morseCodeMap.put("...--", "3");
        morseCodeMap.put("....-", "4");
        morseCodeMap.put(".....", "5");
        morseCodeMap.put("-....", "6");
        morseCodeMap.put("--...", "7");
        morseCodeMap.put("---..", "8");
        morseCodeMap.put("----.", "9");
        morseCodeMap.put("-----", "0");
        morseCodeMap.put("--..--", ",");
        morseCodeMap.put(".-.-.-", ".");
        morseCodeMap.put("..--..", "?");
        morseCodeMap.put("---...", ":");
        morseCodeMap.put("-....-", "-");
        morseCodeMap.put(".--.-.", "@");
        return morseCodeMap;
    }

    public static void main(String[] args) throws IOException {
        Map<String, String> morseCodeMap = initMorseCodeMap();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();
        while(N-- > 0) {
            String morseCode = st.nextToken();
            sb.append(morseCodeMap.get(morseCode));
        }
        System.out.println(sb);
    }
}

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)