프로그래머스 JAVA 뒤에 있는 큰 수 찾기(DP)

다들 스택으로 풀던데 풀이를 봐도 이해가 가지 않더라구요...............

DP 풀이는 별로 없는데 이게 그나마 이해가 가서리 ..

 

처음에 완전탐색으로 풀어서 당연히 시간초과 나서 풀이 찾아봤구요 

DP는 비슷한데 뒤에서부터 시작해서 마지막은 무조건 -1 이니깐 빼고 아래 처럼 비교를 해줍니다

 

EX) i = 3일 때 

         num i  [9, 1, 5, 3, 6, 2] 

        num  j  [9, 1, 5, 3, 6, 2]

 

    answer j  [ -1, 5, 6, 6, -1, -1 ]

 

        num i  [9, 1, 5, 3, 6, 2] 

 answer j  [ -1, 5, 6, 6, -1, -1 ]

--> numbers[i] < answer[j]  // 현재 num이 이전 ans 와 비교해서 작으면 똑같은 ans 를 넣는다.

answer[i] = answer[j]  // 이게 뒤에 있는 가장 큰 수니깐

 

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        Arrays.fill(answer, -1); 
        
  for (int i = numbers.length - 2; i >= 0; i--) {
    for (int j = i + 1; j < numbers.length; j++) {
 
        if (numbers[i] < numbers[j]) {
            answer[i] = numbers[j];
            break;
        }
        
        if (answer[j] == -1) break;
        
        if (numbers[i] < answer[j]) {
            answer[i] = answer[j];
            break;
        }
    }
  }
        
        return answer;
    }
}

 

이 문제 시간초과 나고 다이나믹 프로그래밍으로 풀어야겠다, 이 전 값 이용해야겠다 생각은 했는데 답을 보니 한끗차이지만 더 공부해야겠습니다 ..