[java][boj][s4] 10816. 숫자 카드 2

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

풀이

우선 두 가지 방법으로 풀었다 이 문제가 이분탐색 페이지에 있었기 때문에 이분탐색을 통해 풀어봤고, 시간 초과가 자꾸 나서 그냥 배열의 인덱스 값을 추가하는 방식으로 통과했다 이분탐색 시간 초과 해결하는 방법들을 구글링을 통해서 보긴 했는데... 화가 나서 그냥 뒀다 다음에 다시 풀어봐야지 우선 두 가지 코드 모두 올려놓기는 해야겠다

코드

package lv21_이분탐색;

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

//이분탐색(시간 초과로 실패)
public class s4_10816_숫자카드2 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int[] card = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i<N; i++) {
			card[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(card);
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<M; i++) {
			int num = Integer.parseInt(st.nextToken());
			int start = Arrays.binarySearch(card, num);
			if(start>=0) {
				int cnt = 1;
				for(int j = start+1; j<N; j++) {
					if(card[j]>num) break;
					cnt++;
				}
				for(int k = start-1; k>=0; k--) {
					if(card[k]<num) break;
					cnt++;
				}
				bw.append(cnt+ " ");
			} else bw.append("0 ");
			
		}
		
		bw.flush();
		bw.close();
		br.close();

	}

}

package lv21_이분탐색;

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

public class s4_10816_숫자카드2_2 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int[] cnt = new int[20000001];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i<N; i++) {
			int num = Integer.parseInt(st.nextToken());
            //카드에 적힌 숫자를 인덱스로 사용해 배열에 카드 개수 더하기
			cnt[num + 10000000]++;
		}
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<M; i++) {
			int num = Integer.parseInt(st.nextToken());
            //해당 숫자를 인덱스로 사용해 더해 놓은 개수 출력
			sb.append(cnt[num + 10000000]).append(" ");
			
		}
		
		System.out.println(sb);

	}

}

결과

 

#자바 #java #boj #백준 #알고리즘