#10816 : 숫자 카드 2

풀이방법

사용된 것:

해시맵(HashMap)

이분탐색법

 

해시맵을 사용하는 방법, 이분탐색법을 이용하는 방법이 있다.

시간은 해시맵이 덜 걸리고

메모리는 이분탐색법이 덜 사용한다.

 

 

 

 

2022.04.19

먼저 해시맵을 사용하는 방법이다.

 

<Integer, Integer>의 데이터 쌍을 저장하는 해시맵을 하나 선언한다.

Key에는 카드의 번호, Value에는 카드의 개수를 저장할 것이다.

 

상근이가 가지고 있는 카드들의 번호를 차례차례 읽어오면서 개수를 세어준다.

처음 세는 카드라면 해시맵에 (해당 카드의 번호, 1)의 요소를 새롭게 추가한다.

이미 센 적 있는 카드라면 해시맵에 (해당 카드의 번호, 현재까지 센 개수에 1을 더한 값)의 요소를 추가한다. 해시맵은 키가 동일한 다수의 요소를 저장하지 않으므로 자동으로 이전의 요소는 지워진다.

이때 현재까지 센 개수는 get(해당 카드의 번호)로 알아올 수 있다.

 

그 다음에는 정답을 출력한다.

몇 장 가지고 있는지 구분해야 하는 카드의 번호를 하나 읽어올 때마다,

해시맵에 해당 카드 번호와 동일한 Key가 존재한다면 get(해당 카드의 번호)를 하여 개수를 출력한다.

그런 Key가 존재하지 않는다면 0을 출력한다.

 

 

 

 

 

2022.05.17

이분탐색법을 이용하여 푸는 방법이다.

 

이분탐색법을 이용하면

오름차순으로 정렬된 길이가 N인 리스트 상에서

lower_bound와 upper_bound를

$\log_2 N$ 의 시간복잡도 내에 구할 수 있다.

 

lower_bound란,

오름차순으로 정렬된 리스트와 특정 값 target에 대하여,

리스트 내에서 target 이상의 값이 처음으로 등장하는 위치의 인덱스를 가리킨다.

만약 target 이상의 값이 리스트에 없다면 가장 마지막 인덱스를 가리킨다.

 

target = 11일 때, 아래 리스트에서 lower_bound는 4이다. (인덱스가 0부터 8까지일 때)

 

2

3

3

7

11 lower_ bound

11

11

13

17

 

upper_bound란,

오름차순으로 정렬된 리스트와 특정 값 target에 대하여,

리스트 내에서 target 초과의 값이 처음으로 등장하는 위치의 인덱스를 가리킨다.

만약 target 이상의 값이 리스트에 없다면 가장 마지막 인덱스를 가리킨다.

 

target = 11일 때, 아래 리스트에서 upper_bound는 7이다. (인덱스가 0부터 8까지일 때)

2

3

3

7

11

11

11

13 upper_ bound

17

 

그럼 위 리스트에서 11의 개수는

upper_bound 값에서 lower_bound 값을 빼준 3이다.

 

11이 리스트에 존재하지 않는 경우에는 lower_bound와 upper_bound가 모두 8이므로 8-8=0 이라는 정답을 올바르게 구할 수 있다.

 

단! 주의할 점이 있다.

리스트에 11이 존재하지만 11 초과의 수가 존재하지 않을 경우에는 올바른 정답보다 1 작은 수가 구해지게 된다. 따라서 이런 경우엔 정답에 1을 더해주어야 한다.

 

 

 

 

 

코드

Java(2022.04.19(해시맵))

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//해시맵<카드번호, 카드개수>
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		//가지고 있는 카드의 개수를 해시맵에 저장하기
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++) {
			int temp = Integer.parseInt(st.nextToken());
			//이미 센 적 있는 카드라면 카드개수 1 증가
			if(hm.containsKey(temp)) hm.put(temp, hm.get(temp)+1);
			//처음 세는 카드라면 (카드번호, 1) 추가
			else hm.put(temp, 1);
		}
		
		//정답 출력
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i<m; i++) {
			int temp = Integer.parseInt(st.nextToken());
			//가지고 있는 카드라면 get(카드번호)를 출력
			if(hm.containsKey(temp)) sb.append(hm.get(temp) + " ");
			//가지고 있지 않는 카드라면 0 출력
			else sb.append(0 + " ");
		}
		
		System.out.print(sb);

	}

}

 

Java(2022.05.17(이분탐색법))

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

public class Main {
	
	static int[] list;
	
	//list 상에서 target 이상의 수가 등장하는 첫 인덱스를 리턴
	//target 이상의 수가 없다면 가장 마지막 인덱스를 리턴
	public static int lower_bound(int target) {
		
		int start=0;
		int end=list.length-1;
		
		while(start<end) {
			int mid = (start+end)/2;
			if(list[mid]>=target) end = mid;
			else start = mid+1;
		}
		
		return end;
		
	}
	
	//list 상에서 target 초과의 수가 등장하는 첫 인덱스를 리턴
	//target 초과의 수가 없다면 가장 마지막 인덱스를 리턴
	public static int upper_bound(int target) {
		
		int start=0;
		int end=list.length-1;
		
		while(start<end) {
			int mid = (start+end)/2;
			if(list[mid]>target) end = mid;
			else start = mid+1;
		}
		
		return end;

	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		
		//가지고 있는 카드 읽어오기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		list = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++) list[i] = Integer.parseInt(st.nextToken());
		
		//카드 목록을 오름차순 정렬
		Arrays.sort(list);
		
		//정답 구하기
		StringBuilder sb = new StringBuilder();
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<m; i++) {
			int t = Integer.parseInt(st.nextToken());
			//upper_bound 값에서 lower_bound 값을 빼주면 됨.
			int answer = upper_bound(t)-lower_bound(t);
			//단, t와 일치하는 값은 존재하는데 초과인 값이 없을 경우 정답이 1 적게 계산되므로 1을 더해주어야 함.
			if(list[n-1] == t) answer++;
			sb.append(answer + " ");
		}
		//정답 출력
		System.out.print(sb);

	}

}