[콭] 오래 걸린 코테 문제 모음1-DP/스택

강원지·2023년 3월 19일

코테

코테 다시보기

목록 보기

15/22

숫자 변환하기

문제

x+n, x*2, x*3을 반복하여 y로 만들 수 있는 최소 연산 횟수를 구하여라

접근방법

완전탐색-bfs
다이내믹 프로그래밍-현재 연산 횟수 이전에 동일한 숫자에 도달했던 적이 있다면 그 숫자에 대해서는 다시 탐색하지 않음

javascript 코드

function solution(x, y, n) {
    var answer = 0;
    
    let data=[x]
    let obj={}
    if(x===y) return 0
    while(data.length){
        let newData=[]
        for(const d of data){
            for(const e of [d+n,d*2,d*3]){
                if(obj[e]) continue 
                obj[e]=true
                if(e===y) return answer+1
                if(e<y) newData.push(e)
            }         
        }
        answer++ 
        data=newData
    }
    
    return -1;
}

23.04.05 다시 풀기

function solution(x, y, n) {
  let dp = {};
  dp[x] = 0;

  let visit = [x];

  if(x===y) return 0
    
  while (visit.length) {
    let now = visit.shift();
    for (const e of [now + n, now * 2, now * 3]) {
      if(e===y) return dp[now]+1
      if (e > y || dp[e]) continue;
      dp[e] = dp[now] + 1;
      visit.push(e);
    } 
  } 
  return -1;
}

뒤에 있는 큰 수 찾기

문제

배열에 담긴 수들에 대해 뒤에 있는 수 중 가장 가까이 있는 큰 수를 배열에 담아 반환하라 큰 수가 없다면 -1을 넣어라

접근방법

뒤에 있는 큰 수를 찾는 문제기 때문에 뒤에서부터 배열을 탐색하며 큰 수를 발견하면 max 배열에 넣음.

배열을 역순으로 뒤집은 뒤
reverse[i-1]가 reverse[i]보다 크다면(원배열에서 뒷 수가 작다면) max와 reAnswer배열에 reverse[i-1]를 넣음(unshift는 너무 느림)
reverse[i-1]가 reverse[i]보다 작다면(원배열에서 뒷 수가 크다면)
- max배열에서 reverse[i]보다 큰 수를 찾을 때까지 max를 pop하고
- 결국 큰 수가 없다면 reAnswer에 -1 삽입
- max배열에서 reverse[i]보다 큰 수를 찾았다면 reAnswer에 max를 삽입하고 반복문을 끝냄

max를 탐색하지 않도록 정렬했으면 더 좋았을 듯

reAnswer를 뒤집어서 반환

힙/우선순위 큐

javascript 코드

function solution(numbers) {
    var answer = [];
    let reAnswer=[] 
    
    let reverse=[]
    let len=numbers.length-1
    numbers.forEach((n,i)=>reverse[len-i]=n)
    
   let max=[reverse[0]]
    for(let i=0;i<=len;i++){
        if(reverse[i]<reverse[i-1]) { 
            max.push(reverse[i-1])
            reAnswer.push(reverse[i-1])
            continue
        }
        while(1){
            let maxLen=max.length
            if(maxLen===0){
                reAnswer.push(-1)
                break;
            }
            if(max[maxLen-1]<=reverse[i]){
                max.pop()
            }else if(max[maxLen-1]>reverse[i]){
                reAnswer.push(max[maxLen-1]) 
                break
            }
        } 
    }
    reAnswer.forEach((n,i)=>answer[len-i]=n)
    return answer;
}

23.04.05 다시 풀기

function solution(numbers) {
    let answer =new Array(numbers.length).fill(-1)
    
    let stack=[0]
    for(let i=1;i<numbers.length;i++){
        while(stack.length&&numbers[stack[stack.length-1]]<numbers[i]){ 
            let idx=stack.pop()
            if(numbers[idx]<numbers[i]) answer[idx]=numbers[i]   
        }
        stack.push(i)
    }
    
    return answer;
}