[프로그래머스] 1154539 : Lv2 뒤에 있는 큰 수 찾기| 스택

[프로그래머스] 1154539 : Lv2 뒤에 있는 큰 수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

---

[python] 문제 풀이

배열의 수 만큼 루프를 돌려서 직접 원소들의 크기를 비교하는 코드를 짬. 

1. results 리스트를 생성해서 모든 값을 -1 로 초기화. 각 요소는 숫자에 대한 결과 값을 저장하게 됨. (큰 수가 없으면 -1로 남게 함) 

2. 마지막 요소를 제외하고 numbers에 있는 모든 요소들의 크기를 비교해야함.

3. 현재 요소값과 그 뒤에 있는 모든 요소 값을 비교.

def solution(numbers):
    results = [-1] * len(numbers) # results 리스트 생성 초기화
    for i in range(len(numbers)-1):  # 마지막 요소 제외하고 numbers 리스트 각 요소에 대해 반복
        values = numbers[i] #i번째 요소 값을 values에 저장
        for j in numbers[i+1:]: #현재 요소 values다음에 오는 모든 요소 반복
            if values < j: #현재 요소 값이 j번째 요소랑 크기 비교함.
                results[i] = j #크기가 큰 요소를 result리스트에 저장
                break
    
    return results

ㅋ,,,,,,,, 시간초과 

gpt 말로는

"당신의 코드는 두 개의 중첩된 루프를 사용하여 numbers 리스트를 탐색합니다. 이로 인해 시간 복잡도가 O(n^2)로 증가하게 되며, 리스트의 길이가 커질수록 실행 시간이 급격히 증가합니다. "란다

 

---

stack 을 사용하면 더 간단하게 코드를 작성할 수 있다.

 

[최종코드]

 

def solution(numbers):
    results = [-1] * len(numbers)
    stack = [] #stack 초기화 #인덱스를 저장하는데 사용
    
    for i in range(len(numbers)):
        while stack and numbers[stack[-1]]<numbers[i]:
            results[stack.pop()] = numbers[i]
        stack.append(i)
    
    return results

 

while stack and numbers[stack[-1]] < numbers[i]:
    results[stack.pop()] = numbers[i]

stack 이 비어있지 않고, stack의 마지막 인덱스에 해당하는 값 < numbers의 i번째 값 이면

-> stack에서 인덱스 꺼내, 해당 인덱스 결과를 숫자 numbers[i]로 저장

 

** 큰 숫자를 찾을 때, 현재 숫자와 비교하고 그보다 작은 숫잗르의 위치를 스택에서 제거하며 처리

-> 시간 복잡도가 줄어듦

---

 

ex) numbers = [2,3,3,5]

1. 초기 설정

 result = [-1,-1,-1,-1]

 stack = []

2. 반복 과정

 i=0 :

- 스택이 비어 있으므로 인덱스 0 추가

-  stack.append(0)

 i=1 :

- 스택 있음, stack[-1]=0  

- numbers [0] =2 가 numbers[1]=3 보다 작음.

- stack.pop() 으로 스택 가장 위의 값 0을 꺼내고, results[0]=number[1]=3으로 업데이트 

- results =[3,-1,-1,-1]

- stack.append(1) -> stack = [1]

i=2 : 

 -  스택의 마지막 값을 인덱스로 갖는  numbers[1]=3은 현재 인덱스 i의 number[2]=3이랑 같음

 -  stack.append(2) -> stack =[1,2]

i=3 :

 -  스택의 마지막 값을 인덱스로 갖는 number[2] = 3 은 현재의 인덱스의 numbers[3]= 5 보다 작음.

stack = [1,2]

 -  stack.pop() 으로 두번 pop 해야함

 1) 첫번째 팝 : 스택의 마지막 값 (인덱스 2) 꺼냄 

     -> stack = [1]

     -> results 에 현재 숫자인 5 를 넣음

 results = [3,-1,5,-1]

  2) 두번째 팝 : 스택의 마지막 값 (인덱스 1) 꺼냄 

       ->stack =[]

       -> numbers[1] =3  이므로 results[1] 에 현재 숫자 5를 넣음.

  results = [3,5,5,-1]

 

 

https://tildacoding.tistory.com/15

[자료구조] [python] Stack(스택)