프로그래머스 3단계 답지2

거스름돈

처음 코드,

그냥 dfs를 사용하니 효율성 0이 떴다. dp로 풀어보자

function solution(n, money) {
    money.sort((a,b)=>a-b);
    let answer=0;
    for(let i=0;i<money.length;i++){
        dfs(n-money[i],i);
    }
    function dfs(n,idx){
        for(let i=idx;i<money.length;i++){
            if(n===0) answer++;
            if(n<money[i]) break;
            dfs(n-money[i],i);
        }
    }
    return answer%1000000007;
}

 

수정1

ans(money_length, n) = ans(i-1, n) + ans(i-1, n-money[i]) + ans(i-1, n- 2*money[i]) + ...

생각해보면 당연한 식인데 찾기 쉽지 않다.. 질문란보고 알았다.

효율성 몇개만 성공

function solution(n, money) {
    money.sort((a,b)=>a-b);
    function ans(money_length,n){
        if(money_length===1){
            if(n%money[0]===0){
                return 1;
            }
            return 0;
        }
        else if(n===0) return 1;
        const arr=[];
        while(n>=0){
            arr.push(ans(money_length-1,n));
            n-=money[money_length-1];
        }
        return arr.reduce((acc,cur)=>acc+cur,0);
    }
    return ans(money.length,n)
}

 

수정2

function solution(n, money) {
    let dp=[1].concat(Array(n).fill(0));
    money.forEach(v=>{
        dp[v]+=1;
        for(let i=v+1;i<=n;i++){
            dp[i]+=dp[i-v];
        }
    })
    return dp[n];
}

난 생각못해 ㅈㅈ

아니 생각해

다시풀기

programmers.co.kr/learn/courses/30/lessons/12907

 

 

 

 

 

 

멀리뛰기

function solution(n) {
    let dp=[0,1,2];
    if(n<=2) return dp[n];
    for(let i=3;i<=n;i++){
        dp[i]=(dp[i-1]+dp[i-2])%1234567;
    }
    return dp[n];
}

이것도 답보고 알았다. 생각해보면 당연한건데....

dp[i]는 dp[i-1]에서 1을 더한것과 dp[i-2]에서 2를 더한 것의 합이다.

다시 풀기

programmers.co.kr/learn/courses/30/lessons/12914

 

 

 

 

 

방문 길이 -- Summer/Winter Coding(~2018)

function solution(dirs) {
    const road=[];
    let x=0, y=0;
    dirs.split('').forEach(v=>{
        switch(v){
            case "U" :
                if(y===5) break;
                road.push([[x,y],[x,y+1]],[[x,y+1],[x,y]]);
                y++;
                break;
            case "D" :
                if(y===-5) break;
                road.push([[x,y],[x,y-1]],[[x,y-1],[x,y]]);
                y--;
                break;
            case "L" :
                if(x===-5) break;
                road.push([[x,y],[x-1,y]],[[x-1,y],[x,y]]);
                x--;
                break;
            case "R" :
                if(x===5) break;
                road.push([[x,y],[x+1,y]],[[x+1,y],[x,y]]);
                x++;
                break;
        }
    })
    return multiDimensionalUnique(road).length/2;
    
}
function multiDimensionalUnique(arr) {
    const uniques = [];
    const itemsFound = {};
    for(let i = 0; i < arr.length; i++) {
        const stringified = JSON.stringify(arr[i]);
        if(itemsFound[stringified]) continue;
        uniques.push(arr[i]);
        itemsFound[stringified] = true;
    }
    return uniques;
}

 

그냥 별 생각없이 풀었는데 풀렸다. 중복제거 함수 말고는 생각할 것도 없는 문제였다.

programmers.co.kr/learn/courses/30/lessons/49994

 

 

 

 

 

 

불량 사용자 -- 2019 카카오 개발자 겨울 인턴십

function solution(user_id, banned_id) {
  let result = [];
  function dfs(user, banned, arr) {
    if (arr.length === banned_id.length) {
      result.push(arr);
      return;
    }
    for (let i = 0; i < user.length; i++) {
      if (user[i].length !== banned[0].length) continue;
      let right = true;
      for (let j = 0; j < banned[0].length; j++) {
        if (banned[0][j] !== "*" && user[i][j] !== banned[0][j]) {
          right = false;
          break;
        }
      }
      right &&
        dfs(
          user.filter((v, idx) => i !== idx),
          banned.slice(1),
          [...arr, user[i]]
        );
    }
  }
  dfs(user_id, banned_id, []);
  result.map(i=>i.sort());
  result=result.map(i=>i.toString());
  return [...new Set(result)].length;
}

안될줄 알았는데 그냥 됬다.... 모지

dfs로 그냥 풀고 sort한다음 배열을 string으로 바꾼후 set으로 중복을 제거해줬다.

어차피 배열의 길이도 같고 응모아이디가 소문자와 숫자로만 이루어져있기 때문에 이렇게 해도 문제없겠다 해서 시범코드로 넣어봤더니 그냥 됬다. 다른것도 그냥 막 풀어도 제발 테케 통과좀 됬으면 좋겠다..

programmers.co.kr/learn/courses/30/lessons/64064

 

 

 

 

 

 

 

야근 지수

function solution(n, works) {
  if (works.reduce((acc, cur) => acc + cur, 0) < n) return 0;
  works.sort((a, b) => b - a);
  let index = 0;
  while (n > 0) {
    if (works[index] < works[index + 1]) {
      index++;
      continue;
    }
    else if (index !== 0 && works[index - 1] === works[index]) {
      index = 0;
      continue;
    }
    works[index] -= 1;
    n--;
  }
  return works.reduce((acc, cur) => acc + cur ** 2, 0);
}

그냥 정렬을 계속하면 당연히 시간초과가 뜬다. 인덱스를 잘 조절해야 된다.

첫번째 if문은 다음 index의 숫자가 더 크면 index를 증가시키는 식이고

두번째 if문은 이전 index의 숫자와 현재 index의 숫자가 같으면 index를 0으로 할당하는 식이고

그 외의 경우에 index의 숫자를 줄여주면서 n도 1씩 줄이는 식이다.

두번째 if문의 예를 보면

223이 나올때 이전에 index가 0또는 1이므로 index가 1이 되고 식에 의해 index가 0이 된다. 이렇게 되면 index가 0일때 두 if문을 만족하지 않으므로 222가 된다.

222인 경우를 봐도 index가 0이 되서 122가 된다.

221이라면 index가 0일때부터 두 if문을 만족하지 않으므로 121이 된다.

즉 첫번째 식때문에 두번째 식이 성립이 된다.(말이 이상하네.... 뭐라 말할지 모르겠음)

programmers.co.kr/learn/courses/30/lessons/12927

 

 

 

 

 

 

스타수열

 

어렵네....

programmers.co.kr/learn/courses/30/lessons/70130

 

 

 

 

 

 

 

줄서는 방법

const getPermutations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((i) => [i]); // 1개씩 선택한다면 모든 배열의 원소를 return한다.

  arr.forEach((fixed, index, array) => {
    const rest = [...array.slice(0, index), ...array.slice(index + 1)]; // fixed를 제외한 나머지 배열(순열)
    const permutations = getPermutations(rest, selectNumber - 1); // rest에 대한 순열을 구한다.
    const attached = permutations.map((permutation) => [fixed, ...permutation]); // fixed와 rest에 대한 조합을 붙인다.
    results.push(...attached); // result 배열에 push
  });

  return results;
};

function solution(n, k) {
    let arr=Array(n).fill().map((v,i)=>i+1);
    let permu=getPermutations(arr,n);
    return permu[k-1];
}

당연히?? 효율성 실패

function solution(n, k) {
    let arr=Array(n).fill().map((v,i)=>i+1);
    let forFactoN=n;
    let answer=[];
    while(answer.length!==n){
        const facto=factorial(forFactoN);
        const interval=facto/forFactoN;
        const idx=Math.ceil(k/interval)-1;
        answer.push(arr.splice(idx,1));
        k-=interval*idx;
        forFactoN--;
    }
    return answer.flat();
}

function factorial(n) {
    let result=1;
    for (n;n>1;n--){
        result*=n;
    }
    return result;
}

index가 0 1 이 헷갈렸다 조금... 왤케 장난질하는것같지

먼저 원래 배열([1,2,3, ~~~])을 만들어 놓자. 그리고 이 배열을 제거하면서 answer 배열에 답을 집어넣을 것이다.

먼저 차근차근 첫번째 숫자부터 찾는다고 생각하자.  순서대로 배열을 정렬한다고 했을때(문제의 조건대로)

n!/n마다 첫번째 숫자가 바뀐다. 천천히 생각해보면 알 수 있다. 그래도 안되면 3,4,5 앞부분만 permutation 함수를 만들어서 실험해봐라.(실패 경우 permutation 함수를 참조)

이제 arr에서 answer로 옮길 index를 찾을 수 있다. 문제의 예시로 설명하면 올림(5/2)-1=2 이다.

이 부분에서 헷갈려서 바로 통과하지 못했다.

문제 예시로 예를 들면

• [1, 2, 3]  0
• [1, 3, 2]  0
• [2, 1, 3]  1
• [2, 3, 1]  1
• [3, 1, 2]  2
• [3, 2, 1]  2

가 되어야 한다. 다섯번째와 여섯번째를 보면 k/interval 값이 5/2=2.5 6/2=3 이다. 따라서 올림후 1을 빼야 한다.

그리고 k에는 방금 구한 index*interval값 위에서 보면 2*2=4를 빼면 된다.

다음 while문에는

arr=[1,2] k=1, n=2(forFactN) 가 된다. 똑같이 반복하면 끝

programmers.co.kr/learn/courses/30/lessons/12936

 

 

 

 

 

 

최고의 집합

function solution(n, s) {
    if(n>s) return [-1];
    const answer=[];
    for(n;n>0;n--){
        const num=Math.floor(s/n);
        answer.push(num);
        s-=num;
    }
    return answer;
}

각 원소의 곱이 최대인 경우는 평균값에 가까운 값인 것을 쉽게 예측할 수 있다.

이것도 처음 경우부터 천천히 생각을 해보자. 첫번째 수는 Math.floor(s/n)인 것이 당연하다. 여기서 n을 하나씩 빼준다. 그리고 s에 num을 뺀다.

solution(2,9)를 생각해보자

num=2/9=4.5=>4 

answer=[4];

s=9-4=5;

여기가 for문의 첫번째 동작부분인데 answer에 한개가 추가됬기 때문에 추가할 집합의 수는 n-1이다. 그래서 n을 빼는것이고 s에 num을 빼는 이유는 자명하므로 생략(문제조건)

programmers.co.kr/learn/courses/30/lessons/12938

 

 

 

 

 

 

하노이의 탑

function solution(n) {
    const answer=[];
    function hanoi(num,from,by,to){
        if(num===1){
            answer.push([from,to]);
        }else{
            hanoi(num-1,from,to,by);
            answer.push([from,to]);
            hanoi(num-1,by,from,to)
        }
    }
    hanoi(n,1,2,3);
    return answer;
}

이건 당연히 못푼다. ^^

어떻게 이걸 책안보고 풀어 나는 멍청해서 불가능

자료구조 책을 보면 재귀부분에 가장 많이 소개되는 예제중에 한가지이다.

아무런 배경지식 없이 바로 풀라고 한다면 푸는게 쉽지 않을 것이다.

먼저 그림으로 구조를 파악하는 것이 중요하다.

혼자서 직접 n이 2일때 3일때 4일때 그림을 그려보자

그러면 1부터 n-1까지의 원판이 2번째 자리에 위치하고 마지막 n번째 원판을 3으로 이동시키고 1부터 n-1까지의 원판을 3으로 옮기는 것을 알 수 있다. 이게 풀이의 전부다.

n이 1일때는 당연히 바로 push를 하면되고

else의 첫번째 문은 1부터 n-1까지의 원판을 by자리로 옮기는 식이고

두번째 문은 n번째 원판을 from에서 to로 올기는 식

세번째 문은 1부터 n-1까지의 원판을 by자리에서 to자리로 옮기는 식이다. 

 

 

 

 

 

 

징검다리 건너기 -- 2019 카카오 개발자 겨울 인턴십

function solution(stones, k) {
    const len=stones.length;
    let min=0;
    let max=200000000;
    while(min<max-1){
        let mid=parseInt((min+max)/2);
        if(check(stones,mid,len,k)) min=mid;
        else max=mid;
    }
    return max;
}

function check(stones,mid,len,k){
    let zero=0;
    for(let i=0;i<len;i++){
        stones[i]<=mid ? zero++ : zero=0;
        if(zero===k) return false;
    }
    return true;
}

 

카카오 해설을 보고 풀었다. 체크하는 함수는 만들 수 있었는데 이분법으로 풀어야 되는지 생각을 못했다. 그리고 min과 max를 처음에는 stones의 최소 최대값으로 하면 된다고 생각했는데 그렇게 하니 테케에서 실패했다.

아래는 카카오 해설의 내용이다.

• 0이 연속으로 K개가 나오는 구간이 있는 경우 : M번째 친구는 징검다리를 건널 수 없습니다.
• 또한, M번째 친구보다 뒤에 건너는 친구들은 모두 징검다리를 건널 수 없습니다.
• 따라서 찾아야 하는 답은 0 이상 M – 1 이하인 정수 중 하나입니다.
• 0이 연속으로 K개가 나오는 구간이 없는 경우 : M번째 친구는 징검다리를 건널 수 있습니다.
• 이 경우 첫 번째 ~ M – 1 번째 친구들은 모두 정상적으로 징검다리를 건널 수 있습니다.
• 따라서 찾아야 하는 답은 M 이상 MAX값 이하인 정수 중 하나입니다.

programmers.co.kr/learn/courses/30/lessons/64062

 

 

 

 

 

 

N-Queen

function solution(n) {
    let answer=0;
    function dfs(arr,n,row){
        if(row===n) answer++;
        for(let column=0;column<n;column++){
            isValid(arr,n,row,column) && dfs([...arr,column],n,row+1);
        }
    }
    function isValid(arr,n,row,column){
        for(let i=0;i<arr.length;i++){
            const diff=row-i;
            if(arr[i]===column || arr[i]+diff===column || arr[i]-diff===column) return false;
        }
        return true;
    }
    dfs([],n,0);
    return answer;
}

 

dfs문제다. 찾아보니 이런 문제는 백트래킹이라고 한다더라

dfs는 그냥 모든 경우. 조건이 성립하지 않으면 뒤로돌아가서는 경우를 찾는건 백트래킹

근데 그동안 백트래킹으로 풀어온 문제도 많다. 그냥 이런 용어가 있구나 했다

퀸의 직선 조건에 의하면 행과 열에 하나씩만 존재할 수 있다. 따라서 배열도 굳이 2차원으로 행,열을 집어넣지 않고 i번째 index의 배열에는 i번째 행의 값으로 넣었다. 그리고 arr[index]는 열의 값이다.

그러면 결국 유효성 함수만 만들면 된다.

직선에 있는 경우, 대각선 두 경우 일때 return false하면 끝

programmers.co.kr/learn/courses/30/lessons/12952

 

 

 

 

 

 

보석 쇼핑 -- 2020 카카오 인턴십

머리아파서 먼저 효율성 생각안하고 풀었을때 대략 o(n^2)

function solution(gems) {
  let n = [...new Set(gems)].length;
  if (n === 1) return [1, 1];
  const result = [];
  for (let i = 0; i < gems.length - n + 1; i++) {
    const arr = [i, gems[i]];
    for (let j = i + 1; j < gems.length; j++) {
      if (!arr.includes(gems[j])) arr.push(gems[j]);
      if (arr.length === n + 1) {
        arr.push(j);
        break;
      }
    }
    if (arr.length === n + 2)
      result.push([arr[0], arr[n + 1], arr[n + 1] - arr[0]]);
  }
  result.sort((a, b) => {
    if (a[2] === b[2]) return a[0] - b[0];
    return a[2] - b[2];
  });
  return [result[0][0] + 1, result[0][1] + 1];
}

 

카카오 공식 해설 참조

function solution(gems) {
  const n = [...new Set(gems)].length;
  let map = new Map();
  let left = 0,
    right = 0;
  map.set(gems[0], 1);
  let result = [];
  while (right !== gems.length) {
    if (map.size === n) {
      result.push([left + 1, right + 1, right - left]);
      const left_value = gems[left];
      const left_value_num = map.get(left_value);
      if (left_value_num === 1) map.delete(left_value);
      else map.set(left_value, left_value_num - 1);
      left++;
    } else {
      right++;
      if (map.get(gems[right])) map.set(gems[right], map.get(gems[right]) + 1);
      else map.set(gems[right], 1);
    }
  }
  result.sort((a, b) => {
    if (a[2] === b[2]) return a[0] - b[0];
    return a[2] - b[2];
  });
  return [result[0][0], result[0][1]];
}

 

일다 이건 내가 푼게 아니다. 해설참조해서 풀었기 때문에...

코드짜는건 쉬운데 저렇게 풀어야 겠다는 생각을 못했다.. 보석의 개수를 세어서 어떻게 할 수 있을까 정도는 생각을 했는데 그 이상을 못했다.

left와 right를 증가시키는 순서를 주의.

result의 2번째 index에 차이를 넣어줬다. sort할때 더 편하게 하기 위해서

 

카카오 해설

문제 해설

1. 맵 자료구조에서, ‘map[보석 이름] = 빈도수’로 정의를 합니다.
2. 왼쪽 포인터 l과 오른쪽 포인터 r을 모두 1번 진열대에 위치시킵니다.
3. 양 포인터 중, 둘 중 하나라도 진열대의 범위를 벗어나면 알고리즘을 종료합니다.
4. 양 포인터가 가리키는 범위 안에 포함된 보석 종류의 개수를 세어 봅니다.(map의 사이즈를 체크합니다)
5. 5-1. 범위 안에 보석 종류가 전체 보석 종류와 일치하면 더 좋은 답인지 체크한 후 l를 증가시킵니다. 그리고 2로 갑니다.
   5-2. 범위 안에 보석 종류가 전체 보석 종류보다 작다면 r를 증가시킵니다. 그리고 3으로 갑니다.

즉, 왼쪽을 가리키는 포인터 l과 오른쪽을 가리키는 포인터 r을 이용하여 보석의 종류가 모자라면 r을 증가시키고, 보석의 종류가 충분하면 l을 증가시키는 과정을 반복하면서, 정답을 갱신시켜나갑니다. 이때 l을 증가시키기 이전, map자료구조에서 l번 진열대에 있던 보석의 빈도수를 감소시켜주어야 하며 특히 빈도수가 1에서 0이 될 때에는 map에서 완전히 제거하여야 합니다. r을 증가시킬 때는 map자료구조에서 증가된 r번 진열대에 있는 보석의 빈도수를 증가시켜줍니다.

tech.kakao.com/2020/07/01/2020-internship-test/

2020 카카오 인턴십 for Tech developers 문제해설

 

programmers.co.kr/learn/courses/30/lessons/67258

 

 

 

 

 

 

 

배달 -- Summer/Winter Coding(~2018)

옛날에 책에서 풀었던 코드 그대로(일부만 수정) Dijkstra 알고리즘

function DirectedGraph() {
    this.edges = {};
}
DirectedGraph.prototype.addVertex = function(vertex) {
    this.edges[vertex] = {};
}
DirectedGraph.prototype.addEdge = function(origVertex, destVertex, weight) {
    if (weight === undefined) {
        weight = 0;
    }
    if(this.edges[origVertex][destVertex]){
        if(this.edges[origVertex][destVertex]>weight)
            this.edges[origVertex][destVertex] = weight;
    }
    else this.edges[origVertex][destVertex] = weight;
}
function _isEmpty(obj) {
    return Object.keys(obj).length === 0;
}

function _extractMin(Q, dist) {
    var minimumDistance = Infinity,
        nodeWithMinimumDistance = null;
    for (var node in Q) {
        if (dist[node] <= minimumDistance) {
            minimumDistance = dist[node];
            nodeWithMinimumDistance = node;
        }
    }
    return nodeWithMinimumDistance;
}

DirectedGraph.prototype.Dijkstra = function(source) {
    // create vertex set Q
    var Q = {},
        dist = {};
    for (var vertex in this.edges) {
        // unknown distances set to Infinity
        dist[vertex] = Infinity;
        // add v to Q
        Q[vertex] = this.edges[vertex];
    }
    // Distance from source to source init to 0
    dist[source] = 0;

    while (!_isEmpty(Q)) {
        var u = _extractMin(Q, dist); // get the min distance

        // remove u from Q
        delete Q[u];

        // for each neighbor, v, of u:
        // where v is still in Q.
        for (var neighbor in this.edges[u]) {
            // current distance
            var alt = dist[u] + this.edges[u][neighbor];
            // a shorter path has been found
            if (alt < dist[neighbor]) {
                dist[neighbor] = alt;
            }
        }
    }
    return dist;
}

function solution(N, road, K) {
    var digraph1 = new DirectedGraph();
    for(let i=1;i<=N;i++) digraph1.addVertex(i);
    for(let i=0;i<road.length;i++){
        digraph1.addEdge(road[i][0],road[i][1],road[i][2]);
        digraph1.addEdge(road[i][1],road[i][0],road[i][2]);
    }
    const result=digraph1.Dijkstra(1);
    let answer=0;
    for(let i in result){
        if(result[i]<=K) answer++;
    }
    return answer;
}

 

클래스로 수정 + 내 방식대로

class Graph {
  constructor() {
    this.edges = {};
  }
  addVertex(vertex) {
    this.edges[vertex] = {};
  }
  addEdge(a, b, weight) {
    if (this.edges[a][b] < weight) return;
    this.edges[a][b] = weight;
    this.edges[b][a] = weight;
  }
  copyEdges() {
    let Q = {};
    for (let vertex in this.edges) {
      Q[vertex] = this.edges[vertex];
    }
    return Q;
  }
  makeInfinity() {
    let dist = {};
    for (let vertex in this.edges) {
      dist[vertex] = Infinity;
    }
    return dist;
  }
  findMin(Q, dist) {
    let minDist = Infinity,
      nodeMinDist = null;
    for (let node in Q) {
      if (dist[node] <= minDist) {
        minDist = dist[node];
        nodeMinDist = node;
      }
    }
    return nodeMinDist;
  }
  Dijkstra(start) {
    let Q = this.copyEdges(),
      dist = this.makeInfinity();
    dist[start] = 0;
    while (Object.keys(Q).length !== 0) {
      let min = this.findMin(Q, dist);
      console.log(min);
      delete Q[min];
      for (let edge in this.edges[min]) {
        let alt = dist[min] + this.edges[min][edge];
        if (alt < dist[edge]) dist[edge] = alt;
      }
    }
    return dist;
  }
}

function solution(N, road, K) {
  const graph = new Graph();
  for (let i = 1; i <= N; i++) graph.addVertex(i);
  road.forEach((v) => {
    graph.addEdge(v[0], v[1], v[2]);
  });
  let result = graph.Dijkstra(1);
  let answer = 0;
  for (let i in result) {
    if (result[i] <= K) answer++;
  }
  return answer;
}

 

obj대신 Map으로 수정 그냥 Map 연습할겸

class Graph {
  constructor() {
    this.edges = new Map();
  }
  addVertex(vertex) {
    this.edges.set(vertex, new Map());
  }
  addEdge(a, b, weight) {
    if (this.edges.get(a).get(b) < weight) return;
    this.edges.get(a).set(b, weight);
    this.edges.get(b).set(a, weight);
  }
  copyEdges() {
    let Q = new Map();
    for (let [key, value] of this.edges) {
      Q.set(key, value);
    }
    return Q;
  }
  makeInfinity() {
    let dist = new Map();
    for (let vertex of this.edges.keys()) {
      dist.set(vertex, Infinity);
    }
    return dist;
  }
  findMin(Q, dist) {
    let minDist = Infinity,
      nodeMinDist = null;
    for (let node of Q.keys()) {
      if (dist.get(node) <= minDist) {
        minDist = dist.get(node);
        nodeMinDist = node;
      }
    }
    return nodeMinDist;
  }
  Dijkstra(start) {
    let Q = this.copyEdges(),
      dist = this.makeInfinity();
    dist.set(start, 0);
    while (Q.size !== 0) {
      let min = this.findMin(Q, dist);
      Q.delete(min);
      for (let edge of this.edges.get(min).keys()) {
        let alt = dist.get(min) + this.edges.get(min).get(edge);
        if (alt < dist.get(edge)) dist.set(edge, alt);
      }
    }
    return dist;
  }
}

function solution(N, road, K) {
  const graph = new Graph();
  for (let i = 1; i <= N; i++) graph.addVertex(i);
  road.forEach((v) => {
    graph.addEdge(v[0], v[1], v[2]);
  });
  let result = graph.Dijkstra(1);
  let answer = 0;
  for (let value of result.values()) {
    if (value <= K) answer++;
  }
  return answer;
}

 

programmers.co.kr/learn/courses/30/lessons/12978

 

 

 

 

 

 

 

 

경주로 건설 -- 2020 카카오 인턴십

 

 

programmers.co.kr/learn/courses/30/lessons/67259

 

 

 

 

 

 

 

기지국 설치 -- Summer/Winter Coding(~2018)

효율성 실패... 그냥 생각없이 품

function solution(n, stations, w) {
    let arr=Array(n).fill(0);
    stations.forEach(v=>{
        v--;
        for(let i=v-w;i<=v+w;i++){
            if(i<0) i=0;
            else if(i>=n) break; 
            arr[i]=1;
        }
    });
    let answer=0;
    if(arr[0]===0){
        for(let i=0;i<2*w+1;i++) arr[i]=1;
        answer++;
    }
    while(arr.reduce((acc,cur)=>acc+cur,0)!==n){
        let idx=arr.indexOf(0);
        for(let i=idx;i<idx+2*w+1;i++){
            if(i>=n) break;
            arr[i]=1;
        }
        answer++;
    }
    return answer
}

 

성공

function solution(n, stations, w) {
    let start, end;
    let spread=2*w+1;
    let answer=0;
    start=1, end=stations[0]-w;
    answer+=Math.ceil((end-start)/spread);
    for(let i=0;i<stations.length-1;i++){
        start=stations[i]+w+1, end=stations[i+1]-w;
        answer+=Math.ceil((end-start)/spread);
    }
    start=stations[stations.length-1]+w+1, end=n+1;
    answer+=Math.ceil((end-start)/spread);
    return answer;
}

 

처음에는 배열로 만들어서 풀었다. 보통 처음에 이 방법이 떠올를 것이다. (나만 그런가..)

효율성을 당연히 실패하고 생각해보니  stations의 인덱스에서만 생각을 하면 됬다. 어디에 설치하는 지는 중요하지 않다. 그저 최소값을 구하는 것 뿐이다. 그렇기 때문에 시작위치, 끝위치, 전파하는 거리만 생각을 하면 훨씬 복잡도를 줄이면서 답이 나온다.

처음과 끝은 조금 경우가 다르기 때문에 그냥 따로 빼줬다.

참고로 start는 진짜 시작하는 부분이고 끝은 뺄샘할때 편하게 하기 위해서 끝부분에 1을 더한 값이다.

ex)  5부터 10 사이의 수는 6개, 10-5+1=6

programmers.co.kr/learn/courses/30/lessons/12979

 

 

 

 

 

숫자 게임 -- Summer/Winter Coding(~2018)

실패1

function solution(A, B) {
    A.sort((a,b)=>a-b);
    B.sort((a,b)=>a-b);
    let answer=0;
    while(B.length!==0){
        const min=A[0];
        const idx=B.findIndex(i=>i>min);
        if(idx===-1) break;
        A.shift();
        B.splice(0,idx+1);
        answer++;
    }
    return answer;
}

 

실패2

function solution(A, B) {
    A.sort((a,b)=>a-b);
    B.sort((a,b)=>a-b);
    let answer=0;
    while(B.length!==0){
        const min=A[0];
        if(min>=B[B.length-1]) break;
        const idx=B.findIndex(i=>i>min);
        A.shift();
        B.splice(0,idx+1);
        answer++;
    }
    return answer;
}

 

성공

function solution(A, B) {
    A.sort((a,b)=>a-b);
    B.sort((a,b)=>a-b);
    let answer=0;
    for(let i=0;i<B.length;i++){
        if(A[answer]<B[i]) answer++;
    }
    return answer;
}

 

위에랑 메커니즘은 똑같다. 그냥 배열을 삭제하는 것 대신 index를 조절할 뿐이다.

오름차순으로 정렬하고 차례대로 비교하면 된다.

programmers.co.kr/learn/courses/30/lessons/12987

 

 

 

 

셔틀버스 -- 2018 KAKAO BLIND RECRUITMENT

function solution(n, t, m, timetable) {
    let min=9*60-t;
    let arr=[];
    timetable=timetable.map(v=>parseInt(v.substr(0,2))*60+parseInt(v.substr(3)));
    timetable.sort((a,b)=>a-b);
    for(let i=0;i<n;i++){
        min+=t;
        let count=0;
        for(let j=0;j<m;j++){
            if(min>=timetable[0]){
                count++;
                arr.push(timetable.shift());
            }
        }
        if(i===n-1 && count===m) min=arr[arr.length-1]-1;
    }
    let hour=Math.floor(min/60);
    min%=60;
    if (String(hour).length === 1) hour = "0" + String(hour);
    if (String(min).length === 1) min = "0" + String(min);
    return hour + ":" + min;
}

뭔가 안풀려서 복잡하게 막 풀었는데 일단 풀렸다

 

programmers.co.kr/learn/courses/30/lessons/17678

 

 

 

 

 

 

 

 

경주로 건설 -- 2020 카카오 인턴쉽

블록이동먼저하고 풀어야지

programmers.co.kr/learn/courses/30/lessons/67259