[Java] 백준 23791번 : K번째 음식 찾기 1

1. 문제

https://www.acmicpc.net/problem/23791

23791번: K번째 음식 찾기 1

 

 

 

2. 풀이 과정

병합 정렬 + 이진 탐색 문제이다. 여기서 시간 단축을 위해 누적합 개념을 추가적으로 사용했다.

 

예를 들어, 입력이 아래와 같이 주어진다면

4
1 5 10 15
2 3 8 9

 

병합 정렬하면서 한식, 양식 수를 세서 누적합을 구해놓고 이진탐색할 때 이용한다.

 

	1	2	3	5	8	9	10	15
한식	1	1	1	2	2	2	3	4
양식	0	1	2	2	3	4	4	4

 

만약 한식 1개, 양식 4개에서 4번째 음식을 구한다고 하면, (가능한 한식 수)+(가능한 양식 수) = 4인 값을 찾으면된다. 여기서는 한식은 최소/최대 1개 가능하므로 양식이 3개인 8이 답이 된다.

 

import java.io.*;
import java.util.*;

public class Boj23791 {
	static int n, cnt[][];//한식 수, 양식 수
	
	public static int binarySearch(int n1, int n2, int k) {
		int s = 0, e = 2*n-1;
		while(s<=e) {
			int m = (s+e)/2;
			int temp = Math.min(n1, cnt[m][0])+Math.min(n2, cnt[m][1]);
			//n1 + n2 ==k인 경우가 있음 => 경계치를 더해주기 위해 같을 때는 e=m-1
			if(temp<k) {
				s = m+1;
			}
			else {
				e = m-1;
			}
		}
		return s;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		int arr[][] = new int[2][n];
		int pos[][] = new int[2*n][2];//위치
		cnt = new int[2*n][2];
		for(int i=0; i<2; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//병합 정렬
		int x=0, y=0, idx=0;
		int han = 0, yang = 0;//한식 수, 양식 수
		while(x<n || y<n) {
			if(y>=n || (x<n && arr[0][x]<=arr[1][y])) {
				cnt[idx][0] = ++han;
				cnt[idx][1] = yang;
				pos[idx][0] = 1;
				pos[idx++][1] = ++x;
			}
			else if(x>=n || (y<n && arr[1][y]<arr[0][x])) {
				cnt[idx][0] = han;
				cnt[idx][1] = ++yang;
				pos[idx][0] = 2;
				pos[idx++][1] = ++y;
			}
		}
		
		//이진탐색
		StringBuilder sb = new StringBuilder();
		int q = Integer.parseInt(br.readLine());
		for(int i=0; i<q; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int ans = binarySearch(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			sb.append(pos[ans][0]).append(" ").append(pos[ans][1]).append("\n");
		}
		System.out.print(sb.toString());
	}

}