자료 구조에 대해

백준 문제 - 암기왕

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

---

1. 테스트케이스 개수 T입력
2. 정수 갯수 입력(수첩1)
3. 정수들 띄어쓰기로 입력
4. 정수 갯수 입력(수첩2)
5. 정수들 띄어쓰기로 입력(수첩1의 값과 비교)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
		// 1번 테스트케이스를 입력
        int testCase = Integer.parseInt(br.readLine());
        int num = 0;

		
        for(int i=0; i<testCase; i++){
        	// 2번 N개의 정수 갯수 입력(수첩1)
            int N = Integer.parseInt(br.readLine());
            // 3번 정수를 띄어쓰기로 입력
            st = new StringTokenizer(br.readLine());
            List<Integer> list = new ArrayList<>();
            for(int j=0; j<N; j++){
            	// 정수를 띄어쓰기로 잘라 읽어서 리스트에 담아준다.
                list.add(Integer.parseInt(st.nextToken()));
            }
			
            // 4번 M개의 정수 갯수 입력(수첩2)
            int M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
            	// 정수를 인덱스 0~M까지 띄어쓰기로 자른다
                num = Integer.parseInt(st.nextToken());
                // 리스트(수첩1)에 자른 정수가 포함되어 있다면
                if(list.contains(num)){
                	// 1 출력
                    sb.append(1).append("\n");
                }else{
                
                	// 2출력
                    sb.append(0).append("\n");
                }
            }
        }
        System.out.println(sb.toString());
    }
}

이렇게 푸니 시간초과가 났다. ArrayList로 해서 앞에서 부터 차례로 전부 비교해서 시간이 오래걸리는 거 같다. 그래서 검색해보니 Set은 순서에 상관없이 저장되므로 그 값을 그냥 뽑아서 쓰기 때문에 비교적 시간이 빠르다고 했다. 그래서 Set으로 해봤다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        int testCase = Integer.parseInt(br.readLine());
        Set<Integer> note1 = new HashSet<>();
        Set<Integer> note2 = new HashSet<>();
        for(int i=0; i<testCase; i++){
            // 수첩 1
            int N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());

            for(int j=0; j<N; j++){
                note1.add(Integer.parseInt(st.nextToken()));
            }

            // 수첩 2
            int M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());

            for(int j=0; j<M; j++){
                note2.add(Integer.parseInt(st.nextToken()));
            }
            for(Integer num : note2){
                if(note1.contains(num)) sb.append(1+"\n");
                else sb.append(0+"\n");
            }
            note1.clear();
            note2.clear();
        }
        System.out.println(sb.toString());
    }
}

Set을 2개 써서 비교하면서 하려고 했는데 결과가 00011이 되어야되는게 11000으로 출력된다. 뭔가 상향된 for문에서 값을 오름차순해주는 거 같다. 그래서 여러번 다르게 돌려보니 오름차순을 해주는 것은 아니었고 자기 맘대로 뽑히는 거 같았다. 그래서 Set을 1개를 써서 수첩1의 내용을 담고 수첩2는 그냥 값을 적어서 하나씩 비교해 있다면 1을 출력하고 아니면 0을 출력하도록 해봐야겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        int testCase = Integer.parseInt(br.readLine());
        int num = 0;
        Set<Integer> set = new HashSet<>();
        for(int i=0; i<testCase; i++){
            // 수첩 1
            int N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());

            for(int j=0; j<N; j++){
                set.add(Integer.parseInt(st.nextToken()));
            }

            // 수첩 2
            int M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                num = Integer.parseInt(st.nextToken());
                if(set.contains(num)){
                    sb.append(1).append("\n");
                }else{
                    sb.append(0).append("\n");
                }
            }
            set.clear();
        }
        System.out.println(sb.toString());
    }
}

수첩1에 Set형으로 넣어 수첩2의 내용은 하나씩 수첩1의 내용과 비교해서 뽑아주니 잘되었다. 그리고 마지막엔 clear(); 를 안해주게 되면 Set에 값들이 계속 쌓이게 되어 나중엔 전부 포함되어 있을 수 있기 때문에 꼭 청소를 해줘야한다. 자료구조는 어떨 때 어떤 걸 사용해야될 지 아직 제대로 감이 오지않았다. 오늘은 Set에 대해 조금 알 수 있는 시간이었다. 비교를 할 땐 자료구조를 2개를 만들어서 할 필요가 없다는 걸 깨달았다. 아직은 자료구조에 대해 이해도가 부족하다고 느낄 수 있었다. 문제들을 더 접하면서 공부해야겠다.

백준 2776번