[Hashset][Java][BOJ] #2776. 암기왕

#Hashset #Silver4

🌷 문제 설명

✏️ 백준 연습문제: #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을 출력한다.

입출력 예

Input	Result
1 5 4 1 5 2 3 5 1 3 7 9 5	1 1 0 0 1

 

🌷 내 코드

1.  이중포문

나는 프린트를 찍지 않으면 문제를 풀지 못하는 멍청이기 때문에 VS 코드에서 하나하나 실행해가면서 입력값 받는 삽질을 아주 오래했다. 안그래도 입력을 어떻게 받는지 잘 모르는데 자바는 파이썬이나 자스보다 훨씬 방법도 많고 헷갈리는거 같다. 블로그 검색해봐도 뭔가 정형화된 입력받는 포맷이 없었다. 지피티 너가 아니었다면 해내지 못했을거야. 너무 헷갈려서 파이썬으로 먼저 풀고 자바로 변경하는 작업을 함.. 이게 뭐하는거지..?

알고 바보, 아니 그냥 바보인 나는 이중 포문도 사실 말처럼 그리 빨리 풀지는 못했는데, flag변수 설정해서 확인하는걸 생각해 내는데 오래 걸렸다.

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

public class BOJ_2776 {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("example.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 생성
        StringBuilder sb = new StringBuilder(); // 출력할 결과 저장
        int t = Integer.parseInt(br.readLine()); // test case 수


        for (int i=0; i<t; i++) { 
            int n = Integer.parseInt(br.readLine()); // 노트 1에 수가 몇개 있는지
            int[] note1 = new int[n]; // 노트 1에 있는 수 
            StringTokenizer st = new StringTokenizer(br.readLine()); // StringTokenizer는 문자열을 공백을 기준으로 토큰으로 나누는 역할
            
            for (int j=0; j<n; j++) {
                note1[j] = Integer.parseInt(st.nextToken()); // 노트 1에 있는 수를 배열에 넣기
            }

            int m = Integer.parseInt(br.readLine()); // 노트 2에 수가 몇개 있는지
            int[] note2 = new int[m]; // 노트 2에 있는 수

            st = new StringTokenizer(br.readLine()); // StringTokenizer는 문자열을 공백을 기준으로 토큰으로 나누는 역할
            for (int j=0; j<m; j++) { // 노트 2에 있는 수를 배열에 넣기
                note2[j] = Integer.parseInt(st.nextToken()); // nextToken()은 토큰을 반환
            }

            for (int j=0; j<m; j++) { // 노트 2에 있는 수가 노트 1에 있는지 확인
                boolean found = false;
                for (int k=0; k<n; k++) {
                    if (note1[k] == note2[j]) { // 있으면 1 출력
                        sb.append(1).append("\n");
                        found = true;
                        break;
                    } 
                }
                if (!found) { // 없으면 0 출력
                    sb.append(0).append("\n");
                }
            }


        System.out.println(sb);

    }
    }}

 

 

2.  해쉬셋

이중 포문을 돌리면서 알고는 있었다 이게 시간 초과가 날 것이라는 것을. 그래서 문제에 보면 이진탐색 되어있길래 그거 해보려고 했는데 진짜 자바 너 ㅇㅣ색기.... 내가 어레이랑 어레이리스트랑 리스트 차이점 알아오게되면 그때 할게.. 아직 더 친해져야한다.

기염둥이의 TIL을 보고 해쉬셋을 이용해야 한다는걸 알았다. 물론 나는 해쉬셋 선언하는 법을 모른다. 근데 해쉬셋의 h 쓰자마자 코파일럿이 선언을 해 주었다ㅋㅋㅋ 이제 코딩도 다 템빨이야

 

🤖 해쉬셋과 해쉬맵은 둘 다 해시 기반 자료구조긴 하지만, 아래와 같은 차이점을 가진다.

특징	HashMap	HashSet
저장 방식	key-value쌍 저장	value만 저장
메서드	put(key, value) get(key)	add(value) contains(value)

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 생성
        StringBuilder sb = new StringBuilder(); // 출력할 결과 저장
        int t = Integer.parseInt(br.readLine()); // test case 수


        for (int i=0; i<t; i++) { 
            int n = Integer.parseInt(br.readLine()); // 노트 1에 수가 몇개 있는지
            int[] note1 = new int[n]; // 노트 1에 있는 수 
            StringTokenizer st = new StringTokenizer(br.readLine()); // StringTokenizer는 문자열을 공백을 기준으로 토큰으로 나누는 역할
            
            for (int j=0; j<n; j++) {
                note1[j] = Integer.parseInt(st.nextToken()); // 노트 1에 있는 수를 배열에 넣기
            }

            int m = Integer.parseInt(br.readLine()); // 노트 2에 수가 몇개 있는지
            int[] note2 = new int[m]; // 노트 2에 있는 수
            st = new StringTokenizer(br.readLine()); 

            HashSet<Integer> set = new HashSet<>(); // 해쉬셋 선언

            for (int j=0; j<n; j++) {
                set.add(note1[j]);
            }

            for (int j=0; j<m; j++) { // 노트 2에 있는 수를 배열에 넣기
                note2[j] = Integer.parseInt(st.nextToken()); // nextToken()은 토큰을 반환
            }

            for (int j=0; j<m; j++) { // 노트 2에 있는 수가 노트 1에 있는지 확인
                if (set.contains(note2[j])) { // set.contains()
                    sb.append(1).append("\n");
                } else {
                    sb.append(0).append("\n");
                }
            }
        

    }
            // 마지막 줄바꿈 제거
        if (sb.length() > 0) {
            sb.setLength(sb.length() - 1);
        }

        System.out.println(sb);
    }}

 

🌷 코멘트

와 자바 무슨일인데.. 왜 코테를 자바로 보는 사람들이 있는거지???
인풋 받는데만 거의 한시간 걸렸다 미쳔나봐 그냥 파이썬 할까.. 쉽지 않다 진짜...

컴파일에러 환장~

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!

~대가리 꽃밭인 디지털 노마드가 꿈이예요~

🧚‍♀️ Gyumin Lee

📧 gyumin.q.lee@gmail.com

qminlee723 - Overview