백준 온라인 저지, 그리디 / 20311번: 화학실험 (파이썬 / , 백준 골드문제)

문제

화학 실험을 하던 윤이는 일렬로 나열해 놓은 $N$개의 시험관에서 재밌는 특징을 발견했다. 그 특징은 모든 이웃한 시험관 쌍에 대해, 두 시험관에 들어 있는 시약의 색깔이 서로 다르다는 점이었다. 흥미롭다고 느낀 윤이는 실험보고서에 이 사실과 함께 각 색깔별 시약의 수를 적었다. 하지만 보고서를 채점하던 조교 원이는 윤이가 색깔별 시약의 수를 제대로 적었는지 의문이 들었다. 윤이의 보고서와 일치하도록 시험관을 배열할 수 있는지 판별하는 프로그램을 작성하시오.

입력

첫 번째 줄에 시험관의 개수 $N$과 색깔의 종류 수 $K$가 공백을 사이에 두고 주어진다.

두 번째 줄에 $K$개의 양의 정수 $c_i$가 공백을 사이에 두고 주어진다. 각 색깔에는 번호가 붙어 있으며, $c_i$는 $i$번 색깔의 시약이 담긴 시험관의 개수이다. $(1≤i≤K)$

출력

조건을 만족하는 시험관 배열을 만들 수 있으면, 시험관의 색깔 번호를 공백으로 구분하여 순서대로 출력한다. 답이 여러 개이면 아무 거나 출력한다.

조건을 만족하는 시험관 배열을 만들 수 없으면 $-1$을 출력한다.

제한

$1 ≤ K ≤ N ≤ 300,000$

$c_1, \cdots, c_k > 0$

$c_1+\cdots+c_k = N$

서브태스크 1 (40점)

$i≥2$에 대해 $c_i=1$

서브태스크 2 (60점)

추가적인 제약 조건이 없다.

예제 입력 1

6 3
3 1 2

예제 출력 1

1 2 3 1 3 1

이 입력은 서브태스크 1의 조건을 만족하지 않는다.

예제 입력 2

6 3
4 1 1

예제 출력 2

-1

힌트

W3sicHJvYmxlbV9pZCI6IjIwMzExIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNjU0XHVkNTU5IFx1YzJlNFx1ZDVkOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNjU0XHVkNTU5IFx1YzJlNFx1ZDVkOFx1Yzc0NCBcdWQ1NThcdWIzNTggXHVjNzI0XHVjNzc0XHViMjk0IFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWIwOThcdWM1ZjRcdWQ1NzQgXHViMTkzXHVjNzQwICROJFx1YWMxY1x1Yzc1OCBcdWMyZGNcdWQ1ZDhcdWFkMDBcdWM1ZDBcdWMxMWMgXHVjN2FjXHViYzBjXHViMjk0IFx1ZDJiOVx1YzlkNVx1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1YWRmOCBcdWQyYjlcdWM5ZDVcdWM3NDAgXHViYWE4XHViNGUwIFx1Yzc3NFx1YzZjM1x1ZDU1YyBcdWMyZGNcdWQ1ZDhcdWFkMDAgXHVjMzBkXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHViNDUwIFx1YzJkY1x1ZDVkOFx1YWQwMFx1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YzJkY1x1YzU3ZFx1Yzc1OCBcdWMwYzlcdWFlNTRcdWM3NzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNFx1YjI5NCBcdWM4MTBcdWM3NzRcdWM1YzhcdWIyZTQuIFx1ZDc2NVx1YmJmOFx1Yjg2ZFx1YjJlNFx1YWNlMCBcdWIyOTBcdWIwODAgXHVjNzI0XHVjNzc0XHViMjk0IFx1YzJlNFx1ZDVkOFx1YmNmNFx1YWNlMFx1YzExY1x1YzVkMCBcdWM3NzQgXHVjMGFjXHVjMmU0XHVhY2ZjIFx1ZDU2OFx1YWVkOCBcdWFjMDEgXHVjMGM5XHVhZTU0XHViY2M0IFx1YzJkY1x1YzU3ZFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjODAxXHVjNWM4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHViY2Y0XHVhY2UwXHVjMTFjXHViOTdjIFx1Y2M0NFx1YzgxMFx1ZDU1OFx1YjM1OCBcdWM4NzBcdWFkNTAgXHVjNmQwXHVjNzc0XHViMjk0IFx1YzcyNFx1Yzc3NFx1YWMwMCBcdWMwYzlcdWFlNTRcdWJjYzQgXHVjMmRjXHVjNTdkXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWM4MWNcdWIzMDBcdWI4NWMgXHVjODAxXHVjNWM4XHViMjk0XHVjOWMwIFx1Yzc1OFx1YmIzOFx1Yzc3NCBcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1YzcyNFx1Yzc3NFx1Yzc1OCBcdWJjZjRcdWFjZTBcdWMxMWNcdWM2NDAgXHVjNzdjXHVjZTU4XHVkNTU4XHViM2M0XHViODVkIFx1YzJkY1x1ZDVkOFx1YWQwMFx1Yzc0NCBcdWJjMzBcdWM1ZjRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWQzMTBcdWJjYzRcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJkY1x1ZDVkOFx1YWQwMFx1Yzc1OCBcdWFjMWNcdWMyMTggJE4kXHVhY2ZjIFx1YzBjOVx1YWU1NFx1Yzc1OCBcdWM4ODVcdWI5NTggXHVjMjE4ICRLJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwICRLJFx1YWMxY1x1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4ICRjX2kkXHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzBjOVx1YWU1NFx1YzVkMFx1YjI5NCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgJGNfaSRcdWIyOTQgJGkkXHViYzg4IFx1YzBjOVx1YWU1NFx1Yzc1OCBcdWMyZGNcdWM1N2RcdWM3NzQgXHViMmY0XHVhZTM0IFx1YzJkY1x1ZDVkOFx1YWQwMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuICQoMSZsZTtpJmxlO0spJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMmRjXHVkNWQ4XHVhZDAwIFx1YmMzMFx1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCwgXHVjMmRjXHVkNWQ4XHVhZDAwXHVjNzU4IFx1YzBjOVx1YWU1NCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc3NFx1YmE3NCBcdWM1NDRcdWJiMzQgXHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyZGNcdWQ1ZDhcdWFkMDAgXHViYzMwXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHVjNzNjXHViYTc0ICQtMSRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHA+JDEgJmxlOyBLICZsZTsgTiAmbGU7IDMwMCwwMDAkPFwvcD5cclxuXHJcbjxwPiRjXzEsIFxcY2RvdHMsIGNfayAmZ3Q7IDAkPFwvcD5cclxuXHJcbjxwPiRjXzErXFxjZG90cytjX2sgPSBOJDxcL3A+XHJcbiIsInN1YnRhc2sxIjoiPHA+JGkmZ2U7MiRcdWM1ZDAgXHViMzAwXHVkNTc0ICRjX2k9MSQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPlx1Y2Q5NFx1YWMwMFx1YzgwMVx1Yzc3OCBcdWM4MWNcdWM1N2QgXHVjODcwXHVhYzc0XHVjNzc0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+XHVjNzc0IFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWMxMWNcdWJlMGNcdWQwZGNcdWMyYTRcdWQwNmMgMVx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIyMDMxMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNoZW1pc3RyeSBFeHBlcmltZW50IiwiZGVzY3JpcHRpb24iOiI8cD5EdXJpbmcgYSBjaGVtaXN0cnkgZXhwZXJpbWVudCwgWXVuZWUgZm91bmQgYW4gaW50ZXJlc3RpbmcgZmVhdHVyZSZuYnNwO2luIHRoZSAkTiQgdGVzdCB0dWJlcyBhcnJhbmdlZCBpbiBhIGxpbmU6Jm5ic3A7Zm9yIGV2ZXJ5Jm5ic3A7cGFpciBvZiBhZGphY2VudCB0ZXN0IHR1YmVzLCB0aGUgcmVhZ2VudHMgaW4gdGhlIHR3byB0dWJlcyBoYWQgZGlmZmVyZW50IGNvbG9ycy4gWXVuZWUgZ290Jm5ic3A7aW50cmlndWVkJm5ic3A7YW5kJm5ic3A7d3JvdGUgYWJvdXQgdGhpcyZuYnNwO2ZlYXR1cmUmbmJzcDthbG9uZyB3aXRoJm5ic3A7dGhlIG51bWJlciBvZiB0ZXN0IHR1YmVzJm5ic3A7Zm9yIGVhY2ggY29sb3IgaW4gdGhlIGV4cGVyaW1lbnQgcmVwb3J0LiZuYnNwO0hvd2V2ZXIsIHRoZSB0ZWFjaGluZyBhc3Npc3RhbnQmbmJzcDtXb25lZSwgd2hvIHdhcyBzY29yaW5nIHRoZSByZXBvcnQsJm5ic3A7d29uZGVyZWQgd2hldGhlciBZdW5lZSBjb3JyZWN0bHkgd3JvdGUgZG93biB0aGUgbnVtYmVyIG9mIHJlYWdlbnRzJm5ic3A7Zm9yIGVhY2ggY29sb3IuIFdyaXRlIGEgcHJvZ3JhbSB0byBkZXRlcm1pbmUgaWYgdGhlIHRlc3QgdHViZXMgY2FuIGJlIGFycmFuZ2VkIGFzIHJlY29yZGVkIGJ5IFl1bmVlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUsIHRoZSBudW1iZXIgb2YgdGVzdCB0dWJlcyAkTiQgYW5kIHRoZSBudW1iZXIgb2YgY29sb3JzICRLJCBhcmUgZ2l2ZW4sIHNlcGFyYXRlZCBieSBhIHdoaXRlc3BhY2UuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBzZWNvbmQgbGluZSwgJEskIHBvc2l0aXZlIGludGVnZXJzICRjX2kkIGFyZSBnaXZlbiwgc2VwYXJhdGVkIGJ5IHdoaXRlc3BhY2VzLiBFYWNoIGNvbG9yIGlzIHJlcHJlc2VudGVkIGJ5IGFuIGludGVnZXIgZnJvbSAkMSQgdG8gJEskLiZuYnNwOyRjX2kkIGlzIHRoZSBudW1iZXIgb2YgdGVzdCB0dWJlcyB0aGF0IGNvbnRhaW4gdGhlIHJlYWdlbnQgd2l0aCBhIGNvbG9yICRpJC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JZiB0aGVyZSBleGlzdHMgYW4gYXJyYW5nZW1lbnQgb2YgdGVzdCB0dWJlcyB0aGF0IHNhdGlzZmllcyB0aGUgY29uZGl0aW9uLCBvdXRwdXQgdGhlIGNvbG9ycyZuYnNwO29mIHRoZSByZWFnZW50cyBpbiB0aGUgdGVzdCB0dWJlcyBpbiBvcmRlci4gSWYgdGhlcmUgYXJlIHNldmVyYWwgcG9zc2libGUgYXJyYW5nZW1lbnRzLCBvdXRwdXQgYW55IG9mIHRoZW0uPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGRvZXMgbm90IGV4aXN0IHN1Y2ggYW4gYXJyYW5nZW1lbnQsIG91dHB1dCAkLTEkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6IjxwPiQxICZsZTsgSyAmbGU7IE4gJmxlOyAzMDAsMDAwJDxcL3A+XHJcblxyXG48cD4kY18xLCBcXGNkb3RzLCBjX2sgJmd0OyAwJDxcL3A+XHJcblxyXG48cD4kY18xK1xcY2RvdHMrY19rID0gTiQ8XC9wPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiRjX2k9MSQgZm9yIGVhY2ggJGkmZ2U7MiQuPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD5ObyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5Ob3RlIHRoYXQgdGhpcyBzYW1wbGUgZGF0YSBkb2VzIG5vdCBzYXRpc2Z5IHRoZSBjb25kaXRpb24gZm9yIHN1YnRhc2sgMS48XC9wPlxyXG4ifV0=

접근 방법

- 0. 각 시험관의 개수를 최대 힙에 저장한 뒤, 이를 하나씩 빼내어주며 배열(result)에 저장한다.
- 1. 이때 값을 하나씩 빼내어 줄 때마다 다른 리스트(temp)에 저장하고, 만일 리스트에 값이 존재하는 경우 해당 값을 빼내어 최대 힙에 다시 저장한다.
- 2. 최대 힙에 값이 없거나, result에 값이 연속되는 경우 동작을 중단한다.
- 3. 만일 result에 있는 값이 연속되는 경우 -1을 출력한다.
- 4. 3번에 해당되지 않는다면 배열의 원소를 출력조건에 맞게 출력한다.

코드

# https://www.acmicpc.net/problem/20311
# 접근 방법
# 0. 각 시험관의 개수를 최대 힙에 저장한 뒤, 이를 하나씩 빼내어주며 배열(result)에 저장한다. 
# 1. 이때 값을 하나씩 빼내어 줄 때마다 다른 리스트(temp)에 저장하고, 만일 리스트에 값이 존재하는 경우 해당 값을 빼내어 최대 힙에 다시 저장한다.
# 2. 최대 힙에 값이 없거나, result에 값이 연속되는 경우 동작을 중단한다.
# 3. 만일 result에 있는 값이 연속되는 경우 -1을 출력한다.
# 4. 3번에 해당되지 않는다면 배열의 원소를 출력조건에 맞게 출력한다.
import sys, heapq
input = sys.stdin.readline
n, k = map(int, input().split())
arr = list(map(int, input().split()))
maxH = []
for i in range(k):
    heapq.heappush(maxH, [-arr[i], i])

flag = True
result = []
temp = []
while maxH:
    
    value, index = heapq.heappop(maxH)
    result.append(index+1)
    if len(result) >= 2 and result[-1] == result[-2]:
        flag = False
        break

    if temp:
        x = temp.pop()
        if x[0] < 0:
            heapq.heappush(maxH, x)    
    

    temp.append([value + 1, index])


if not flag or temp[0][0] <= -1:
    print(-1)

else:
    for x in result:
        print(x, end = ' ')