[백준(JAVA)] 1157번: 단어 공부

문제

✔ 난이도 - Bronze 1

설명

입력받은걸 toCharArray로 문자형배열로 저장하고 순회하면서 HashMap에 저장함.
이 때 getOrDefault를 사용하여 이미 존재하면 해당 key의 value값을 가져오고, 아니라면 디폴트값을 0으로 설정함.
그 후 정렬하고, 만약 갯수가 1개 이상이고 최상위와 두번째 상위의 value 값이 같다면 ?를 출력, 그 외의 모든 경우(항목이 1개이거나, 1등의 빈도수가 2등보다 클 때)는 최상위의 value값을 출력한다.

풀이

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();

        char[] arr = br.readLine().toLowerCase().toCharArray();
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : arr) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort((a, b) -> Integer.compare(b.getValue(), a.getValue()));

        if (list.size() > 1 && list.get(0).getValue().equals(list.get(1).getValue())) {
            System.out.println("?");
        } else {
            System.out.println(Character.toUpperCase(list.get(0).getKey()));
        }

        System.out.println(sb);
    }
}

처음엔 아래와 같이 조건을 판별했었다

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

결과적으로는 동일한 결과를 내지만, 가독성 측면과 구조적으로 안정된 코드는 아래의 코드이다.

        if (list.size() > 1 && list.get(0).getValue().equals(list.get(1).getValue())) {
            System.out.println("?");
        } else {
            System.out.println(Character.toUpperCase(list.get(0).getKey()));
        }

원래 코드는 로직이 분리되어 복잡했고, 수정된 코드는 하나의 통합된 원칙으로 모든 경우를 처리한다.
수정된 코드는 문제를 더 근본적으로 바라보고있다.

정답이 '?'가 되는 유일한 조건은 무엇인가?
-> 리스트에 항목이 2개 이상 있고, 1등과 2등의 빈도수가 같을 때
-> 그 외는 전부 다 처음 값을 출력

⏰ 시간복잡도

O(N)

1. 입력 및 전처리 (O(N))
   br.readLine().toLowerCase().toCharArray(): 길이 N인 문자열을 읽고, 소문자로 바꾸고, 문자 배열로 만드는 과정은 모두 문자열 길이에 정비례 -> O(N)

2. 알파벳 빈도수 계산 (O(N))
   for (char c : arr): arr의 모든 요소를 한 번씩 순회하므로 정확히 N번 실행됨
   map.put()과 map.getOrDefault()는 해시맵 연산으로, 평균적으로 O(1) 의 시간이 걸림
   따라서 이 반복문 전체는 N * O(1) = O(N)

3. 리스트 변환 및 정렬 (O(1))
   List<Map.Entry<...>> list = new ArrayList<>(map.entrySet()); : map에는 알파벳만 들어가므로 최대 26개의 항목만 존재 -> O(1)
   list.sort(...): 리스트를 정렬하는 것은 보통 O(K log K)의 시간 (K는 리스트의 크기)
   K는 알파벳 개수인 26개를 절대 넘을 수 없는 상수 -> O(26 * log 26) ->상수 시간 -> O(1)

4. 결과 확인 및 출력 (O(1))
   리스트의 첫 번째, 두 번째 요소에 접근하는 것은 O(1)

각 단계의 시간 복잡도를 종합하면 O(N) + O(N) + O(1) + O(1) -> O(N)

TIL💡

📌 == vs .equals() -> Integer는 정수니까 ==로 비교해도 되지 않나?

int는 기본형(Primitive type) 변수이고, HashMap에 들어간 Integer는 객체(Object, Reference type) 이다.

• int a = 100; -> a라는 변수 공간 안에 숫자 100이 직접 들어있음
• Integer b = 100; -> b라는 변수 공간 안에는 숫자 100이 들어있는 객체의 메모리 주소(참조값) 가 들어있음.

---

• == -> 두 변수가 같은 메모리 주소를 가리키고 있는지, 즉 완전히 동일한 객체인지를 비교
• .equals() -> 두 객체의 내용(값)이 같은지를 비교

String 객체를 비교할 때 .equals()를 쓰는 이유도 ==는 같은 문자열이라도 다른 객체일 수 있기 때문인데, Integer도 똑같은 원리가 적용된다.

정리하자면
String, Integer 등 모든 객체(Object) 의 내용(값) 을 비교하고 싶을 땐 항상 .equals()를 사용하자.

==는 int, double, char 같은 기본형(Primitive type) 을 비교하거나, 두 변수가 완전히 동일한 객체를 참조하는지 확인할 때만 사용해야 한다.

📌 String과 Character의 .toLowerCase()

String.toLowerCase()는 문자열 전체에, Character.toLowerCase()는 문자 하나에 적용된다.

String.toLowerCase()

문자열에 포함된 모든 대문자를 소문자로 바꾼다.

String greeting = "Hello WORLD";
String lowerGreeting = greeting.toLowerCase(); // "hello world"

Character.toLowerCase(char c)

단 하나의 문자만 받아서 소문자로 바꾼다.

char alphabet = 'A';
char lowerAlphabet = Character.toLowerCase(alphabet); // 'a'