[자바] 백준 5263 - samba (java)

 문제 : boj5263

---

 

필요 알고리즘 개념

• 해시를 사용한 집합과 맵
  
  • 해시를 사용하지 않고 이 문제를 풀려면 값 압축이 필요하다. 그게 더 귀찮기도 하고, 시간복잡도적으로 비효율적이므로 해시를 사용하자.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  입력된 숫자를 '숫자 - 입력된 횟수' 형태로 나눌 수 있어야 이 문제를 풀 수 있다.

예를들어 예제 입력 1의 경우 다음과 같이 나타낼 수 있다.

123 - 6번

1678 - 2번

43 - 3번

 

  위와 같이 나타낼수만 있다면, 각 횟수를 k로 나누어서 나누어 떨어지지 않는 하나의 값이 답이 된다. 123은 6번이므로 2로 나누어떨어진다. 1678도 마찬가지다. 43은 3번으로 k로 나누어 떨어지지 않으므로 43이 답이된다.

여러개가 k로 나누어 떨어지지 않는 경우는 지문의 'Knowing that only one samba school couldn’t organize'에 따라 신경쓰지 않아도 된다.

 

  그런데, 입력값이 최대 100만개이므로, 만약 하나하나 비교하면서 동일한 수를 찾는다면 O(100만^2)이 되므로 통과할 수 없다. 그렇다고 배열에 해당 숫자가 몇 번 나왔는지 파악하려고 보니 Ci는 최대 10억이므로 10억개짜리 배열이 필요하므로 메모리 초과가 될 것이다(값 압축을 해주면 가능하긴한데, 애초에 값 압축에 HashMap이 필요하므로 이하 풀이보다 더 상위 개념이다.).

 

  따라서 HashMap이 필요하다. 입력으로 들어온 숫자를 key로 하고, 등장 횟수를 value로 하는 HashMap을 만들면 된다. 이 때 내 경우엔 String 자체로 key로 썼는데, Integer로 바꿔서 해도 상관없다.

HashMap<String, Integer> hm = new HashMap<>();
while (n-->0) {
    String cur = br.readLine();
    hm.put(cur, hm.getOrDefault(cur, 0)+1);
}

 

  이후 keySet을 얻어 모든 value를 하나씩 보면서 k로 나누어 떨어지지 않을 경우 그 key를 출력해주면 된다.

for (String key : hm.keySet()) {
    if (hm.get(key)%k!=0) {
        System.out.println(key);
        return;
    }
}

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        HashMap<String, Integer> hm = new HashMap<>();
        while (n-->0) {
            String cur = br.readLine();
            hm.put(cur, hm.getOrDefault(cur, 0)+1);
        }
        for (String key : hm.keySet()) {
            if (hm.get(key)%k!=0) {
                System.out.println(key);
                return;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}