[JAVA] 백준 1920번: 수 찾기

 

---

문제

• N개의 정수 A[1], A[2], ... A[N]이 주어질 때, X라는 정수가 존재하는지 여부를 출력하는 문제.

 

아이디어

• 카운팅 정렬 방식을 활용하려 했지만, 입력 범위가 -2^31 ~ 2^31 이길래 그냥 해시맵을 사용하기로 했다.
• 입력되는 수 마다 해시맵에 저장하고, 맵의 getOrDefault를 활용해 찾는 값이 존재하면 1, 없으면 0을 출력하도록 한다.
• 문제에서는 명확히 밝히지 않았지만, 중복된 정수가 입력될 수도 있기에 맵에 존재 할 경우 그냥 키에 해당하는 값에 +1 해주었다.

 

풀이

import java.io.*;
import java.util.*;

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

        Map<Integer, Integer> map = new HashMap<>();

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        // 입력받은 수를 num에 저장하고,
        // num을 키값으로 가지는 요소가 있으면 +1, 없으면 맵에 추가
        for(int i=0; i<N; i++) {
            int num = Integer.parseInt(st.nextToken());
            map.put(num, map.getOrDefault(num, 0)+1);
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<M; i++) {
            int num = Integer.parseInt(st.nextToken());
            
            // num을 키값으로 가지는 요소가 있으면(0이 아니면) 1 출력
            // 없으면 그대로 0 출력
            int state = map.getOrDefault(num, 0);
            sb.append(state==0 ? 0 : 1).append('\n');
        }

        System.out.println(sb);
    }
}

 

 

채점 결과

1920번 채점 결과

기타

• 문제의 출력 부분을 꼼꼼히 읽지 않아 한 번 틀렸다... 문제를 잘 읽자.
• 이분 탐색으로도 분류되어 있던데.... 풀이가 궁금하다.

 

문제 링크

• 1920번: 수 찾기 (acmicpc.net)