[백준] 25556 : 포스택 (Python)

 

출처 : https://www.acmicpc.net/problem/25556

 

 

---

 

아이디어

이번 문제는 스택 유형이다. 요구사항을 바탕으로 다음과 같은 핵심 연산을 떠올렸다.

'순열 A의 현재 원소를 4개의 스택 중 어디에 넣어야 하는가?'

이에 대한 해답은 예제 입력 케이스들과 함께 발견할 수 있었다. 함께 자세히 알아보자.

 

예제 1번 케이스 시각화(삽입 과정)

위의 사진은 예제 입력 1번 케이스의 삽입 과정을 시각화한 것이다. 먼저 초록색 원 부분을 살펴보자.

만약, 4가 존재하는 1번 스택에 3(현재 순열 A의 원소)을 삽입하게 된다면, 4를 절대로 꺼낼 수 없게 된다. 즉, 스택에 원소가 존재한다면, 넣으려는 수 > stack[i][-1] 일때만, 삽입이 가능하다는 의미이다. 이를 스택 삽입 조건 1로 정리할 수 있다.

만약, 삽입 불가능하다면, 그 다음 스택과 비교를 하면 될 것이고, 유형은 다음 2가지로 나뉜다.

• 원소가 존재하는 다음 스택 -> 다시 비교 -> ... -> 마지막 스택(4번 스택)도 안되면, 순열 청소 불가능 정답 처리.
• 원소가 존재하지 않는 다음 스택(공백 상태) -> 바로 삽입 가능.

 

그렇다면, 파란색 박스 부분을 살펴보자. 이 경우는 여러 스택에 원소가 존재하는 경우를 의미한다. 4개의 스택 모두가 조건 1을 만족하는 경우는 어떻게 해야할까?

이는 Greedy 탐욕법으로 해결할 수 있다. 다음의 상황을 생각해보자.

• ex) 스택1: [6], 스택2: [], 넣으려는 수: 7
• (1) 스택1에 삽입 ==> [6,7]
• (2) 스택2에 삽입 ==> [7]

이 경우를 살펴보면, 넣으려는 수와 스택의 마지막 수와의 차이가 최소일수록 편하게 청소할 수 있음을 알 수 있다. 즉, 넣으려는 수와 마지막 수와의 차이가 최소인 스택을 선택한다는 탐욕적인 방식으로 해결할 수 있다.

 

전부 정리해보자면, 이 문제의 핵심은 '어떤 스택에 삽입해야하는가'이고, 삽입의 조건은 다음 2가지로 정의할 수 있다.

1. 삽입 대상의 스택은 공백이거나, 마지막 원소인 stack[i]-1보다 커야한다.
2. 그러한 스택이 여러개 일때, 마지막 원소와의 차이값이 최소인 스택을 선택한다.
3. 그럼에도 불구하고, 모든 스택(4개)에 삽입 불가능하다면, No로 정답을 처리한다.

이를 바탕으로, 프로그램을 설계하면 문제를 해결할 수 있다.

 

정답 코드

# https://www.acmicpc.net/problem/25556
# 포스텍
# 스택, 그리디

input=__import__('sys').stdin.readline

n=int(input())
stacks=[[] for _ in range(4)]
A=[*map(int,input().split())]

stacks[0].append(A[0]) # 초기값 설정
for i in range(1,n):
    cur=A[i] # 현재 타겟 넘버
    flag,idx,value=False,0,200000 # 삽입후보존재여부,후보스택인덱스,해당값
    for j in range(4):
        ## 해당 스택이 공백이 아니고
        if stacks[j]: 
            # 현재 타겟이 해당 스택 마지막값보다 크고,
            # (타겟-스택마지막값)이 기존 후보의 차이값보다 작은 경우
            if cur>stacks[j][-1] and cur-stacks[j][-1]<value:
                flag=True
                idx,value=j,cur-stacks[j][-1] # 후보 갱신
        ## 이전 스택의 후보에 선정되지 못해서 이번 스택 공백에 넣어야 하는 경우
        elif not flag:
            stacks[j].append(cur)
            break
    # 후보 존재할 경우
    if flag:
        stacks[idx].append(cur)

answer=False
cur_target=n
while cur_target>=1:
    flag=False
    for i in range(4):
        if stacks[i] and stacks[i][-1]==cur_target:
            flag=True
            stacks[i].pop()
            break
    if not flag:
        answer=True
        break
    cur_target-=1

print("YNEOS"[answer::2])