[백준]10815번 숫자카드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

 

 

 

(구상)

버퍼리더로 입력을 받는다. 

상근이가 가진 카드의 수, 비교해야할 수들을 스트링 토크나이져로  두개의 배열에 담기 

for문을 이용하여 상근이가 가진 수가  두번째 배열에 존재 한다면 두번째 배열의 수를 1 ,

존재하지 않는다면 0 으로 바꿔준  후 출력하기 

 

package codingTest;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Algorithm8 {
	public static void main(String[] args) throws Exception {

		int[] arr1;
		int[] arr2;
		StringTokenizer st;

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());
		st = new StringTokenizer(bf.readLine());

		arr1 = new int[n];
		for (int i = 0; i < arr1.length; i++) {
			arr1[i] = Integer.parseInt(st.nextToken());
		}

		int m = Integer.parseInt(bf.readLine());
		arr2 = new int[m];

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < arr2.length; i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < m; i++) {
			boolean fl = false;
			for (int j = 0; j < n; j++) {
				if (arr2[i] == arr1[j])
					fl = true;

			}
			if (fl) {
				arr2[i] = 1;
			} else {
				arr2[i] = 0;
			}
			System.out.print(arr2[i] + " ");
		}

	}
}

결과 : 입출력은 문제 없이 돌아가지만 시간초과이다. 

 

다른방법을 생각해 주었다. 

 

 

(구상)

상근이가 가진 카드의 값은 set에 담아준다. 

그다음 비교 대상이 될 카드의 값이 배열에 존재한다면 바로 1, 없다면 0을 출력하도록 구성 

 

통과한 답안은 다음과 같다. 

int 형으로 변환하여 비교한 답안

package codingTest;

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

public class Algorithm8_1 {
	public static void main(String[] args) throws Exception {

		StringTokenizer st;

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());

		// 집합에 담아주기
		HashSet<Integer> set = new HashSet();
		st = new StringTokenizer(bf.readLine());

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

		int m = Integer.parseInt(bf.readLine());
		st = new StringTokenizer(bf.readLine());

		for (int i = 0; i < m; i++) {
			if (set.contains(Integer.parseInt(st.nextToken()))) {
				System.out.print(1 + " ");

			} else {
				System.out.print(0 + " ");

			}
		}

	}
}

String 형으로 비교한 답안

package ja08;

//백준 10815 숫자카드 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Setset {
	public static void main(String[] args) throws Exception {

		StringTokenizer st;

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());

		// 집합에 담아주기
		HashSet<String> set = new HashSet();
		st = new StringTokenizer(bf.readLine());

		for (int i = 0; i < n; i++) {
			set.add(st.nextToken());
		}

		int m = Integer.parseInt(bf.readLine());
		st = new StringTokenizer(bf.readLine());

		for (int i = 0; i < m; i++) {
			if (set.contains(st.nextToken())) {
				System.out.print(1 + " ");

			} else {
				System.out.print(0 + " ");

			}
		}

	}
}