[프로그래머스] 뒤에 있는 큰 수 찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제를 해결하기 위해 처음에 이중 for문을 사용하니 시간초과가 발생하였다.

하여 for문을 하나만 사용하면서 문제를 해결할 수 있는 방안을 생각해 보았다.

우선 현재 숫자와 다음 숫자를 한 번만 비교하면서 다음 숫자가 더 크면 다음 숫자로 바꾸면 되고, 만약 현재 숫자가 더 크거나 같다면 우선 해당 위치를 따로 저장한다.

해당 과정을 반복하다가 따로 저장한 위치의 숫자 값보다 큰 값이 현재 숫자로 나오게 된다면 이전에 저장해 둔 위치의 값들을 모두 현재 숫자(저장해 둔 위치의 숫자 값보다 큰 숫자)로 바꾸면 된다.

 

1. 정답 리스트를 모두 -1로 초기화한다. answer = [-1] * len(numbers)
2. 현재 숫자의 위치를 저장해 줄 리스트를 생성한다. li = list()
3. 현재 숫자와 다음 숫자를 비교해야 하므로 숫자 리스트의 마지막 전까지 반복한다. for i in range(len(numbers) - 1)
4. 만약 현재 숫자가 다음 숫자보다 작다면 if (numbers[i] < numbers[i + 1])
5. 정답의 현재 숫자 위치에 다음 숫자를 저장한다. answer[i] = numbers[i + 1]
6. 숫자의 위치를 저장한 리스트가 공백이 아니고 마지막으로 저장된 위치의 숫자 값이 현재 숫자보다 작으면 계속 반복한다. while (li) and (numbers[li[-1]] < numbers[i])
7. 마지막 위치를 가져와 정답의 해당 위치에 현재 숫자를 저장한다. answer[li.pop()] = numbers[i]
8. 현재 위치를 추가한다. li.append(i)
9. 마지막 전까지 반복을 하고 나서 숫자의 위치를 저장한 리스트가 공백이 아니고 마지막으로 저장된 위치의 숫자 값이 다음 숫자(마지막 숫자) 보다 작으면 계속 반복한다. while (li) and (numbers[li[-1]] < numbers[i + 1])
10. 마지막 위치를 가져와 정답의 해당 위치에 다음 숫자(마지막 숫자)를 저장한다. answer[li.pop()] = numbers[i + 1]

반응형

3. 소스코드

def solution(numbers):
    answer = []
        
    answer = [-1] * len(numbers)
    li = list()
    for i in range(len(numbers) - 1):
        if (numbers[i] < numbers[i + 1]):
            answer[i] = numbers[i + 1]

        while (li) and (numbers[li[-1]] < numbers[i]):
            answer[li.pop()] = numbers[i]

        li.append(i)

    while (li) and (numbers[li[-1]] < numbers[i + 1]):
    	answer[li.pop()] = numbers[i + 1]

    return answer