[ICPC 예선 "연습" Upsolve] 20337 - Incomplete Sort

 이번 주에 치르게된 ICPC 예선! (물론 단순히 경험삼아서 나간다 본선 진출은 지금 실력으로 어림도 없다) 그 예선에 대비하고자 이번에 선배님 한분(swoon님)과 함께 연습을 하게 되었다. 거기거 내가 푼, 정확히는 아이디어 만을 제공한 하나의 문제를 여기에 적고자 한다. 막간을 이용해서 후기도 적을 건데, 사실 할 말이야 뻔할 지도 모르겠다.

 

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

20337번: Incomplete Sort

 

 이 문제의 대략적인 해석은 이렇다. 4n(n은 자연수) 길이를 가진 1 ~ 4n까지의 모든 자연수를 포함한(그러니 중복되는 element는 없다, 순서는 무작위) 리스트가 있다. 여기서 3번의 sort 기회를 얻는다. 중요한 것은 index 몇 부터 몇을 sort하는 것이 아니라, 정확히 2n(리스트의 절반)개의 index를 골라서, 거기에 있는 숫자들을 sort해버린 후 다시 2n개를 뽑아왔던 index들에 그 순서대로 끼워 넣는 식의 sort라는 것이다.

 리스트의 길이와 리스트의 구성이 주어질 때, 이 sort 기능을 이용할 횟수와 그 횟수에 따라 각각 리스트 전체를 sort할 수 있는 2n개의 index를 출력해라.

 

 대략 이런 문제다. 중간에 설명이 잘못됐을지도? 아무튼 나는 이 문제를 가지고 코딩을 할 수가 읎었다... 3시간 안에 내 역량으로써는 불가능이었겠다만... 다행히 swoon님이 구현력으로 전부 밀어주셨다!(역시 다5의 힘은 데다네!)

 

 처음에 예제를 분석하다가, 앞에 조그만 부분을 먼저 sort할 수 있다면 점진적으로 모든 부분을 sort할 수 있지 않을까? 하는 생각이 들었다. 왜 문제는 하필이면 4로 나누어지는 n을 주었을까? 분명 이유가 있을 것 같은데.. 라는 생각이 들었고, 그러다가 리스트에 1/4을 확정적으로 sort해버릴 수 있는 방법을 찾았다.

 

 8까지의 자연수 리스트를 생각해 보자. 만약 1, 2가 있는 인덱스를 포함한 채로 첫번째와 두번째 인덱스를 소팅하면 어떻게 될까? 첫번째와 두번째 인덱스가 뭐였든 간데, 1과 2가 첫번째와 두번째 인덱스에 들어 갈 수 밖에 없다. 걔네가 모든 list에서 가장 작기 때문이다.

 그 다음으로 3, 4에 대해서도 비슷한 일을 한다. 그럼 이미 리스트가 1, 2, 3, 4, X, X, X, X형태가 된다. 나머지 인덱스는 단순히 n / 2 ~ n까지를 고르는 것으로 모든 list를 소트할 수 있다!

 나중에 집에 돌아와서 보니까 내 아이디어인데 코드도 못짜면 서러울 것 같아서 다시 짜본 결과가 이거다.

n = int(input())
nums = []

for st_i in input().split(' '):
    nums.append(int(st_i))

print("3")
temp_num = []
temp_index = []
for i in range(n // 4):
    temp_num.append(nums[i])
    temp_index.append(i)

for i in range(1, n // 4 + 1):
    if i not in temp_num:
        temp_num.append(i)
        temp_index.append(nums.index(i))

i = n // 4
while len(temp_num) < n // 2:
    if nums[i] not in temp_num:
        temp_num.append(nums[i])
        temp_index.append(i)
    i += 1

temp_num.sort()
temp_index.sort()

for out in temp_index:
    print(out + 1, end=' ')
print()

for i in range(n // 2):
    nums[temp_index[i]] = temp_num[i]
#cycle 1

temp_num.clear()
temp_index.clear()
for i in range(n // 4, n // 2):
    temp_num.append(nums[i])
    temp_index.append(i)

for i in range(n // 4 + 1, n // 2 + 1):
    if i not in temp_num:
        temp_num.append(i)
        temp_index.append(nums.index(i))

i = n // 2
while len(temp_num) < n // 2:
    if nums[i] not in temp_num:
        temp_num.append(nums[i])
        temp_index.append(i)
    i += 1

temp_num.sort()

for out in temp_index:
    print(out + 1, end=' ')
print()
#cycle 2

XXX
#cycle 3(just sort rest of them...)

(XXX는 단순히 검열 처리이다. 코드 복붙러들 방지용인데, 만약 문제를 이해했다면 내가 지워버린 부분을 바로 메꿀 수 있을 것이다.)

 

 처음에는 저 위에서 temp_num을 sort한 결과를 내보냈는데 그게 아니라 temp_index를 sort한 걸 내보내라는 거였다... 거 때문에 swoon님도 그거 고치느냐고 1트를 날렸다 ㅠ 제대로 해석했어야했는데;; 아무튼 이 팀에 어떻게 기여하면 좋을지 좀 감을 잡은 것 같아서 연습하기 잘했다는 생각이 든다. (구현력 제일 좋은 사람이 컴퓨터를 붙들고 있기 마련이기 때문에, 아이디어를 팍팍! 내면 된다. 아님 영어 해석에 주력해도 좋을 것 같다.)