Daily Algorithm - Day 30

105·2025년 1월 20일

algorithm python

입력

출력

예제 1

예제 2

Daily Algorithm

목록 보기

31/34

포스택

포닉스는 길이가 $N$ 인 순열 $A$ 와 네 개의 비어 있는 스택을 가지고 있다.

길이가 $N$ 인 순열이란, $1$ 이상 $N$ 이하의 서로 다른 정수 $N$ 개가 임의로 나열된 수열을 말한다.

스택이란 자료구조의 한 종류로 가장 나중에 삽입한 자료가 가장 먼저 나오는 후입선출 (Last In First Out, LIFO)의 특성을 가지고 있다.

포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다.
순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 즉 순열을 $1, 2, 3, \cdots N$ 으로 만들어야 한다.

1. 순열 $A$ 의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
2. 순열 $A$ 의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
3. 꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.

포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자.

입력

첫째 줄에 순열의 길이 $N$ 이 주어진다. $(1 ≤ N ≤ 100\,000)$

둘째 줄에 순열 $A$ 의 원소 $A_i$ 가 공백으로 구분되어 주어진다. 모든 $A_i$ 는 $1$ 이상 $N$ 이하의 서로 다른 정수임이 보장된다.

출력

포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다.

예제 1

//입력
10
4 3 6 7 8 9 10 2 1 5

//출력
YES

예제 2

//입력
5
5 4 3 2 1

//출력
NO

우선 입력 범위가 보장이 되는데 굳이 행렬의 길이를 입력값으로 줄 필요가 있는가? 에 대한 의문은 있지만 코드를 읽는 사람을 위한 배려라고 생각하자.

스택이 여러개일 때 삽입하려는 숫자의 최솟값이 갱신될 때 마다 새 스택을 사용하면 모든 순열을 정리할 수 있다.
다만 이번에는 스택이 4개로 제한되었으니 최솟값 갱신이 4번 이상 발생한다면 정리가 불가능해진다. 이를 이용해서 구현해보자.

def can_clean_sequence(n, a):
    if (n != len(a)):
        return "길이가 맞지 않습니다."
    
    min_value = a[0]
    count = 0
    
    for number in a:
        if number < min_value:
            min_value = number
            count += 1
    if count < 4:
        return "YES"
    else:
        return "NO"

# 입력
n = int(input())
a = list(map(int, input().split()))

# 결과 출력
print(can_clean_sequence(n, a))   #pass

그럼 gpt 선생님에게 리뷰를 받아보자.

개선된 코드

def can_clean_sequence(n, a):
    stacks = [[] for _ in range(4)]  # 네 개의 빈 스택
    
    for number in a:
        placed = False
        for stack in stacks:
            if not stack or stack[-1] <= number:
                stack.append(number)
                placed = True
                break
        if not placed:
            return "NO"
    
    # 스택에서 정렬된 순서대로 꺼내기
    result = []
    for stack in stacks:
        result.extend(reversed(stack))
    
    # 결과가 1부터 N까지 오름차순인지 확인
    if result == sorted(result):
        return "YES"
    return "NO"

# 입력
n = int(input())
a = list(map(int, input().split()))

# 결과 출력
print(can_clean_sequence(n, a))