Do it! 알고리즘 코딩 테스트 (29번 ~ 31번)

29번 수 찾기

---

내가 떠올린 풀이 해설

N의 최대 범위가 100,000이므로 단순 반복문으로는 풀 수가 없다. 이진 탐색을 적용하면 logn의 시간 복잡도를 사용하므로 이진 탐색을 이용해서 풀어야 된다. 이진 탐색은 정렬이 된 상태여야 하므로 정렬을 하고 start = 0 end = arr.length - 1로 기준을 잡는다. midV에 중앙값을 넣는다. 만약 midV가 크면 end의 값을 mid - 1로 바꿔준다. 작으면 start값을 mid + 1의 값으로 바꿔준다. 같으면 find를 true로 넣어준 후 break로 빠져나온다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1920 {

	public static void main(String[] args) throws 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());
		
		for(int i = 0; i < m; i++) {
			int target = Integer.parseInt(st.nextToken());
			boolean result = false;
			int start = 0;
			int end = arr.length - 1;
			while(start <= end) {
				int mid = (start + end) / 2;
				int midV = arr[mid];
				if(midV > target) {
					end = mid - 1;
				}
				else if(midV < target) {
					start = mid + 1;
				}
				else {
					result = true;
					break;
				}
			}
			if(result) {
				System.out.println(1);
			}
			else {
				System.out.println(0);
			}
		}
	}
}

---

30번 문제 기타 레슨

---

내가 떠올린 풀이 해설

문제를 이해하는데 시간이 걸렸다. 블루레이 크기가 모두 같고 녹화 순서가 바뀌지 않아야 함이라는 조건에서 이진 탐색을 사용해야된다는 단서이다. 첫 레슨부터 마지막까지 차례대로 저장하다 보면 지정한 크기로 모든 레슨을 저장할 수 있는지 판단할 수 있기 때문이다.

모두 저장할 수 있으면 크기를 줄이고 저장할 수 없다면 크키를 늘려주는 방식으로 크기의 최솟값을 알 수 있다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek2343 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int []arr = new int[n];
		int start = 0;
		int end = 0;
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			if(start < arr[i]) {
				start = arr[i];  // 레슨 최댓값을 시작 인덱스로 저장하기
			}
			end = end + arr[i]; // 모든 래슨의 총합을 종료 인덱스로 저장하기
		}
		while(start <= end) {
			int mid = (start + end) / 2;
			int sum = 0;
			int count = 0;
			for(int i = 0; i < n; i++) {  // mid 값으로 모든 레슨을 저장할 수 있는지 확인
				if(sum + arr[i] > mid) {
					count++;
					sum = 0;
				}
				sum = sum + arr[i];
			}
			if(sum != 0) {  // 탐색후 sum이 0이 아니면 블루레이가 1개 더 필요하므로 더함
				count++;
			}
			if(count > m) {
				start = mid + 1;
			}
			else {
				end = mid - 1;
			}
		}
		System.out.println(start);
	}
}

 

---

31번 문제 K번째 수

---

책 풀이 해설

k의 범위가 1 ~ min(10^9, N^2)이므로 시간 복잡도가 N^2인 알고리즘은 사용할 수 없다. 이진 탐색으로 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄이는 방법으로 B [k] 값을 구한다. 작은 수의 개수가 k - 1 개인 중앙값이 정답이다.

---

정확한 풀이

import java.util.*;
public class Baek1300 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		long start = 1;
		long end = m;
		long answer = 0;
		
		while(start <= end) {
			long mid = (start + end) / 2;
			long cnt = 0;
			
			for(int i = 1; i <= n; i++) {
				cnt += Math.min(mid / i, n);
			}
			if(cnt < m) {
				start = mid + 1;
			}
			else {
				answer = mid;
				end = mid - 1;
			}
		}
		System.out.println(answer);
	}
}

---

문제점

이진탐색을 떠올리기 힘들었고 중앙값보다 작은 수의 개수를 세면서 줄이는 방법을 이용해서 작은 수의 개수가 k -1 개인 중앙값이 정답이라는 아이디어를 못 떠올렸다.

---

백준 11866번 요세푸스 문제 0

내가 떠올린 풀이 해설

기본 큐를 이용해서 푸는 문제이다. 큐가 비어 있을 때까지 반복한다. 큐를 pop 하고 다시 그 수를 push 해서 k번째 pop을 할 때 String str에 더해준다. 

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek11866 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		Queue<Integer> que = new LinkedList<>();
		
		for(int i = 1; i <= n; i++) {
			que.offer(i);
		}
		int cnt = 0;
		String str = "<";
		while(!que.isEmpty()) {
			cnt++;
			if(cnt == m) {
				str += que.poll() + ", ";
				cnt = 0;
			}
			else {
				que.offer(que.poll());
			}
		}
		str = str.substring(0, str.length() - 2);
		System.out.print(str + ">");
	}
}

---

오늘의 회고

오늘은 이진탐색 문제를 풀었습니다. 이진 탐색을 사용하는 문제에서 이진 탐색을 사용해야 되는 아이디어를 떠올리기 힘들었습니다. 마지막 문제는 어려워서 풀지 못했습니다. 이진 탐색에 대해 공부하기 위해 내일은 이진 탐색 중에 난의도가 높지 않은 문제를 풀겠습니다.