코드

시간 초과

n = int(input())
arr = list(map(int, input().split()))

check = False

def solution(n, arr):
    for i in range(n):
        for j in range(i+1, n):
            if arr[i] < arr[j]:
                print(arr[j])
                break
                
            if j == n-1:
                print(-1)
    
    # 마지막 요소는 무조건 -1
    print(-1)
solution(n, arr)

구글링 참고

from collections import deque

n = int(input())
arr = list(map(int, input().split()))

# stack은 인덱스를 저장하는 용도로 사용
# 더 빠른 연산을 위해 deque 사용
stack = deque()

# 오큰수가 없으면 -1을 출력하므로 -1로 초기화
result = [-1 for i in range(n)]

# stack은 선입 후출 => arr의 인덱스로 stack[-1]을 사용 (가장 마지막 위치한 요소가 가장 처음 들어간 요소)
# 선입 후출이라 뒤에서부터 요소가 사라진다
# 만약 stack[0]으로 앞에서부터 요소를 비교하면
# pop으로 맨 뒤의 요소값을 제거했는데 앞의 값으로 비교하는 경우가 됨
# 이 때, stack의 첫 요소의 값은 작은데 그 뒤의 요소 값이 큰 경우
# 뒤의 요소값의 크기와는 상관없이 while문이 동작하지 않는다
for i in range(n):
    
    # stack이 비어있지 않고 인덱스로 넣은 스택의 값이 더 작은 경우
    while stack and arr[stack[-1]] < arr[i]:
        
        # stack의 값에 해당하는 result의 인덱스에 arr[i]를 넣음
        result[stack.pop()] = arr[i]
        
    # stack에 i를 넣어줌
    # 맨 처음 반복 시, stack은 비어있으므로 여기서부터 시작
    stack.append(i)
    
# for i in result:
#     print(i, end=' ')
# 위의 for문과 동일    
print(*result)

문제 해설

스택의 성질을 이용하여 오큰수라는 특징을 가진 수를 구하는 문제.

시간 초과가 발생한 코드는 생각보다 쉽게 구현하였다.. 하지만 역시 정답으로 인정받지 못했고 구글링을 통해 코드를 참고하여 문제를 해결하였다. 주석이 거창하듯이 코드를 참고하고도 이해하는데 많은 시간을 투자하여 문제를 해결할 수 있었다.

문제 해결 과정은 아래와 같다.

오큰수

스택의 특성인 LIFO 개념을 이용하여 뒤의 요소로 계속 값을 비교하면서 while문을 돌려주고 스택 자체에는 index를 저장하여 이를 주어진 배열과 함께 활용하여 문제를 푸는 방식에 감명을 받았다. 다양한 문제 풀이법을 습득할 수 있도록 부단히 노력해야겠다.

댓글남기기

참고