Archive / BOJ / Python

2493번 탑

이왜틀?

빠른 문제 번호… 제법 낮은 정답률…
어설픈 코드는 감히 통과하지 못할 문제다.

출력초과 받은 코드 말고 틀린 코드를 보자.

int n=Integer.parseInt(br.readLine());
StringTokenizer st=new StringTokenizer(br.readLine()," ");

int[] art=new int[n+1];
boolean[] arr=new boolean[n+1];

for(int i=1;i<=n;i++) art[i]=Integer.parseInt(st.nextToken());
int m=art[n];
int t=0;

for(int i=n;i>0;i--){
    if(art[i]>=m){
        arr[i]=true;
        m=art[i];
    }
}

StringBuilder sb=new StringBuilder();

for(int i=1;i<=n;i++){
    art[i]=t;
    if(arr[i]){
        t=i;
    }
    sb.append(art[i]+" ");
}
bw.write(sb.toString());

문제에서 스택쓰라는데 왜 안썼지

설계

스택에 손도 안 댄 과거의 내가 괘씸해서 스택으로 푼다.
왼쩍에서 오른쪽으로 탐색하며 레이저 수신 가능 여부를 판단한다.

구현

파이썬은 리스트가 pop까지 지원해서 스택 역할을 할 수 있다.
append와 pop을 사용한다.

왼쪽부터 탐색하며 수신가능한 탑을 제외하고 pop 한다.

N = int(input())

towers = list(map(int, input().split()))
stack = [] # 타워 담을 스택
result = [] # 결과 출력용

for i in range(N):
    # 스택 타워가 현재 타워보다 낮으면 수신 못해서 의미 없음
    while stack and stack[-1][1] < towers[i]:
        stack.pop()

    if not stack:
        result.append(0)
    else:
        # 수신 가능함
        result.append(stack[-1][0] + 1)

    stack.append((i, towers[i]))

print(" ".join(map(str, result)))

채점

반성

처음에 파이썬 스택은 어디있지? 컬렉션을 import 해야하나? 하고 찾다가 없다고 해서 당황했다.
그런데 리스트가 기능을 다 지원해준다.
파이썬 너는 다 계획이 있구나!

코드 확인

Link to GitHub