[백준 1071] 소트 (python)

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

1071번: 소트

소트 문제

A[i] + 1 ≠ A[i+1]을 만족하도록 재정렬했을 때 사전 순으로 앞서는 경우를 출력하는 문제

 

# 사용 알고리즘

그리디

 

📌문제 접근 포인트

1. 요구 조건에 대해서 생각해보자. A[i] +1 ≠ A[i+1] 을 만족할 수 있게 가장 쉽게 접근하려면 카운팅 배열을 사용하면 유리하다. 카운팅 배열을 구성해보자.

2. 카운팅 배열을 만들었으면, A[i] +1 ≠ A[i+1]는 카운팅 배열에선 각 요소가 1씩 차이나므로 A[i] 와 A[i+1]을 의미한다. 요구 조건에 의해 둘이 함께 있어지면 안되므로, A[i]와 A[i+1]이 존재할때 A[i+2]부터 탐색해서 A에 존재하는 가장 작은 수 A[x]를 찾아보자.

3. A[x]가 존재한다면, 사전 순으로 정렬해야 한다는 조건에 의해 A[i]번 만큼 i 값을 전부 결과 값에 넣어준 뒤,  그 다음 가장 작은 수 A[x]를 넣어주자.

4. 만약 A[x]가 존재하지 않는 경우라면 사전 순으로 배열하기 위해서는 A[i+1]를 전부 먼저 결과에 넣고, 그 다음 A[i]를 전부 결과에 넣으면 사전 순으로, A[i] +1 ≠ A[i+1]를 만족하며 넣을 수 있게 된다.

5. 2번의 조건에서 A[i]와 A[i+1]이 연속적으로 존재하는게 아니면 해당 A[i] 값을 그냥 바로 다 결과 값에 넣어주도록 구성하면 성공

⚙ 내가 푼 정답 코드

import sys
N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
# 카운팅 배열 만들기
A = [0]*1003 
for i in num:  
    A[i] += 1

result = []
i = 0
while sum(A) > 0: # 카운팅 배열이 빌 때 까지
    flag = 1
    if A[i] and A[i+1]: # 현재 값과 다음 값이 존재하면
        for x in range(i+2,1001): # 다음 값은 건너 뛰어야하니 i+2부터
            if A[x]: # 값이 존재하면
                result += [i] * A[i] # 현재 i값에 해당하는 것 전부 결과에 넣고
                A[i] = 0 # 다 넣었으니 0으로 초기화
                result.append(x) # x값 넣어주기
                A[x] -= 1 # x값 넣었으니 하나 빼주기
                flag = 0
                break # 끝내!

        if flag : # 위 for문 다 통과해도 없으면
            result += [i+1]*A[i+1] # 이제 i+1칸에 해당하는 값을 전부 밀어넣고
            A[i+1] = 0 # 0으로 초기화하고
            result += [i]*A[i] # i칸에 해당하는 값을 전부 밀어 넣고
            A[i] = 0 # 0으로 초기화

    else : # 바로 직 후 값 존재 안하면
        result += [i] * A[i] # 해당 i 값 전부 넣어버리기
        A[i] = 0
    i += 1
print(*result)