[Python] 1071 소트

문제

N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 N개의 수가 주어진다. N개의 수는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 문제의 정답을 출력한다.

문제 풀이

A. 접근

권국원님의 「보통의 취준생을 위한 코딩 테스트 with 파이썬」을 참고하여 작성함

이틀 동안 고민했는데 못 풀었다. 다양한 접근을 생각해야 하는데 뭔가 하나에 꽂히면 그곳에 집중하여 다른 풀이를 생각하지 못한다 ㅠㅠ
문제의 핵심은 연속된 값이 아니게 정렬하는 프로그램을 작성하는 것이다. 또한, 사전순으로 가장 앞서는 것을 출력하도록 한다.

예를 들어,

3
1 2 3

이러한 입력이 주어졌을 때는

1 3 2

이렇게 연속되지 않으며 사전순으로 가장 앞서게 출력할 수 있다.

또한,

9
1 1 1 1 2 2 2 2 2

이러한 입력이 주어졌을 때,

2 2 2 2 2 1 1 1 1

이렇게 출력해야 한다.

조금 더 예제 입력을 분석해보자.

6
1 2 3 4 5 6

은

1 3 2 4 6 5

이렇게 출력이 된다.
그리고

6
1 1 2 2 3 3

은

1 1 3 3 2 2

이런 식으로 출력이 된다.

출력을 보면서 규칙을 파악해 보자면, a[i]과 a[i] + 1, a[i] + 2가 존재할 때는 항상 a[i] 뒤에 a[i] + 2가 붙어있다.
하지만, a[i]와 a[i] + 1이 존재할 때는 a[i] + 1이 모두 출력이 되어야 a[i]가 출력이 된다.

즉, 조건을 조금 더 명확히 표현하면 다음과 같다.

1. a[i] + 1을 만족하는 수가 있다.
   1. a[i] + 2 이상을 만족하는 수가 있다면, a[i]를 모두 출력한 다음 a[i] + 2를 한 번 출력한다.
   2. 그렇지 않다면, a[i] + 1을 출력한다.
2. 그렇지 않다면 a[i]를 모두 출력한다.

1-1에서 a[i] + 2를 한 번 출력한 이유는 사전순으로 가장 앞서는 수를 찾기 위해서다. 이는 1-2도 동일하다. 사실 2번도 동일한 이유이다. 골드 1 문제라고 해도 사실 분석만 잘 하면 풀 수 있는데 너무 티어를 보고 쫄지 말자!

B. 문제 풀이

전체 코드

n = int(input())

cnt_sort = [0 for i in range(1002)]

arr = [int(i) for i in input().split()]
for i in range(n):
    cnt_sort[arr[i]] += 1

ans = ''

while True:
    switch = False
    for i in range(1001):
        if cnt_sort[i]:
            switch = True
            if cnt_sort[i + 1]:
                k = -1
                for j in range(i + 2, 1001):
                    if cnt_sort[j]:
                        k = j
                        break
                if k != -1:
                    while cnt_sort[i]:
                        ans += str(i) + ' '
                        cnt_sort[i] -= 1
                    ans += str(k) + ' '
                    cnt_sort[k] -= 1
                    break
                else:
                    ans += str(i + 1) + ' '
                    cnt_sort[i + 1] -= 1
                    break
            else:
                while cnt_sort[i]:
                    ans += str(i) + ' '
                    cnt_sort[i] -= 1
                break
    if switch == False:
        break

print(ans)

B-1. 준비

n = int(input())

cnt_sort = [0 for i in range(1002)]

arr = [int(i) for i in input().split()]
for i in range(n):
    cnt_sort[arr[i]] += 1

ans = ''

이번에는 계수 정렬을 사용한다. 같은 수가 계속해서 나오고 수의 개수도 1000개 이하라서 쓰기에 무리가 없다. 그래서 cnt_sort라는 변수를 만들었고, for문으로 각 수의 등장 횟수를 저장한다.

B-2. 풀이

while True:
    switch = False
    for i in range(1001):
        if cnt_sort[i]:
            switch = True
            if cnt_sort[i + 1]:
                k = -1
                for j in range(i + 2, 1001):
                    if cnt_sort[j]:
                        k = j
                        break
                if k != -1:
                    while cnt_sort[i]:
                        ans += str(i) + ' '
                        cnt_sort[i] -= 1
                    ans += str(k) + ' '
                    cnt_sort[k] -= 1
                    break
                else:
                    ans += str(i + 1) + ' '
                    cnt_sort[i + 1] -= 1
                    break
            else:
                while cnt_sort[i]:
                    ans += str(i) + ' '
                    cnt_sort[i] -= 1
                break
    if switch == False:
        break

print(ans)

먼저 while 문의 반복 조건을 설정하기 위해 switch 변수를 만들었다. for문으로 1부터 1000까지 순회한다. 다 순회했는데 값이 없다면 정렬이 종료된 것이므로 while 반복을 종료한다.

--------if cnt_sort[i + 1]:
                k = -1
                for j in range(i + 2, 1001):
                    if cnt_sort[j]:
                        k = j
                        break
                if k != -1:
                    while cnt_sort[i]:
                        ans += str(i) + ' '
                        cnt_sort[i] -= 1
                    ans += str(k) + ' '
                    cnt_sort[k] -= 1
                    break
                else:
                    ans += str(i + 1) + ' '
                    cnt_sort[i + 1] -= 1
                    break

만약 i + 1 값이 있다고 할 때의 조건을 구현하였다.

k는 i + 2 값이 있는지 확인하기 위해 설정한 변수이다.
i + 2부터 1000까지 순회하면서 값이 있는지 파악한다. 만약 값이 있다면 그 값이 a[i] 다음에 와야 한다. 그래서 k에 값을 저장한다.

그렇게 하여 k에 값이 있다면(i + 2 이상의 값이 존재한다면) i 값을 모두 ans에 출력 형식에 맞춰 저장하고 카운팅을 1씩 뺀다. 그 이후에 a[k] 값도 ans에 붙이고 카운팅을 1 뺀다.

k에 값이 없다면 i + 1이 먼저 출력되어야 하므로 ans에 i + 1 값을 붙이고 카운팅을 1 뺀다.

------------else:
                while cnt_sort[i]:
                    ans += str(i) + ' '
                    cnt_sort[i] -= 1
                break
    if switch == False:
        break

print(ans)

i + 1이 없다면 i값을 모두 출력하도록 한다. 왜냐하면 사전순으로 가장 앞서는 값을 출력하기 위해서다.

총평

그리디를 조금 더 풀어볼 필요가 있다. 화이팅