[백준/Java] 1920 : 수 찾기 문제

알고리즘을 풀 때에 set과 list의 선택은 중요하다.
당연히 어떤 key를 가지고 사용하는 문제이거나, 값을 빨리 찾기 위한 의도를 가지고 있다면 set을 사용하는게 맞지만, 그 중간점에 있는 애매한 문제들도 여러 개 있다. 사실 사이즈가 정해져있으면 배열을 사용하는게 맞다고 생각하지만, 제한된 시간안에 풀어야 하는 문제라면 컬렉션을 사용해서 풀 문제들도 있을 것이다.

수 찾기에서는 set을 사용했다. 값을 일차적으로 넣은 상태에서 이후에 나오는 수가 초기에 세팅한 값인지 알기 위해서는 그 해당 값을 찾아야 한다. 즉, 추가와 삭제에 대한 문제가 아닌, 검색에서 성능차이가 발생하는 문제라는 것이다. 수 찾기 문제에서는 명확한 알고리즘을 생각해내지 못해 틀린 사람에 대한 비율보다, 효율성테스트에서 떨어진 사람이 많을 것이라고 생각한다. 

배열로 풀면 바로 되느냐? 그건 또 아니다. 순차적으로 검색했을 때 효율성테스트에서 떨어지고 만다. 즉, 배열을 정렬한 후에 길이에서 중간을 탐색하고 위, 아래인지 파악한 후 다시 중간을 탐색하는 기법 등 어떠한 방식을 사용해야만 한다. 이 탐색기법을 사용하지 않고 바로 풀기위해서는 set을 사용하는게 현명하다고 생각했다.

 

수 찾기 성공

시간제한	메모리제한	제출	정답	맞힌사람	정답비율
1 초	128 MB	114685	33988	22474	30.111%

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
1
0
0
1

문제 해답

import java.util.Set;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
    	
        /* 값을 입력받기 위한 사전 작업 */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        /* nList를 Set으로 만든 이유는 값이 중복되지 않다는 것을 알았으며
        * Hash라는 기능이 값 찾기에 상당히 유용한 기능을 가지고 있기 때문이다. */
        Set<Integer> nList = new HashSet<Integer>();
        List<Integer> mList = new ArrayList<Integer>();
        int n, m;
        n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
        	nList.add(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
        	mList.add(Integer.parseInt(st.nextToken()));
        }
        /* 값 입력 여기까지 */
        
        /* 알고리즘 시작 */
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; i++) {
        	/* nList안에 mList의 i번째 값이 존재한다면 1을 StringBuilder에 저장하고
            * 아닐경우 0을 저장한다. 여기서 mList는 값을 찾기 위한 것이 아닌 해당 index에
            * 저장되어 있는 값을 출력해내는 것이므로 Set으로 만들 필요가 없다. */
        	if(nList.contains(mList.get(i))) {
        		sb.append(1 + "\n");
        	} else {
        		sb.append(0 + "\n");
        	}
        }
        System.out.println(sb);
    }
}