[3월 31일] 뒤에 있는 큰 수 찾기 | 숫자 변환하기

문제

1. 뒤에 있는 큰 수 찾기

문제 설명

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

 

제한사항

• 4 ≤ numbers의 길이 ≤ 1,000,000

 

입출력 예

numbers	result
[2, 3, 3, 5]	[3, 5, 5, -1]
[9, 1, 5, 3, 6, 2]	[-1, 5, 6, 6, -1, -1]

풀이

function solution(numbers) {
    var answer = [];
//     그냥 하나씩 순회하면 O(n**2)이고, n이 최대 100만이라 시간초과 걸릴 것임

    const st = [];
    for(const number of numbers.reverse()){
        if(st.length===0){
            st.push(number);
            answer.push(-1);
            continue;
        }
        if(st[st.length-1]<=number){
            while(1){
                st.pop();
                if(st.length===0 || st[st.length-1]>number ) break;
            }
            if(st.length===0){
                answer.push(-1);
            }else{
                answer.push(st[st.length-1]);
            }   
        }else{
            answer.push(st[st.length-1]);
        }
        st.push(number);

    }


    return answer.reverse();
}

• st이라는 스택을 만들어서, number보다 st의 가장 위 요소가 클 때와 작을 때를 구분해서 풀어주었다.
• 오른쪽 요소 중 큰수이기에 numbers.reverse()를 통해 number를 거꾸로 순회하였다.

---

2. 숫자 변환하기

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

 

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

결과 : 실패. 방법을 아애 생각해내지 못함. DP를 이용한 문제였음

 

풀이 (다른 사람 풀이)

function solution(x, y, n) {
  if (x >= y) return 0;

  const dp = Array(y + 1).fill(Infinity);
  dp[x] = 0;

  for (let i = x + 1; i <= y; i++) {
    if (x <= i - n) dp[i] = Math.min(dp[i], dp[i - n] + 1);
    if (i % 2 === 0 && x <= i / 2) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
    if (i % 3 === 0 && x <= i / 3) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
  }

  return dp[y] === Infinity ? -1 : dp[y];
}

• 이게 DP구나. DP를 여럿 풀어 봤지만, 문제를 보면 이게 DP문제인지 바로 매칭이 되지 않는다. 경험과 실력이 쌓여야 하는 것 같다.
• DP로 i=x+1부터 i=y까지 배열 dp에 축적해 나간다.
• 만약 x+n ≤ i이라면 현재 dp[i]와 (Infinity일 것임) dp[i-n] 즉, 현재 값에서 -n위치의 값에 +1을 한다. → x부터 +n마다 1씩 더해질 것임.
• 만약 i가 2로 나눠지고, x ≤ i/2라면, dp[i]는 dp[i]와 dp[i/2] + 1 중 더 작은 값을 취한다. dp[i/2]에서 *2를하면 dp[i]위치이기 때문이다.
• i가 3으로 나눠지는 경우도 동일하게 수행
• 쌓아온 것을 바탕으로 dp[y]를 return

 

# DP(Dynamic Programming)

: 하나의 문제는 단 한 번만 풀도록 하는 알고리즘

• ex)피보나치 수열 : 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구함. D[i]=D[i-1]+D[i-2]
• 크고 어려운 문제가 있으면, 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것. 다만 그 과정에서 '메모이제이션'이 사용된다는 점에 분할 정복과 다름

DP를 사용하는 경우

1. 작은 문제들이 중복적으로 발생하는 경우
2. 작은 문제들의 해결 방법이 독립적이지 않은 경우
3. 문제를 작은 부분 문제로 쪼갤 수 있으며, 작은 부분 문제들이 전체 문제에서 반복적으로 사용될 수 있는 경우

---

느낀점

1번 : 문제는 처음에는 '어렵다, 어려워'생각했지만, 차분한 마음을 가지고 차근차근 푸니 술술 풀렸다. 항상 마음은 여유롭게, 뇌는 빠르게 굴려가며 문제를 풀도록 하자.

2번 : 다양한 알고리즘 문제를 이래서 풀어봐야 하는 것 같다. 그것도 툭치면 툭 나오게, 이 문제를 보면 '이 알고리즘을 쓰면 되겠는데?'바로 나오도록 말이다. DP 문제를 전에 여럿 풀어본 적이 있다. 그러나, 위의 2번 문제를 보고 바로 '아 DP로 풀면 되겠네!'라는 생각이 들지 않았다. '이게 뭐지~'싶었다. 앞으로는 다양한 알고리즘의 문제를 풀어보고,  '이게 이런 알고리즘이구나~'하는 식으로 매칭시키며 공부하도록 하자.