BOJ | 10816 숫자 카드2 - Java

crystal·2021년 6월 19일

Algorithm

목록 보기

1/8

문제

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

입출력 예

Input	Output
10 6 3 2 10 10 10 -10 -10 7 3 8 10 9 -5 2 3 4 5 -10	3 0 0 1 2 0 0 2

문제 풀이 - Binary Search

백준 사이트는 프로그래머스 사이트랑 다른 점이 있었다.

필요한 패키지를 직접 import 해줘야 했다.
클래스의 이름은 반드시 Main이어야 한다.

👉 계속해서 오류가 나오길래 로직이 잘못됐나 한참 고민 했었던...🤣

숫자 카드 2 문제는 처음에 배열을 쓰고, for문 돌려서 풀면 되겠다 생각하고 제출했다.

위의 2가지를 지키지 않아서 에러가 떴고, 고치고 난 후 제출했는데

시간 초과 가 나와버렸다.. 같은 실수를 반복하지 않기 위해서 시간초과가 나온 이유를 정리하려고 한다.

- 시간초과가 나온 이유

1. 입력시에 Scanner 말고 BuffredReader를 사용하기

👉 결론부터 말하자면 Scanner보다 BufferedReader가 훨씬 빠르다. ✈

자바 카테고리에 상세하게 정리할 예정인데 이유는 두 가지이다.

Scanner의 regular expression의 남발
Scanner와 BufferedReader의 입력발생 횟수 차이

👉 'star'라는 글자를 입력 받는다고 가정할 때, Scanner 로 입력 시 입력 발생 횟수는 글자수 만큼 4번 발생한다. 이에 비해 BufferedReader로 입력 시 입력 발생 횟수는 버퍼에 쌓아놓고 입력이 발생해서 1회 발생한다.

왜 알고리즘 문제를 풀 때 입력으로 BuffredReader 를 주로 사용하는지 오류를 해결하면서 알게 되었다.

2. 출력시에 System.out.println() 말고 Buffer에 쌓아놓고 출력하기.

👉 마찬가지다. System.out.println()보다 Buffer가 훨씬 빠르다. ✈

결과를 도출했을때 System.out.println() 하지 말고,
Buffer로 결과를 append해서 마지막에 1회만 출력해야 한다.
```
  
```

3. 이진 탐색 2가지 만들기

원래 이진탐색은 중복되지 않은 값들 중에서 동일한 값이 존재하면 해당되는 값을 반환한다.
이 문제는 중복되는 값들이 존재한다.
따라서 중복된 값들을 이진탐색해서 해당되는 값이 몇개인지 알기 위해서는
lowBound, upperBound형태로 두가지 이진탐색을 만들어야 한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	
	// static으로 선언 => 후에 upper_bound()와 lower_bound()에서 사용할 예정
	static int n_cardNumbers[];
	
 	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder builder = new StringBuilder();
		
		// 첫째줄 상근이가 가지고 있는 카드 숫자 갯수 n  
		int n = Integer.valueOf(br.readLine());
		
		//  둘째줄 숫자 카드에 적혀있는 N개의 정수
		String[] n_lines = br.readLine().split(" ");
		
		// String 타입의 n_lines의 숫자카드들을 담을 int 배열 n_cardNumbers
		n_cardNumbers = new int[n];
		
			// 상근이가 가지고 있는 숫자카드의 정수들을 int 배열 n_cardNumbers에 담는다.
			for (int i = 0; i < n; i++) {
				n_cardNumbers[i] = Integer.valueOf(n_lines[i]);
			}
		
		// 이진탐색 하기 전에 "정렬"을 해준다. 오름차순
		Arrays.sort(n_cardNumbers);
		
		// 셋째줄 : 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 정수의 갯수 : M
		int m = Integer.valueOf(br.readLine());
		
		// 넷째줄 : 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수
		// " "으로 숫자를 분리하므로 split(" ") 사용
		String[] m_lines = br.readLine().split(" ");
		
		
		for(int i = 0; i < m; i++) {
			
			// 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수 중 하나
			int num = Integer.valueOf(m_lines[i]);
			
            // 연속되는 수 중 가장 낮은 인덱스를 담을 변수 lowIndex
			int lowIndex = lower_bound(num);
			
			// 연속되는 수 중 가장 높은 인덱스를 담을 변수 highIndex
			int highIndex = upper_bound(num);
			
			// 값이 존재하지 않을 때
			if(lowIndex == -1) {
				
				// 0 반환
				builder.append("0 ");
			}
			else {
				
				// 예시 : 6 3 2 10 10 10 -10 -10 7 3 
				// 연속되는 수 10 lowIndex = 3
				// 연속되는 수 10 highIndex = 5
				// 3개가 존재하는 것이므로 5 - 3 + 1
 				// 값이 하나만 존재 할 때도 2, 2-2+1 = 1 개 존재 
				builder.append((highIndex - lowIndex + 1) );
			}
		}
		// 출력
		System.out.println(builder);
	}

	// 연속되는 수 중 가장 높은 인덱스를 반환할 upper_bound 메서드
	private static int upper_bound(int num) {
		// 상근이가 갖고있는 정수 카드의 갯수 n
		int n = n_cardNumbers.length;
		
		int left = 0; // 맨 왼쪽의 인덱스 
		int right = n-1; // 맨 오른쪽의 인덱스
		
		int index = -1; // 못 찾았을 경우에 index가 -1 
		
		// left 포인터가 right에 도달할 때까지 
		while (left <= right) {
			
            // 중간 지점 계산
			int mid = (left + right) / 2;
			
			// 상근이가 갖고 있는 정수카드 중 중간값과 
			// 전달받은 정수(m개의 정수중 하나)가 같을 때
            // 정수카드 값을 찾았을 때                
			if(n_cardNumbers[mid] == num) {
				
                index = mid; // 값이 존재하는 인덱스 반환
				right = mid -1; // 오른쪽 범위를 줄여준다. 
				
			}
			// 정수카드값이 탐색값보다 클 때 
            // 탐색값 왼쪽에 위치                 
			else if (n_cardNumbers[mid] > num) {
				right = mid - 1;
  				//오른쪽을 찾을 필요가 없으니 
  				//오른쪽범위를 줄여준다. 
			}
  			// 정수카드값이 탐색값보다 작을 때
  			// 탐색값 오른쪽에 위치 
			else {
				left = mid + 1;
  				// 왼쪽 찾을 필요가없으니 
  				// 왼쪽 범위 증가시켜준다.
			}
		}
		return index;
}

	// 연속되는 수 중 가장 낮은 인덱스를 반환할 lower_bound 메서드
	private static int lower_bound(int num) {
	
		// 상근이가 갖고있는 정수 카드의 갯수 n
		int n = n_cardNumbers.length;
		
		int left = 0; // 맨 왼쪽의 인덱스 
		int right = n-1; // 맨 오른쪽의 인덱스
		
		int index = -1; // 못 찾았을 경우에 index가 -1 
		
		// left 포인터가 right에 도달할 때까지 
		while (left <= right) {
			int mid = (left + right) / 2;
                            
            // 상근이가 갖고 있는 정수카드 중 중간값과 
			// 전달받은 정수(m개의 정수중 하나)가 같을 때
            // 정수카드 값을 찾았을 때 
			if(n_cardNumbers[mid] == num) {
				index = mid;
				left = mid + 1; // 왼쪽 범위 증가
				
			}
            // 정수카드 값이 탐색값보다 클 때 
            // 탐색값이 왼쪽에 위치                 
			else if (n_cardNumbers[mid] > num) {
				right = mid - 1; 
  				// 오른쪽에 찾을 필요가 없으니 
  				// 1 줄여준다. 
			}
  			// 정수카드 값이 탐색값보다 작을 때
  			// 탐색값 오른쪽에 위치 
			else {
				left = mid + 1;
  				//왼쪽에 찾을 필요가없으니 
  				//1 증가 
			}
		}
		return index;
}