Lv2. 뒤에 있는 큰 수 찾기

문제 보기 :  코딩테스트 연습 - 뒤에 있는 큰 수 찾기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

---

문제

• 정답률 : 60%

---

작성 코드

def solution(numbers):
    answer = []
    for i in range(len(numbers)):
        if i!=len(numbers)-1 and numbers[i] <= max(numbers[i+1:]) :
            for k in numbers[i+1:]:
                if numbers[i] < k:
                    answer.append(k)
                    break
        else:
            answer.append(-1)
    return answer

21점짜리 답안...ㅋㅋㅋㅋㅋㅋ ㅠㅠ 사실 통과 못할 줄 알고 있었다.

def solution(numbers):
    answer = []
    i = 0
    while True: #for i in range(len(numbers)):
        if i == len(numbers)-1:
            answer.append(-1)
            break
        
        elif numbers[i] > max(numbers[i+1:]):
            answer.append(-1)
            i += 1
            
        else:
            passturn = 1 ; num = numbers[i]
            for k in range(i+1,len(numbers)):
                if num >= numbers[k]:
                    passturn +=1
                    all_small = 1
                else: #num < numbers[k]
                    all_small = 0
                    break
        
            if all_small == 1 :
                jj = [-1]*passturn
                answer += jj
                i += passturn
            elif all_small == 0 and passturn < 3: #
                jj = [numbers[k]]*passturn
                answer += jj
                i += passturn
            else: #
                jj = [numbers[k]]
                answer += jj
                i += 1
    return answer

[9, 1, 5, 3, 6, 2] [-1, 5, 6, 6, -1, -1]의 경우, [5, 3, 6]에서 [6,6,-1]로 처리되는 것을 보고
아! 5보다 큰 수를 찾는 과정에서 사이에 나온 숫자들도 모두 같은 수로 처리하면 되겠구나 라고 생각했고 그렇게 처리했다. 

그리고 추가로 "예제 [5, 1, 3, 6] / 기댓값 [6, 3, 6, -1]"의 테스트 케이스를 새로 만들어서 시도해봤다.
여기는 위의 예제와 다른 문제가 발생하는데, 내가 위에서 고려했던 그대로 적용한다면, 기댓값은 [6,6,6,-1]이어야한다. 
하지만 기댓값은 [6,3,6,-1]이다. 그래서 passturn이 3 미만인 경우에만 사이 숫자를 같은 수로 처리하고, 만약 3 이상인 경우 1개만 numbers[k]로 두고, 뒤엔 다시 while문을 돌도록 코딩했다.

근데.. 이렇게 한 결과도 21.7점이었다. 대부분 런타임에러/시간초과가 문제 ㅠㅠ

 

def solution(numbers):
    answer = [-1]*len(numbers)
    
    for i in range(len(numbers)-2,-1,-1):
        
        if numbers[i] < numbers[i+1]: #3<5
            answer[i] = numbers[i+1]
            
        elif numbers[i] > numbers[i+1]: #6>2
            for j in range(i+1,len(numbers)):
                if numbers[i] < answer[j]:
                    answer[i] = answer[j]
                    break
                elif answer[j] == -1:
                    break
                    
        elif numbers[i] == numbers[i+1]: #3=3
            answer[i] = answer[i+1]
            
    return answer

진짜 두시간 동안 이거만 목이 빠져라 풀었다..

살...려줘...

동적 프로그래밍 으으으으 너무 어렵다

---

풀이

설명은 짧게 작성하겠다... (멘탈이 다소 털린 상태임)

동적 프로그래밍으로 풀었다. 전체를 -1로 두고 대소관계에 따라 -1를 때로는 5로, 3으로, 2로 변경하면서 answer를 조정했다. 

동적 프로그래밍을 많이 해보지 않은 나한테는 난이도가 높게 느껴졌다....ㅠㅠ

역시 코테는 풀고 풀어도 끝이 없는 것 같다. (Like 수학)