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

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2023-04-20

  • 해결 방법 :

    • dp와 2중 반복문을 활용해 문제 해결
      • 외부 반복문에서 numbers를 거꾸로 돌되, numbers의 (마지막 인덱스 - 1)부터 시작(i)
      • 내부 반복문에서 i 이후로 탐색(j)
        • 현재보다 큰 값이면(numbers[j]) dp 업데이트 후 내부 반복문 종료
        • dp가 현재보다 큰 값이면(dp[j]) dp 업데이트 후 내부 반복문 종료
        • 이 때 dp가 -1이면(dp[j]) 뒤 숫자들은 더 이상 탐색할 필요가 없으므로 내부 반복문 종료

  • 회고 :

    • 처음에 numbers의 길이가 1,000,000 이었기에 한 번 반복이나 이진탐색으로 해결해야 한다고 생각했다.
    • 그러나 뒤 숫자들은 앞 숫자에 영향을 받기에 dp를 통해 해결할 수 있다고 생각했고, 코드를 짰다.

    • 처음 코드

      function solution(numbers) {
  const dp = Array.from({ length: numbers.length }, () => -1);

  for (let i = numbers.length - 2; i >= 0; i--) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] < numbers[j]) {
        dp[i] = numbers[j];
        break;
      }

      if (numbers[i] < dp[j]) {
        dp[i] = dp[j];
        break;
      }
    }
  }

  return dp;
}

    • 그러나 두 테스트 케이스에서 시간 초과가 발생했다..

      image

    • 곰곰이 생각하던 중 안쪽 반복문에서 첫 dp[j]가 -1인 경우도 더 이상 뒤를 탐색할 필요가 없으므로 다음과 같이 조건에 추가했다.

      if (numbers[i] < dp[j] || dp[j] === -1) {
  dp[i] = dp[j];
  break;
}

    • 통과 !!

      image

  • 코드

    function solution(numbers) {
  const dp = Array.from({ length: numbers.length }, () => -1);

  for (let i = numbers.length - 2; i >= 0; i--) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] < numbers[j]) {
        dp[i] = numbers[j];
        break;
      }

      if (numbers[i] < dp[j] || dp[j] === -1) {
        dp[i] = dp[j];
        break;
      }
    }
  }

  return dp;
}

  • 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges