[백준 알고리즘/Python3] 17298 오큰수

문제 이해

수열에서 하나를 집고 오른쪽으로 차례대로 돌면서 큰 수가 나오면 정지하는 식으로 생각했습니다. 하지만 시간초과가 나왔습니다.

 

코드

list_size = input()

list = input().split()

result = ''

for i in range(len(list_size)):
    stack = []
    #오른쪽만 스택에 담는다.
    for j in range(len(list)):

        stack.extend(list[j+1:]) # 들어온 수의 한칸 앞부터 스택에 넣는다.

        if(stack == []): #스택이 끝났다면
            result += '-1 '
            break

        for k in stack:
            if(list[j] < k): #스택에 있는 값이 수열 j보다 작으면 오큰수
                result += k + ' '
                break
            elif(list[-1] == k): # 스택에 큰 값이 없다면
                result += '-1 '
                break
            
        stack.clear()

print(result, end='')

 

 

다른 방법을 생각해야 합니다. 도저히 생각이 나지 않아 다른분의 풀이를 보고 했습니다.

 

코드

list_size = int(input())

list = input().split()

stack = []

for i in range(list_size): # 수열의 크기만큼 

    #처음에 스택이 비어있다면 하나 넣고 시작
    if(stack == []):
        stack.append(i)
        continue

    # 스택이 비어있거나 해당 인덱스가 높다면 실행
    while(stack != [] and int(list[i]) > int(list[stack[-1]]) ): 
        list[stack.pop()] = list[i]
    stack.append(i)

#남아있는 스택이 있으면 해당 인덱스를 -1로 변환
while(stack != []):
    list[stack.pop()] = -1

#list의 int를 str로 변환
for z in range(len(list)):
    list[z] = str(list[z])

print(' '.join(list))

저는 하나씩 교체 할 생각을 했지 수열을 한꺼번에 정리할 생각을 못했습니다. 수열을 돌면서 더 작은 수를 스택에 넣고 큰 수를 만나면 스택에 있는 것(인덱스)을  큰 수와 비교하는 방법입니다.

 

 

출처