[백준(JAVA)] 9046번: 복호화

세하·2025년 10월 14일

Java 백준

[백준] 문제풀이

목록 보기

63/94

문제

✔ 난이도 - Bronze 2

설명

HashMap을 사용하여 알파벳에 따른 빈도수를 key-value 쌍으로 관리함
그 후 정렬하고 상위 2개를 비교하여(2개 이상일 시) 같으면 ?를, 다르다면 최상단의 key 값을 출력함
공백일때 예외처리도 신경써주기

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            String input = br.readLine();

            HashMap<Character, Integer> hm = new HashMap<>();

            for (char word : input.toCharArray()){
                if (word == ' ') continue;
                hm.put(word, hm.getOrDefault(word, 0) + 1);
            }

            List<Map.Entry<Character, Integer>> list = new ArrayList<>(hm.entrySet());
            list.sort((a, b) -> Integer.compare(b.getValue(), a.getValue()));
            // System.out.println(list.toString());

            Map.Entry<Character, Integer> first = list.get(0);

            if (list.size() == 1) {
                sb.append(first.getKey());
            } else {
                Map.Entry<Character, Integer> second = list.get(1);

                if (first.getValue() == second.getValue()) {
                    sb.append('?');
                } else {
                    sb.append(first.getKey());
                }
            }

            sb.append('\n');

        }

        System.out.println(sb);
    }
}

⏰ 시간복잡도

O(T * N)

T: 테스트 케이스의 수 (1 ≤ T ≤ 20)
N: 각 테스트 케이스에 입력되는 문자열의 최대 길이 (1 ≤ N ≤ 255)

br.readLine(): 길이 N의 문자열을 읽는 데 O(N)
for (char word : input.toCharArray()): 문자열의 각 문자를 한 번씩 순회하므로 O(N)
hm.put() 및 hm.getOrDefault(): 해시맵의 삽입 및 조회 연산은 평균적으로 O(1)
따라서 이 부분의 전체 시간 복잡도는 O(N) + O(N) * O(1) = O(N) -> 상수 시간

해시맵에 저장된 고유 문자의 개수를 C라고 할 때, 영어 소문자는 26개이므로 C의 최댓값은 26임.
new ArrayList<>(hm.entrySet()): 해시맵의 모든 항목을 리스트로 옮기는 데 걸리는 시간은 O(C) -> 상수
list.sort(): 리스트를 정렬하는 데는 O(C log C) -> 상수
C는 알파벳 개수(최대 26)로 고정된 상수이므로, 이 단계의 시간 복잡도는 O(1) -> 상수 시간