백준 10815. 숫자 카드

🅰 백준 10815. 숫자 카드

10815번: 숫자 카드

✏️ 문제 풀이

• 숫자를 정렬한 다음 이분탐색을 이용하여 문제를 풀었다.
• 중간값을 비교하여 탐색하는 과정을 재귀로 구현하였는데 생각보다 수행시간이 오래걸렸다. 
• 그래서 재귀방식 말고 main문 안에서 바로 답을 찾도록 구현 하였는데 0.1초밖에 안 줄어들었다.
• start, end, middle 값 설정
  목표값 middle과 비교하여 
  1. ans<middle 이면 
  start = 고정
  end = middle-1
  middle = start+end/2
  
  2. ans>middle이면
  start = middle+1
  middle = start+end / 2
  end = 고정

 

분명 2초까지였는데 4초가 통과한 이유는 뭘까...?

시간이 너무 오래걸리는 같아 List에 넣어서 Contains함수를 이용하여 M이 있는지 구현하였으나 ArrayList, LinkedList 둘 다 시간초과가 떴다. 코드는 거의 2배가 줄어들었는데 시간초과가 뜬 이유가 뭘까 하고 찾아보니 Contains함수는 리스트를 처음부터 끝까지 탐색하여 찾는 기법이라 시간복잡도가 O(1)이였기 때문이였다. 오래 걸리는 문제들은 Contains함수로 풀면 안되겠다.

 

 

✏️ main함수 내 구현 소스코드

package divideandconquer;

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

public class Main_실버4_10815_숫자카드 {
	private static StringBuilder sb = new StringBuilder();
	private static int arrN[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		arrN = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arrN[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arrN);
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int start = 0, end = arrN.length - 1, middle = (start + end) / 2;
			int ans = Integer.parseInt(st.nextToken());
			boolean check = false;
			while (start <= end) {
				if (arrN[middle] == ans) {
					sb.append(1);
					check = true;
					break;
				} else if (arrN[middle] < ans) {
					start = middle + 1;
				} else {
					end = middle - 1;
				}
				middle = (start + end) / 2;
			}
			if(!check) {
				sb.append(0);
			}

			//search(start, end, middle, ans);
			System.out.print(sb + " ");
			sb.setLength(0);
		}
	}
}

✏️ 재귀함수를 이용한 소스코드

package divideandconquer;

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

public class Main_실버4_10815_숫자카드 {
	private static StringBuilder sb = new StringBuilder();
	private static int arrN[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		arrN = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arrN[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arrN);
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int start = 0, end = arrN.length - 1, middle = (start + end) / 2;
			int ans = Integer.parseInt(st.nextToken());
			search(start, end, middle, ans);
			System.out.print(sb + " ");
			sb.setLength(0);
		}
	}


	private static void search(int start, int end, int middle, int ans) {
		if (start > end) {
			sb.append(0);
			return;
		}

		if (arrN[middle] == ans) {
			sb.append(1);
			return;
		} else if (ans < arrN[middle])
			end = middle - 1;
		else
			start = middle + 1;
		middle = (start + end) / 2;

		search(start, end, middle, ans);
	}
}

✅ 후기

• 이분탐색을 이용했음에도 불구하고 시간이 오래 걸린 이유를 잘 모르겠다. log2 N인데 18.3xxxx