[자바] 백준 8975 - PJESMA (java)

 문제 : boj8975

---

 

필요 알고리즘 개념

• 해시를 사용한 집합과 맵
  
  • 해시를 통해 어떠한 문자열이 존재하는지 빠르게 확인이 가능해야 한다.

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

 

---

 

풀이

  해시에 대해 알고 있다면 문제 파악만 잘 됬다면 어렵지 않게 풀 수 있다.

N개의 문자열에 대해, M개의 문자열을 하나씩 입력받다가 N개에서 존재했던 문자열 중 ⌈N/2⌉개가 나온 경우 몇번째인지 출력해주면 된다.

 

  예를들어 예제 입력 1을 보자.

3
sedam
gladnih
patuljaka
7
sedam
dana
sedam
noci
sedam
gladnih
godina

  N개의 문자열에 대해, ⌈N/2⌉은 2 이므로 2개 이상의 문자가 나온게 몇번째인지 출력해주면 된다.

1 : sedam 존재한다. 현재 1개이다.

2. dana는 N개의 문자에 포함되지 않는다.

3. sedam은 존재하지만, 이미 첫번째에서 나왔으므로 무시한다.

4. noci는 존재하지 않는다.

5. sedam은 마찬가지로 무시한다.

6. gladnih는 존재하고 이전에 안나왔다. 2개가 나왔으므로 '6'이 답이 된다.

 

 

  그렇다면 N개의 문자열을 HashSet에 등록해둘 경우 M개의 문자열을 입력받으면서 바로바로 존재하는지 확인이 가능할 것이다. 중복으로 체크되는 경우는 해당 문자가 존재할 경우 HashSet에서 제거해줌으로써 간단하게 중복 예외처리를 해줄 수 있다. 로직은 다음과 같다.

 

A. N개의 문자열을 HashSet에 넣는다.

B. ⌈N/2⌉ 을 계산해서 변수에 넣어둔다. 이걸 factor라고 하겠다.

C. 이하 M개의 문자열을 순서대로 입력받으면서, 해시셋에서 존재한다면 해시셋에서 해당 문자를 제거해주고 factor를 1 감소시킨다.

D. 'C'를 factor가 0이 될때까지 해주면 된다. 0이 되었다면 몇번째인지 출력해준다.

 

  이 때 factor가 0이 되지 않는 경우는 문제의 'Note: the test data will be such that Mirko will always guess the song title from the lyrics.' 부분에 따라 신경쓰지 않아도 된다.

 

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        HashSet<String> hs = new HashSet<>();
        for (int i = 0; i < n; i++) {
            hs.add(br.readLine());
        }

        int k = Integer.parseInt(br.readLine());
        int cnt = 0;
        int factor = n/2+(n%2==1?1:0);
        while (factor>0) {
            cnt++;
            String cur = br.readLine();
            if (hs.contains(cur)) {
                factor--;
                hs.remove(cur);
            }
        }
        System.out.println(cnt);
    }

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