[백준 24337] 가희와 탑 (JAVA)

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

24337번: 가희와 탑

 

구현 문제로, 풀이법을 생각해내기 꽤 어려운 문제였다...

 

1. 건물의 최고 높이는 a와 b중 큰 값이다.

2. 디큐를 생성하여 a-1만큼의 오름 차순 + 최고 높이 건물 + b-1만큼의 내림차순으로 먼저 add 한다!

3. 다 add 한 후에 디큐 사이즈가 n보다 크다면, 건물 정보가 나올 수 없는 것이기에 -1을 출력한다!!

4. 여기까지 진행하면 아래와 같은 경우가 발생된다.

입력

9 1 5 -> 5 4 3 2 1

3 1 2 -> 2 1             

이러면 건물의 개수가 맞지 않기 떄문에, 가장 낮은 건물의 높이인 1을 앞쪽에 추가하여 개수를 맞춘다!

주의 할 점은 앞에서 보이는 건물의 수가 달라지지 않도록 해야하기에,

기존 디큐의 가장 앞에 있는 값을 poll하여 따로 저장해 논 후,  나중에 다시 addFirst()한다!!

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

	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 a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		int maxHeight=Math.max(a, b); //건물 최고 높이
		Deque<Integer> q = new LinkedList<>();
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i < a; i++) {
			q.add(i);
		}
		q.add(maxHeight);
		for (int i = b - 1; i > 0; i--) {
			q.add(i);
		}

		if(q.size()>n) {
			System.out.println(-1);
			return;
		}
		
		//건물 갯수 맞추기
		int first = q.pollFirst();
		int qSize = q.size();
		for(int i=1;i<=n-qSize-1;i++) {
			q.addFirst(1);
		}
		q.addFirst(first);
		for (int i = 1; i <= n; i++) {
			System.out.print(q.pollFirst() + " ");
		}

	}

}