알고리즘 문제

뒤에 있는 큰 수 찾기

시도

주어진 문제에서 numbers의 각 요소들의 자리에 다음을 만족하는 숫자가 들어가야 한다.
1. 자신보다 뒤에 위치해야 한다.
2. 자신보다 큰 숫자여야 한다.
3. 큰 숫자 중에서 자신과 가장 가까운 위치여야 한다.
4. 위의 1,2,3을 모두 만족하는 숫자가 담아져야 하며, 해당되는 숫자가 없다면 -1을 담는다.

시도해본 코드는 다음과 같다.

def solution(numbers):
   answer = []
   
   for i, num in enumerate(numbers):
       if i < len(numbers):
           after_list = numbers[i+1:]
           
           for l, after_num in enumerate(after_list):
               if num < after_num:
                   answer.append(after_num)
                   break
                   
               elif l == len(numbers[i+1:])-1 and num >= after_num:
                   answer.append(-1)
                   
   answer.append(-1)
   
   return answer

1. 입력받은 요소 중 첫번째 요소num을 가져온다.
2. num의 다음번째부터 마지막까지를 담는 after_list를 만든다.
   • i가 마지막일때 after_list를 만들 수 없기 때문에 i-1까지만 실행할 수 있도록 조건을 걸어준다.
3. after_list의 각 요소를 돌면서 num과 값을 비교한다.
   4-1. num보다 큰 after_num이 있다면 answer에 after_num을 append하고 for문을 종료한다
   4-2. after_list의 마지막까지 큰 값이 없다면 -1을 append한다.
4. numbers의 마지막값은 뒤에 있는 요소가 존재하지 않기때문에 무조건 -1의 값을 가지므로 for문이 종료된 이후 마지막 -1값을 answer에 append해준다.

각 요소들을 확인할 수 있도록 enumerate를 사용하였고 입력값에 대한 출력값이 제대로 나오는 것을 확인했다.
정답 제출시 8번테스트 이후로 렉걸린줄 알았다.. 뭔가 싶어서 보고있는데 시간초과가 주르르를르륵....
출력은 잘 되지만 시간이 너무 오래걸려서 정답처리를 받지 못했다.. 더 줄이는 방법을 한참 생각해보다가...

해결

다른 분의 풀이의 도움을 받았다.. stack을 활용하여 시간복잡도를 줄여서 해결해야 했다. stack의 기본적인 동작방식만 알았지 이것을 활용할 생각도 못했고 답안 코드의 이해에도 시간이 걸렸다.

답안 코드는 다음과 같다.

def solution(numbers):
    answer = [-1] * len(numbers)
    stack = []
    
    for i, number in enumerate(numbers):
        while stack and numbers[stack[-1]] < number:
            answer[stack.pop()] = number
            
        stack.append(i)
        
    return answer

1. numbers의 길이만큼의 '-1'을 가진 answer을 선언한다.
2. stack 활용을 위한 빈 리스트를 만들어 준다.
3. enumerate를 사용해 for문으로 numbers를 돌린다.
4. 4-1. while문에서 number의 값을 이전값과 비교하여 number가 큰 경우 이전값의 자리에 number값을 넣어주고 이전값의 인덱스를 지워준다.

while문 조건 해석
while stack and numbers[stack[-1]] < number

-> 'stack의 bool값' 
		and 
'numbers[stack[-1]] < number'	의 조건이 True일때 반복하겠다.

stack이 비어있는 경우 bool값이 False이므로 while문 실행없이
아래에 있는 stack.append(i)가 실행되어 i를 stack리스트에 append한다.
조건을 만족하는 경우 'stack.pop()'을 사용하여 
바꾸고자 하는 answer의 인덱스 지정 및 다음 while문을 위해 사용한 것을 지워준다.

4-2. while문의 조건이 false일때까지 반복해야 하기 때문에 4-1의 과정을 반복해준다. 만약 number의 값이 비교하는 값보다 작거나 같은경우 number의 i를 stack리스트에 append한다.

고찰

문제를 해결하긴 했지만 시간복잡도 측면에서 좋지 않았던 시도를 했던 것 같다. 문제해결보다 더 나아가 시간복잡도를 최소한으로 하면서 풀어낼 수 있도록 계속 문제도 풀고, 시간복잡도에 대한 공부도 더 해야되겠다..