[백준] no1920: 수 찾기

문제

백준 no1920 : https://www.acmicpc.net/problem/1920

I : N개의 수로 이루어진 수열A를 입력받고, M개의 수로 이루어진 수열B를 입력받음

O : 수열 B에 포함된 수가 수열 A에 있는지 확인. 존재하면 1 없으면 0을 순차적으로 출력

---

원리

: M개의 수를 가진 수열B에서 하나씩 꺼내가 수열 A에 있는지 확인

 

* 참고링크 : 자료구조의 시간복잡도 https://hbase.tistory.com/185

---

풀이방법

1. 이중 반복문을 이용한 방법

2. Binary Search를 이용한 방법 

3. 자료구조를 이용한 방법 (ArrayList) [시간복잡도 O(n)]

4. 자료구조를 이용한 방법 (Hashset) : 제일 빠름 Best [시간복잡도 O(1)]

---

나의 코드

1. 이중 반복문을 이용한 방법

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

public class no1920 {
	/* 시간초과 : 이중for문 사용 방식 */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        br.readLine();
        String[] arrN = br.readLine().split(" ");
        int M = Integer.parseInt(br.readLine());
        boolean tf = false;
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            String X = st.nextToken();
            for (int j = 0; j < arrN.length; j++) {
                if (X.equals(arrN[j])) {
                    bw.write("1" + "\n");
                    tf = true;
                    break;
                }
            }
            if(tf== false) {
                bw.write("0" + "\n");
            } else {
                tf = false;
            }
        }

        bw.close();
    }
}

2. 자료구조를 이용한 방법 (ArrayList)

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

public class no1920 {
	/* 시간초과 : ArrayList 사용 방식 */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        ArrayList<String> listN = new ArrayList<>();
        StringTokenizer stst = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) listN.add(stst.nextToken());

        int M = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        while(M-->0) {
            String str = st.nextToken();
            if(listN.contains(str)) {
                bw.write("1"+"\n");
            } else {
                bw.write("0"+"\n");
            }
        }
        bw.close();
    }
}

3. 자료구조를 이용한 방법 (Hashset) : 제일 빠름 Best

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

public class no1920 {
/* Set 사용 */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        Set<String> setN = new HashSet<>();
        StringTokenizer stst = new StringTokenizer(br.readLine(), " ");
        for(int i =0 ; i<N ; i++) setN.add(stst.nextToken());

        int M = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        while(M-->0) {
            String str = st.nextToken();
            if(setN.contains(str)) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
    }
}

---

레퍼런스 코드

🎁hyoreal님의 블로그 : https://hyospital.tistory.com/51