[JAVA] 10816번 - 숫자 카드 2

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

정수 M이 숫자카드 N에 속하는지 판단해야한다

마찬가지로 이분탐색을 이용한다

 

배열에 포함 되는지 판단하는 시간복잡도는 O(M)이다

 

시간복잡도를 계산해보자

N은 500,000이고 M도 500,000이다.

일반적인 시간복잡도인 O(N)인 경우(배열의 원소를 하나씩 비교하면서 탐색)

O(M) * O(N)이므로 바로 시간초과다

 

O(LogN)일경우

O(M) * O(LogN) 이니까 약 285만 회로 1초안에 충분히 가능하다 

 

어떤 알고리즘을 써야하는지 판단했으니 이제 어떻게 문제를 풀지 생각해야한다

이번에는 숫자의 유무가 아닌 몇개를 가지고 있는지 출력해야한다

 

이분탐색의 알고리즘 원리인 low과 high를 이용했다.

원소의 왼쪽 끝 값과 오른쪽 끝 값을 이용한다

 

-10 -10 2 3 3 6 7 10 10 10 의 배열에서 3을 찾는다고 가정할 때

3이 위치하는 가장 왼쪽의 인덱스 3

3이 위치하는 가장 오른쪽의 인덱스+1(찾고자 하는 값을 초과한 값을 처음 만나는 위치) 5

5-3=2 이므로 3은 두번 등장한다.

 

중복 원소의 길이 = (상한-하한)

하한코드는 lowerBound

상한코드는 upperBound 

 

lower에서는 찾은 값과 찾고자 하는 값이 크거나 같을때 계속 작아지고, upper는 찾은 값이 찾고자 하는 값보다 클떄만 커져야한다

 

lowerBound

 

 

 

upperBound

이렇게 하면 lower는 2 upper는 4이므로

upper-lower를 하면 2가 나온다. 4는 2번 나왔다는 거다 

 

두번째로는 해시맵을 이용해서도 풀어봤다

key는 카드 값, value는 카드 개수의 자료구조를 만들고 key가 존재하면 1을 추가한다

HashMap에서 key값을 이용하여 찾아주기만 하면 됨으로 O(1) 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. N을 입력받는다

2. N크기만큼 arr배열에 숫자들을 입력받는다

3. 배열을 오름차순 정렬한다

4. m을 입력받는다

5. m만큼 수를 입력받음과 동시에 해당 숫자의 개수를 세기위해 (상한-하한) 을 수행한다

6. 출력한다 

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

1회차 시도

 -> 수 찾기1과 마찬가지로 똑같이 하고 해당 숫자가 있을때마다 cnt를 해줫다

근데 답이 이상하게 나왔다 

		for(int i=0; i<m; i++) {
			if(Arrays.binarySearch(arr, Integer.parseInt(st.nextToken())) >=0) {
				cnt++;
				sb.append(cnt);
			}
			else {
				sb.append(0);
			}
			
		}
		
		System.out.println(sb);

 

정답코드

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int n = Integer.parseInt(br.readLine());	
		int arr[] = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
		
		Arrays.sort(arr);
		
		int m = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();
		
		for(int i=0; i<m; i++) {
			int k = Integer.parseInt(st.nextToken());
			sb.append(upperBound(arr,k) - lowerBound(arr,k)).append(" ");
			
		}
		
		System.out.println(sb);
	}

	private static int lowerBound(int[] arr, int k) {
		int low = 0;
		int high = arr.length;
		
		while(low<high) {
			int mid= (low+high)/2;
			if(arr[mid]>=k) { //k값이 중간위치 보다 같거나 작으면
				high = mid; //high를 mid로 줄여서 왼쪽 부분 탐색
			}
			else {
				low = mid +1; //k가 mid값보다 오른쪽에 있으니까 low를 옮겨 오른쪽 탐색
			}
		}
		return low;
	}

	private static int upperBound(int[] arr, int k) {
		int low = 0;
        int high = arr.length;

        while(low<high) {
        	int mid= (low+high)/2;
        	if(arr[mid]>k) { //k값이 중간위치보다 작으면
        		high = mid; //왼쪽부분 탐색
        	}
        	else {
        		low=mid+1;
        	}
        			
        }
    
        return low;
	}

 

해시맵을 이용

public class Main {
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int n = Integer.parseInt(br.readLine());	
		HashMap<Integer, Integer> map = new HashMap<>();
		
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            
            if(!map.containsKey(num)) {
            	map.put(num, 1);
            }
            else {
            	map.put(num, map.get(num)+1);
            }
        }
		
		
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine(), " ");
		StringBuffer sb = new StringBuffer();
		
		for(int i=0; i<m; i++) {
			int k = Integer.parseInt(st.nextToken());
			if(map.containsKey(k)) {
				sb.append(map.get(k)+ " ");
			}
			else {
				sb.append(0+ " ");
			}
			
		}
		
		System.out.println(sb);
	}



	}