[프로그래머스] LV2 > 연습문제 > 뒤에 있는 큰 수 찾기

LV2 > 연습문제 > 뒤에 있는 큰 수 찾기

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

프로그래머스

 

 

def check(index, arr):
    len_arr = len(arr)
    max_n = 0
    for j in range(index, len_arr):
        if j <= len_arr-2:
            if arr[index] < max(arr[index : j+2]):
                return max(arr[index : j+2])
        else:
            return -1
    

def solution(numbers):
    answer = []
    max_n = max(numbers)
    for i in range(len(numbers)):
        if (i == (len(numbers)-1)) or (numbers[i] == max_n):
            answer.append(-1)
        elif numbers[i] < numbers[i+1]:
            answer.append(numbers[i+1])
        elif numbers[i] >= numbers[i+1]:
            answer.append(check(i, numbers))
            
    return answer

 

10번 ~ 22번 문제 시간초과

 

 

def check(index, arr, n):
    len_arr = len(arr)
    max_n = 0
    if index+n <= len_arr:
        if arr[index] < max(arr[index : index+n]):
            return max(arr[index : index+n])
        else:
            return check(index, arr, n+1)
    else:
        return -1
    

def solution(numbers):
    answer = []
    max_n = max(numbers)
    for i in range(len(numbers)):
        if (i == (len(numbers)-1)) or (numbers[i] == max_n):
            answer.append(-1)
        elif numbers[i] < numbers[i+1]:
            answer.append(numbers[i+1])
        
            
        elif numbers[i] >= numbers[i+1]:
            answer.append(check(i, numbers, 1))
    return answer

 

6번 ~ 22번 문제 시간초과

재귀가 더 시간을 많이 잡아먹음

구조적인 문제가 분명

 

마지막으로 구조는 그대로 가져가고

tru / except문을 활용해보았다.

def solution(numbers):
    answer = []
    max_n = max(numbers)
    for i in range(len(numbers)):
        if (i == (len(numbers)-1)) or (numbers[i] == max_n):
            answer.append(-1)
        elif numbers[i] < numbers[i+1]:
            answer.append(numbers[i+1])
        else:
            for k in range(1, len(numbers[i:])+1):
                try:
                    # print("try문 들어옴")
                    # print(i, numbers[i], k)
                    if numbers[i:].index(numbers[i]+k) >= 0:
                        answer.append(numbers[i]+k)
                        # print(answer)
                        check = 1
                        break
                except:
                    check = 0
                    continue
                    
            if check == 0:
                answer.append(-1)
                    
                
        
    return answer

 

잘못된 부분이 있는지 실패가 많이 떴다.

결국 찾아보고 stack 자료구조를 활용해 뒤에서부터 비교하는 방법으로 많이 풀이한 것을 알았다.

그래서 다음과 같이 풀이했다.

이 풀이에서 가장 중요한 부분은 앞에서 부터 비교하던걸 뒤에서 부터 비교하는 거라 생각한다.

앞에서 비교할 때는 내 다음것을 고려해야 되지만, 뒤로 비교하면 나보다 작다면 적용해주고 나보다 크다면 없애면 된다!

 

def solution(numbers):
    n = len(numbers)
    answer = [-1] * n  # 정답을 -1로 초기화
    stack = []  # 스택을 초기화

    for i in range(n - 1, -1, -1):  # 배열을 오른쪽에서 왼쪽으로 순회
        # 현재 숫자보다 작은 숫자는 스택에서 제거
        while stack and stack[-1] <= numbers[i]:
            stack.pop()
        
        # 스택이 비어 있지 않다면 스택의 맨 위가 '뒤에 있는 큰 수'
        if stack:
            answer[i] = stack[-1]
        
        # 현재 숫자를 스택에 추가
        stack.append(numbers[i])

    return answer

 

 

만약 이해하기 어렵다면 다음 print문을 같이 사용하면 좋을거 같다.

def solution(numbers):
    n = len(numbers)
    answer = [-1] * n  # 정답을 -1로 초기화
    stack = []  # 스택을 초기화

    for i in range(n - 1, -1, -1):  # 배열을 오른쪽에서 왼쪽으로 순회
        # 현재 숫자보다 작은 숫자는 스택에서 제거
        print('index = ', i, 'stack =',stack, 'numbers =', numbers[i])
        while stack and stack[-1] <= numbers[i]:
            stack.pop()
            print('stack pop')
        
        # 스택이 비어 있지 않다면 스택의 맨 위가 '뒤에 있는 큰 수'
        if stack:
            answer[i] = stack[-1]
        
        # 현재 숫자를 스택에 추가
        stack.append(numbers[i])
        print('answer - ',answer)
        print('stack =',stack)
        
    
    return answer