[JAVA] 1920번 - 수 찾기

문제 탐색하기

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

 

이 문제의 유형은 이분탐색이다.

왜 이 문제를 이분탐색으로 풀어야하는지 질문했는데 지금은 하나씩 배우는 단계라고 생각하면 된다고 하셔서 일단 이분탐색을 사용하겠다

 

이분탐색의 알고리즘은 원래 잘 알고 있어서 생략한다(구글링하면 설명이 아주 잘되어있다)

자바에서는 Arrays.binarySearch로 라이브러리를 제공하고 있다!

 

근데 생각해볼건 그냥 탐색을 해도 되는데 왜 이분탐색을 하는가?이다

일단 시간복잡도가 기존의 탐색에 비해 빠르다. O(logN) 이다

기존에 배열을 탐색하는건 O(N)이니까 상대적으로 빠르다 

 

 

문제에서 N개의 정수가 있고 N은 100,000이다. M도 100,000이므로 입력이 매우 크다

단순하게 이중 for문으로 구할 수도 있다. 근데  시간제한은 1초이고 그러면 N*M이니까 1000억번을 연산해야한다 그럼 시간이 초과된다 컴퓨터는 1초에 약 3-5억번 연산을 할 수 있기 때문

 

 

코드 설계하기

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

 

1. N을 입력받는다

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

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

4. m을 입력받는다

5. m만큼 수를 입력받음과 동시에 이분탐색을 수행한다 

Arrays.binarySearch

해당 key를 찾으면 그 위치를 리턴하고 그렇지 않으면 음수 반환 

 

6. if(Arrays.binarySearch(arr, Integer.parseInt(st.nextToken())) >= 0) 

이분탐색의 결과가 0이상이라는것은 해당 숫자가 배열 arr에 존재한다는것을 의미

그러면 1을 추가

아니면 0을 추가

 

시도 회차 수정 사항

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

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());	
		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();
		
		// m개의 수를 입력받고 arr배열에 존재하는지 확인
		for(int i=0; i<m; i++) {
			if(Arrays.binarySearch(arr, Integer.parseInt(st.nextToken())) >=0) {
				sb.append(1).append("\n");
			}
			else {
				sb.append(0).append("\n");
			}
			
		}
		System.out.println(sb);
		
		
	}
}