[Python] 프로그래머스, 뒤에 있는 큰 수 찾기 Lv.2 (feat.Stack, 시간초과, 파이썬, while문에서 list 활용법)

반짝반짝 알고리즘, 인프준

 

 

 

뒤에 있는 큰 수 찾기

문제 링크

프로그래머스

 

문제 설명

정수로 이루어진 배열 'numbers'가 있습니다. 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰 수라고 합니다. 정수 배열 'numbers'가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰 수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해 주세요. 단, 뒷 큰 수가 존재하지 않는 원소는 -1을 담습니다.

 

제한 조건

4 <= 'numbers'의 길이 <= 1,000,000

1 <= 'numbers[i]' <= 1,000,000

 

 

입출력 예

numbers	result
[ 2, 3, 3, 5 ]	[ 3, 5, 5, -1 ]
[ 9, 1, 5, 3, 6, 2 ]	[ -1, 5, 6, 6, -1, -1 ]

 

입출력 예 설명

입출력 예#1

2의 뒷 큰 수는 3입니다. 첫 번째 3의 뒷 큰 수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰 수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [ 3, 5, 5, -1 ]이 됩니다.

 

입출력 예#2

9는 뒷 큰 수가 없으므로 -1입니다. 1의 뒷 큰 수는 5이며, 5와 3의 뒷 큰 수는 6입니다. 6과 2는 뒷 큰 수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [ -1, 5, 6, 6, -1, -1 ]이 됩니다.

 

 

 

해결 과정

문제를 읽고 첫 접근은 'numbers'의 모든 수를 뒷 수들과 확인하며 큰 값을 담는 방식으로 구현하였습니다.

 

먼저 결과 값을 'numbers'의 길이만큼 모두 -1로 담아줍니다. 그리고 뒷 수만 확인하기 위해 'numbers'의 값과 인덱스 값을 같이 생성하며 for loop을 돌립니다. i번째 n과 이후 값을 비교하며 뒷 큰 수를 찾기 위한 for loop을 추가하며 이중 for문이 구현되었습니다.

 

여기서 i번째 n보다 큰 j를 만났을 때 -1이 담긴 값을 j로 바꿔주게 되며 큰 j를 만나지 못하면 i번째 값은 그대로 -1이 담긴 채로 넘어갑니다.

 

def solution(numbers):
    answer = [-1] * len(numbers)                    # 결과 값 목록 -1로 셋팅
    
    for i, n in enumerate(numbers):                 # 인덱스와 정수 값으로 for loop
        for j in numbers[ i + 1 : len(numbers) ]:   # 비교를 위해 i번째의 n 이후 부터 for loop
            if n < j:                               # 1. i번째 n 보다 큰 가까운 값을 만나면
                answer[i] = j                       # 2. i번째 결과값에 담고
                break                               # 3. for loop 빠져 나가기
    
    return answer                                   # 결과 값 목록 반환

 

 

위 코드는 논리에 문제가 없어 테스트 케이스에서 실행 성공했지만 이중 for문 사용으로 시간 복잡도가 O(n**2), 즉 n의 값이 커질수록 실행시간이 커지기 때문에 이 코드는 일부 케이스에서 시간 초과가 발생하게 됩니다.

 

 

또 다른 풀이

 

while loop, list & dictionary 활용

while문 조건에 list를 넣어주면 값이 있는 동안 계속 반복하게 됩니다. 반복하다가 조건에 맞을 때 pop() 또는 remove() 할 때 활용할 수 있습니다. 아래 예제코드를 보면 더 쉽게 이해할 수 있으며 dictionary도 비슷하게 활용 가능합니다.

list = [1, 2, 3, 4]

while list:
    print(list.pop())
    
# print
4
3
2
1

 

 

stack 문제로 접근한 코드입니다.

 

1. stack으로 활용할 배열과 결과 값 배열을 'numbers'의 길이만큼 -1로 담아 선언해 줍니다.

 

2. 'numbers'의 길이만큼 for loop을 돌려줍니다.

 

3. while문에서 stack의 마지막 인덱스의 value와 numbers[i] 값과 비교하여 pop()을 해주어 뒷 큰 수가 없는 인덱스가 남도록 합니다.

 

4. stack에는 numbers의 원소의 인덱스를 넣어줍니다.

 

def solution(numbers):
    stack = []
    answer = [-1] * len(numbers)

    for i in range(len(numbers)):
            while stack and numbers[stack[-1]] < numbers[i]:
                answer[stack.pop()] = numbers[i]
            stack.append(i)
    
    return answer

 

 

 

 

 

 

---

 

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습,https://school.programmers.co.kr/learn/challenges