문제 링크
문제
티어: 골드 3
알고리즘: 그리디
입력
첫째 줄에 건물의 개수 N, 가희가 볼 수 있는 건물의 개수 a, 단비가 볼 수 있는 건물의 개수 b가 공백으로 구분해서 주어집니다.
출력
문제의 조건에 맞는 건물들의 높이 정보가 1개 이상 존재하는 경우 N개의 건물 높이 정보 중 사전순으로 가장 앞선 것을 출력해 주세요. 출력 형식은 다음을 만족해야 합니다.
-
1번 건물, ... , N번 건물의 높이를 공백으로 구분해서 출력해 주세요. 출력하는 수들이 모두 다를 필요는 없습니다.
-
높이는 1보다 크거나 같은 정수여야 합니다.
문제의 조건에 맞는 건물들의 높이 정보가 존재하지 않으면 첫 줄에 -1을 출력해 주세요.
제한
- 1 ≤ N ≤ 105
- 1 ≤ a ≤ N
- 1 ≤ b ≤ N
풀이
구하고자 하는 것은 사전 순으로 가장 앞서는 N개의 건물 높이 정보이다.
조건에 맞지 않는 건물들의 높이 정보가 존재하지 않으면 -1을 출력해야 하는데
조건에 맞지 않는다는 것은 a, b를 만족시킬 수 없다는 것이다.
먼저 a, b를 만족하려면 최소 건물의 개수가 a + b - 1 개 있어야 한다.
ex) a = 1, b = 2인 경우 2 1
그래서 (a + b - 1) > N 인 경우에는 -1를 출력한다.
그 외에 경우는 무조건 조건을 만족할 수 있다.
우리는 사전 순으로 가장 앞선 것을 출력해야 한다.
그러면 높이가 1인 건물부터 차례대로 사용해야 하고, 자릿수는 최소화해야 한다. 그러면 최대 높이는 max(a, b)가 된다.
예를 들어 a = 3, b = 5인 경우 사전 순으로 가장 앞선 건물 높이 정보는
1 2 5 4 3 2 1이다.
근데 마지막 조건인 N을 만족해야 한다. left = N - (a + b - 1) 만큼을 추가로 넣어줘야 하는데 이때도 사전 순으로 가장 앞서게끔 넣어줘야 한다.
처음 나는 그냥 맨 앞에 높이가 1인 건물을 left 개수만큼 추가해 주면 될 것 같다고 생각했다.
하지만 이 방식은 엣지 케이스를 통과하지 못한다. (a가 1인 경우)
a = 1, b = 5, N = 8인 경우
5 4 3 2 1이고, left는 3이다. 이때 앞에다 추가해 주면
1 1 1 5 4 3 2 1이 된다. 그러면 a = 2가 되어 a 조건을 만족하지 못한다.
그래서 사전 순으로 앞서게끔 하려면 앞에다 추가하는 것은 맞지만 맨 앞이 아니라는 것을 알 수 있다. 왜냐하면 맨 앞에 잉여 건물을 놓는 것은 맞춰놓은 조건을 해치기 때문이다.
그러면 우리가 원하는 것은 만족한 조건을 그대로 유지하면서 사전 순으로 앞서는 것이다.
그 위치는 0번과 1번 위치 사이에 잉여 건물을 추가하는 것이다.
5 4 3 2 1이고, left 3인 상태에서 0번과 1번 위치 사이는 높이 5 건물과 높이 4 건물 사이이기 때문에 5 1 1 1 4 3 2 1이 되고, 이 값이 a, b 조건을 만족하면서 사전 순으로 가장 앞서는 N개의 건물 높이 정보다.
그리디 알고리즘 풀이의 시간 복잡도는 O(N)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, a, b;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
if(N < (a + b - 1)) {
//최소 개수보다 적은 경우는 불가능함.
System.out.println(-1);
} else {
System.out.println(answer());
}
}
static String answer() {
int[] bulidings = new int[a + b - 1];
int rmCnt = N - (a + b - 1);
if(a >= b) {
//a가 더 큰 경우 a를 기준으로 최대 높이를 설정
for(int i=0; i<a; i++) {
bulidings[i] = i + 1;
}
for(int i=bulidings.length - 1; i >=a; i--) {
bulidings[i] = (bulidings.length) - i;
}
} else {
//b가 더 큰 경우 b를 기준으로 최대 높이를 설정
for(int i=bulidings.length - 1; i>(bulidings.length - 1) - b; i--) {
bulidings[i] = (bulidings.length) - i;
}
for(int i=0; i<=(bulidings.length - 1) - b; i++) {
bulidings[i] = i + 1;
}
}
StringBuilder sb = new StringBuilder();
for(int i=0; i<bulidings.length; i++) {
sb.append(bulidings[i]).append(" ");
if(i == 0) {
//잉여 건물 처리
for(int j=0; j<rmCnt; j++) {
sb.append("1").append(" ");
}
}
}
return sb.toString().trim();
}
}