[프로그래머스/python] 뒤에 있는 큰 수 찾기

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

프로그래머스

 

 

사용 자료구조: 스택

 

 

사실 문제의 답을 내는 논리 자체는 너무 쉬워서 이게 왜 Lv. 2 ? 라고 생각했지만.. 23 개의 테스트케이스 중에 11번까지 통과되고 나머지는 시간초과가 떴다. 

 

이중 for 문을 사용하기 때문에 시간 복잡도가 O(n^2) 이 되기 때문에 n 값이 커질수록 실행시간이 길어져 시간 초과가 발생한 것이다. 

 

 

시간초과코드

def findLargerThenMe(cur, numList):
    for i in range(len(numList)):
        if cur < numList[i]:
            return numList[i]
    return -1

def solution(numbers):
    answer = []

    for i in range(len(numbers)-1):
        if numbers[i] < numbers[i+1]:
            answer.append(numbers[i+1])
        else:
            answer.append(findLargerThenMe(numbers[i], numbers[i + 1:]))
    answer.append(-1)

    return answer

 

 

이렇게 저렇게 코드를 코쳐봤지만, 도저히 모르겠어서 풀이를 보고 공부했다. (분하다 😭)

 

 

우선 이 문제를 풀려면 스택을 사용해야 한다.

 

스택: 데이터를 임시로 저장하는 자료구조로 자료를 차례대로 처리할 수 있도록 해줌

-> 스택을 사용하여 뒷큰수를 찾지 못한 숫자의 인덱스를 저장해 두고 numbers 배열을 돌면서 뒷큰수 찾기

 

1. answer 배열을 numbers 배열을 길이만큼 -1 로 초기화 -> 뒷큰수가 존재하지 않는 경우 계속 -1 로 남아있어야 하기 때문

2. numbers 배열을 돌면서 방문

3. 방문한 numbers 숫자와 numbers[스택 꼭대기 값=인덱스] 를 확인 

• 방문한 numbers 값이 뒷큰수가 될 수 있다면 스택 꼭대기 값을 pop 시키고 answer 에 방문한 numbers 값 추가
• 방문한 numbers 값이 뒷큰수가 될 수 없다면 방문한 numbers 배열의 인덱스를 스택에 넣고 2번으로 돌아가서 반복

 

예시)

 

answer 배열을 numbers 배열의 길이만큼 -1 로 초기화하고 시작

 

가장 먼저 배열의 9를 방문, 스택에 9의 인덱스인 0을 넣음 (비교할 대상이 존재하지 않음)

 

1을 방문

스택의 꼭대기 값인 9와 1을 비교 -> 1은 9의 뒷큰수가 될 수 없음 -> 스택에 1의 인덱스 추가

 

5를 방문

스택의 꼭대기 값인 1과 5를 비교 -> 5는 1의 뒷큰수가 될 수 있음 -> 스택에서 1을 pop, answer 1번 인덱스 값을 5로 바꿈(뒷큰수 추가)

다시 스택의 꼭대기 값인 9와 5를 비교 -> 5는 9의 뒷큰수가 될 수 없음 -> 스택에 5의 인덱스 추가

 

3을 방문

스택의 꼭대기 값인 5와 비교 -> 3은 5의 뒷큰수가 될 수 없음 -> 스택에 5의 인덱스 추가

 

6을 방문

스택의 꼭대기 값인 3과 비교 -> 6은 3의 뒷큰수가 될 수 있음 -> 스택에서 3을 pop, answer 3번 인덱스 값을 6으로 바꿈(뒷큰수 추가)

스택의 꼭대기 값인 5와 비교 -> 6은 5의 뒷큰수가 될 수 있음 -> 스택에서 5를 pop, answer 2번 인덱스 값을 6으로 바꿈(뒷큰수 추가)

스택의 꼭대기 값인 9와 비교 -> 6은 9의 뒷큰수가 될 수 없음 -> 스택에 6의 인덱스 추가

 

마지막 수인 2는 뒤에 남는 수가 없기 때문에 무조건 -1의 값을 가지게 됨.

스택에 마지막까지 남아있던 6과 9 역시 뒷큰수가 없기 때문에 -1의 값을 가지게 됨.

 

 

전체코드

def solution(numbers):
    answer = [-1]*len(numbers)
    
    stack = []
    
    for index in range(len(numbers)):
    
        visit = numbers[index]
        
        while stack and numbers[stack[-1]]<visit:
            answer[stack.pop()]=visit
            
        stack.append(index)
                
    return answer