[BOJ] 2776 - 암기왕 JAVA

www.acmicpc.net/problem/2776

2776번: 암기왕

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에  ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

출력

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.

예제 입력 1

1

5

4 1 5 2 3

5

1 3 7 9 5

예제 출력 1

1

1

0

0

1

 

 

 

 

 

 

풀이 1. (틀린 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        while(T-- > 0) {
            StringBuilder sb = new StringBuilder();
            Set<Integer> note1 = new HashSet<>();
            Set<Integer> note2 = new LinkedHashSet<>();

            int n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < n; i++) {
                note1.add(Integer.parseInt(st.nextToken()));
            }
            int m = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < m; i++) {
                note2.add(Integer.parseInt(st.nextToken()));
            }

            for(int num : note2) {
                if(note1.contains(num)) {
                    sb.append("1\n");
                }else {
                    sb.append("0\n");
                }
            }
            System.out.println(sb.toString());
        }
    }
}

 

Set의 특성을 제대로 생각하지 않고 풀어서 틀렸다.

 

1. Set은 중복 원소는 저장하지 않는다.

-> 그렇기 때문에 note2에 전부 저장한 후 하나씩 뽑아낼 경우 m개의 질문 중 중복되는 값이 있다면 m개 이하의 답이 출력되어버릴 수 있다.

 

2. Set은 입력 순서를 보장하지 않는다.

-> Set은 기본적으로 입력 순서를 보장하지 않고 오름차순으로 값을 저장한다. 이 때문에 값들의 저장을 일괄적으로 수행한 후 검사를 하면 출력값의 순서가 올바르지 못하게 된다.

(순서 유지를 원한다면 LinkedHashSet을 쓰면 된다.)

 

이를 해결하기 위해 그냥 m개의 수를 입력 받자마자 검사를 실시했다.

 

 

 

 

 

풀이 2. (정답 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(st.nextToken());

        while(T-- > 0) {
            Set<Integer> note = new HashSet<>();
            int n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < n; i++) {
                note.add(Integer.parseInt(st.nextToken()));
            }

            int m = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < m; i++) {
                int num = Integer.parseInt(st.nextToken());
                if(note.contains(num)) {
                    sb.append("1\n");
                }else {
                    sb.append("0\n");
                }
            }
        }
        System.out.println(sb.toString());
    }
}

 

Set을 하나만 사용하고 m개의 숫자를 입력 받자마자 검사하여 해결.