[백준][Python] 17298. 오큰수

반응형

 

 

 

 

 

 

🙆‍♂️문제

---

 

🙋‍♂️풀이

---

수열이 주어집니다.

이 수열에 있는 값 중 하나를 Ai라고 했을 때

오큰수는 수열 중 Ai보다 큰 수 중 가장 왼쪽에 있는 수를 의미합니다.

 

🚀 입력받기

---

import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

우선 수열의 길이 n과 수열 arr을 입력 받습니다.

 

🚀 문제 풀이 핵심

---

stack = []
answer=[]
for i in range(n):
    answer.append(-1)
maxNum = max(arr)
for i in range(n):
    if len(stack) == 0:
        stack.append(i)
    else:
        while 1:
            if arr[i] > arr[stack[-1]]:
                answer[stack[-1]] = arr[i]
                stack.pop(-1)
                if len(stack)==0:
                    stack.append(i)
                    break
            else:
                stack.append(i)
                break

스택을 이용해서 풀 수 있는 문제입니다.

먼저 정답 배열을 모두 -1로 초기화 시켜주고 시작합니다.

이는 오큰수가 나오지 않는다면 -1이 되어야 하기 때문에 하는 작업입니다.

 

코드를 보다 자세히 살펴보면

for i in range(n):
    if len(stack) == 0:
        stack.append(i)

먼저 stack의 길이가 0일 때 stack에 아무것 도 없을 때 지금 값이 최대값이라면 -1로 초기화 시켜주고

(사실 없어도 되는 부분임.)

아니라면 stack에 현재 인덱스 값을 넣습니다.

 

    else:
        while 1:
            if arr[i] > arr[stack[-1]]:
                answer[stack[-1]] = arr[i]
                stack.pop(-1)
                if len(stack)==0:
                    stack.append(i)
                    break
            else:
                stack.append(i)
                break

이 부분은 이제 stack에 값이 들어가 있는 경우

현재 잡혀있는 인덱스의 배열값과 stack의 가장 마지막 부분을 비교해서 현재 값이 크다면

정답 리스트에서 이 스택에 저장된 인덱스 부분을 현재 값으로 변경하는 작업을

while문을 통해서 stack에 저장된 인덱스의 리스트 값이 더 클 때 까지 지속 진행합니다. 

 

위의 방식으로 스택을 활용하여 for문을 한번만 돌려서 오큰수로 설정할 수 있습니다.

 

🚀 출력하기

---

for i in answer:
    print(i,end=" ")

728x90