220823 - 좋은 수

◾ 좋은 수 : 백준 1060번 (골드 1)

• https://www.acmicpc.net/problem/1060

문제

정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다.

• A와 B는 양의 정수이고, A < B를 만족한다.
• A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.

정수 x를 포함하는 좋은 구간의 개수가 정수 y를 포함하는 좋은 구간의 개수보다 작으면 x는 y보다 더 좋다고 한다. x와 y를 포함하는 좋은 구간의 개수가 같거나, 구간의 개수가 둘 다 무한대와 같은 경우, 작은 수를 더 좋다고 한다.

집합 S가 주어지고, 이를 이용해 전체 정수를 더 좋은 수가 앞으로 오게 정렬했다고 가정하자. 앞에 오는 수 n개를 구해보자.

---

입력

• 첫째 줄 : 집합의 크기 L(1 <= L <= 50)
• 둘째 줄 : 집합에 포함된 정수. (중복되는 정수 X)
• 셋째 줄 : 출력할 수 n (1 <= n <= 100)

출력

• 상위 n개의 수를 공백으로 구분해 출력.

입출력 예

Input	Output
1 3 6	3 1 2 4 5 6

---

◾ 풀이

1. 해설

• 좋은 구간이 가능한 범위를 우선순위 큐에 추가하여 좋은 구간의 수가 작은 것부터 출력.
  1. 좋은 구간의 수가 작은 것.
  2. 좋은 구간의 수가 같거나, 무한대인 경우 : 작은 수.
• [a..i..mid..b] : a-범위 시작 값, b-범위 종료 값, mid-중앙값, i-좋은 구간을 계산하려는 값
  • i의 좋은 구간 = (b - i) * (i - a + 1) + (i - a) = (idx+1)(b - (idx + a)) + idx
    • (i - a) == idx(인덱스)
    • i = (idx +a)
    • idx는 0부터 시작
    • 범위의 반대편에 위치한 수는 서로 좋은 구간의 수가 같음.
• 좋은 구간의 범위 : [1, 2, 3, 4, 5, 6]
  • 1 : (0+1)(6-(0+1)) + 0 = 5개
    • [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 6]
  • 2 : (1+1)(6-(1+1)) + 1 = 9개
    • [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 6]
    • [2, 3], [2, 3, 4], [2, 3, 4, 5], [2, 3, 4, 5, 6]
  • 3 : (2+1)(6-(2+1)) + 2 = 11개
    • [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 6]
    • [2, 3], [2, 3, 4], [2, 3, 4, 5], [2, 3, 4, 5, 6]
    • [3, 4], [3, 4 ,5], [3, 4, 5, 6]
  • 4 : 3의 결과 = 11개
  • 5 : 2의 결과 = 9개
  • 6 : 1의 결과 = 5개

---

2. 프로그램

1. 집합의 크기, 집합 입력.
   • 집합 입력 시 집합의 값을 우선순위 큐에 추가. (좋은 구간의 수가 0)
2. 집합의 값을 기준으로 좋은 구간을 범위를 구해 우선순위 큐에 추가.
   • 좋은 구간의 수 기준 오름차순.
   • 범위의 최소값(왼쪽값) 기준 오름차순.
3. n개의 수를 차례로 출력.
   • 값 출력시 왼쪽, 오른쪽 순으로 출력.
     • 이후, 해당 구간의 새로운 좋은 구간의 수를 구해 재추가.
   • 왼쪽, 오른쪽 값이 같거나 1차이인 경우 => 해당 범위의 값을 모두 출력한 경우 범위 삭제
   • 모든 값을 출력하거나 우선순위 큐가 비게되면 종료.
4. n개의 수를 모두 출력하지 못했다면 집합의 값 중 [최대값 + 1]부터 차례로 출력.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class GoodNum implements Comparable<GoodNum>{
	int left;	// 왼쪽 범위.
	int right;	// 오른쪽 범위.
	int idx;	// 왼쪽, 오른쪽에서의 인덱스.(범위에서 반대편에 위치한 값과 좋은 구간의 수가 같음.)
	int count;	// 좋은 구간의 수.
	
	public GoodNum(int left, int right, int idx, int count) {
		super();
		this.left = left;	
		this.right = right;	
		this.idx = idx;		
		this.count = count;	
	}
	
	// 정렬 기준
	// 1. 좋은 구간의 개수 (오름차순)
	// 2. 작은 수 (오름차순) : [left, right] 범위를 표현하므로 left가 작다면 작은 수.
	@Override
	public int compareTo(GoodNum o) {
		int res = this.count - o.count;
		if (res == 0) return this.left - o.left;
		
		return res;
	}
}

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		// 집합의 크기.
		int L = Integer.parseInt(in.readLine());
		
		// 좋은 구간이 될 수 있는 범위.
		// - good : 집합 원소를 기준으로 좋은 구간이 될 수 있는 범위를 담을 우선순위큐.
		PriorityQueue<GoodNum> good = new PriorityQueue<>();

		// 집합 입력.
		// - list : 집합의 원소를 저장할 리스트.
		st = new StringTokenizer(in.readLine());
		List<Integer> list = new ArrayList<>();	
		for(int i = 0; i < L; i++) {
			int temp = Integer.parseInt(st.nextToken());
			list.add(temp);
			// 집합의 값을 좋은 구간으로 추가.
			good.offer(new GoodNum(temp, temp, 0, 0));
		}
			
		
		int n = Integer.parseInt(in.readLine());
		
		// 집합 원소 정렬.
		Collections.sort(list);

		// left, right : 좋은 구간이 될 수 있는 범위.
		// - (left-1) == 0 또는 집합의 값.
		// - (right+1) == 집합의 값.
		int left = 1;
		int right = Integer.MAX_VALUE;
		for(int i = 0; i < L; i++) {
			if (left == list.get(i)) {
				left = list.get(i) + 1;
				continue;
			}
			right = list.get(i)-1;
			good.offer(new GoodNum(left, right, 0, right - left));
			left = right+2;
		}
		
		// 1. 우선순위 큐를 사용해 차례로 출력.
		while(!good.isEmpty() && n > 0) {	
			// 최소 좋은 구간을 가지는 범위 반환.
			GoodNum cur = good.poll();
			// idx를 이용해 왼쪽, 오른쪽 수 확인.
			int curLeft = cur.left + cur.idx;
			int curRight = cur.right - cur.idx;
			
			// 왼쪽은 무조건 출력.
			sb.append(curLeft).append(" ");
			n--;
			
			// 모든 수를 출력했다면 종료.
			if (n <= 0) break;
			
			
			// 같은 수가 출력되면 안되므로 같은 수가 아닐 때만 오른쪽 출력.
			if(curLeft != curRight) {
				sb.append(curRight).append(" ");
				n--;
			}
			
			// 범위의 모든 수를 출력했다면 해당 범위 제거.
			if(curLeft == curRight || (curLeft+1) == curRight)
				continue;

			// [새로운 인덱스, 좋은 구간의 수] 계산 및 추가.
			int newIdx = cur.idx+1;
			int newCount = (newIdx+1)*(cur.right - (cur.left+newIdx)) + newIdx; 
			good.offer(new GoodNum(cur.left, cur.right, newIdx, newCount));
		}
		
		// 2. 상위 n개를 출력하지 못했다면 [집합의 최대값 + 1]부터 차례로 출력.
		for(int v = list.get(L-1)+1; n > 0; n--) {
			sb.append(v++).append(" ");
		}
		
		System.out.println(sb);
	}
}