문제 링크
문제 요약
항구에서 컨테이너를 저장하고 꺼내는 로봇의 작업 로그가 주어집니다. 컨테이너는 위로 쌓는 방식으로 저장되며, 꺼낼 때는 가장 위에 있는 컨테이너만 꺼낼 수 있습니다.
컨테이너를 저장할 때는 소문자로, 꺼낼 때는 대문자로 로그를 남깁니다.
주어진 로그가 다음 조건을 만족하는지 확인해야 합니다:
- 컨테이너를 꺼낼 때 (대문자): 저장 공간에 해당 컨테이너가 존재해야 하며, 반드시 가장 위에 있어야 합니다.
- 모든 작업이 끝난 후: 저장 공간은 비어있어야 합니다.
위 조건을 만족하면 안정적인 작동(1)이고, 그렇지 않으면 불안정한 작동(0)입니다.
풀이
이 문제는 컨테이너를 쌓고 꺼내는 과정이 가장 나중에 들어간 것이 가장 먼저 나오는 (LIFO: Last-In, First-Out) 구조임을 명확히 보여줍니다. 이는 전형적인 스택(Stack) 자료구조의 특징입니다.
따라서 주어진 로그 문자열을 순회하면서 스택을 이용하여 다음과 같이 처리합니다.
-
컨테이너 저장 (소문자): 로그 문자가 소문자(‘a’~‘z’)인 경우, 해당 컨테이너가 스택에 추가됨을 의미합니다. 스택에 해당 문자를
push합니다. -
컨테이너 꺼내기 (대문자): 로그 문자가 대문자(‘A’~‘Z’)인 경우, 스택에서 컨테이너를
pop합니다. 이때 두 가지 조건을 확인해야 합니다.- 스택이 비어있는가?: 만약 스택이 비어있는데 컨테이너를 꺼내려고 한다면, 이는 존재하지 않는 컨테이너를 꺼내는 것이므로 불안정한 작동입니다. 즉시
0을 반환합니다. - 올바른 컨테이너인가?: 스택에서
pop한 컨테이너의 종류(소문자)가 현재 로그에 있는 대문자 컨테이너의 소문자 형태와 일치하는지 확인합니다. 예를 들어, 스택에서 ‘c’를pop했는데 로그에는 ‘D’가 있다면, 잘못된 컨테이너를 꺼낸 것이므로 불안정한 작동입니다. 즉시0을 반환합니다.
- 스택이 비어있는가?: 만약 스택이 비어있는데 컨테이너를 꺼내려고 한다면, 이는 존재하지 않는 컨테이너를 꺼내는 것이므로 불안정한 작동입니다. 즉시
-
모든 로그 처리 후: 로그의 모든 문자를 처리한 후에는 스택이 비어있는지 확인해야 합니다. 만약 스택에 컨테이너가 남아있다면, 모든 작업이 끝난 후에도 저장 공간이 비어있지 않다는 조건에 위배되므로 불안정한 작동입니다. 즉시
0을 반환합니다.
위의 모든 조건을 통과했다면, 주어진 로그는 안정적인 작동을 나타내므로 1을 반환합니다.
정답 코드
stack = []
def push(x):
stack.append(x)
def pop():
if stack:
return stack.pop()
return -1
def solve():
n = int(input())
s = input()
for current in s:
if current.isupper(): # 대문자: 컨테이너 꺼내기
ret = pop() # 스택에서 꺼내거나, 스택이 비었으면 -1 반환
# 스택이 비었거나 (ret == -1), 꺼낸 컨테이너 종류가 다르면 불안정
if ret == -1 or ret != current.lower():
return 0
else: # 소문자: 컨테이너 저장
push(current)
# 모든 로그 처리 후 스택이 비어있지 않으면 불안정
return 0 if stack else 1
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()
print(ret)