백준 1071 : 소트

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

1071번: 소트

 

해결 방법 : Stack

• 주여진 배열을 정렬하고 작은 숫자부터 pop하여 asnwer에 담는다.
• 만약 pop해서 나온 값이 answer[-1] + 1이라면,
  
  • 만약 해당 값이 max값이라면, answer을 거꾸로 탐색하며 answer[-1]이 아닌 곳에 남은 모든 값들(모두 max일 것)을 집어 넣는다.
  • 만약 해당 값이 max가 아니라면, answer[-1] + 1 보다 큰 값이 나올때까지 wait_list에 넣는다.
    •  answer[-1] + 1 보다 큰 값이 나오면, 해당 값을 answer에 담고, wait_list를 stack에 다시 추가한다.
• stack의 숫자가 모두 pop되면 종료

 

 

import sys
input = sys.stdin.readline

def solution(N, arr):
    arr.sort(reverse=True) # 리스트 pop 연산 효율성을 위해 내림차순 정렬
    mx = arr[0] # max 값
    answer = [arr.pop()] # 가장 작은 숫자를 하나 담아놓는다.
    while len(arr) > 0: # stack이 empty state일때까지
        wait = [] # 대기 리스트

        if answer[-1] + 1 == arr[-1]: # 연속된 숫자가 나온 경우,
            if arr[-1] == mx: # 만약 현재 숫자가 max이면, 
                idx = len(answer) - 1
                while idx >= 0 and answer[idx] == answer[-1]: # 최근 max-1이 시작된 idx 찾기
                    idx -= 1
                answer = answer[:idx+1] + arr + answer[idx+1:] # 해당 idx에 삽입후 종료
                break

            else: # 현재 숫자 보다 더 큰 숫자가 있는 경우,
                while answer[-1] + 1 == arr[-1]: # 더 큰 숫자가 나올때까지 반복
                    wait.append(arr.pop())

        answer.append(arr.pop()) # 더 큰 숫자 answer에 추가
        arr += wait # 대기리스트에 있는 숫자들 다시 stack에 push

    return ' '.join([str(i) for i in answer])

if __name__ == '__main__':
    N = int(input())
    arr = list(map(int, input().split()))
    result = solution(N, arr)
    print(result)