1. x가 1부터 r2일 때까지 반복
2. 해당 시점에서 y의 최댓값, 최솟값 구하기
   • 대각선 길이 구하는 x^2 + y^2 = r^2을 이용해서 y^2 = r^2 - x^2
   • 이때 큰 원의 경계는 포함하지 않도록 버림, 작은 원의 경계는 포함하도록 올림
   • i가 r1보다 크거나 같다면 0으로 처리해서 x축 위의 점까지 세기
3. 1사분면의 점 개수만 센 것이므로 결과는 4를 곱하기

코드

function solution(r1, r2) {
  let result = 0;
  for (let i = 1; i <= r2; ++i) {
    let maxY = Math.floor(Math.sqrt(r2 ** 2 - i ** 2));
    let minY = i >= r1 ? 0 : Math.ceil(Math.sqrt(r1 ** 2 - i ** 2));
    result += maxY - minY + 1;
  }
  return result * 4;
}

🤔

1시간 넘게 고민했는데도 답이 안 나와서 다른 사람들의 풀이를 참고했다. O(n^2)을 O(n)으로 줄이는 건 항상 어려운 것 같다.

• 참고한 블로그 https://judahhh.tistory.com/87 https://supersfel.tistory.com/447

1. 전체 상자에 대해 반복
2. 아직 열리지 않았으면 해당 상자의 카드 번호를 그룹에 추가하고 열림 표시
3. 2번 카드의 번호를 가진 상자 열기
4. 더이상 열 수 없으면 다음 상자에 대해 반복
5. 더이상 만들 수 있는 그룹이 없으면 그룹 배열 길이의 최댓값 구해서 갱신

코드

function solution(cards) {
  let result = 0;
  for (let i = 0; i < cards.length; ++i) {
    const groups = [[]];
    const visited = Array(cards.length).fill(false);
    let curr = cards[i] - 1;

    while (curr >= 0) {
      visited[curr] = true;
      groups.at(-1).push(cards[curr]);
      curr = cards[curr] - 1;
      if (visited[curr]) {
        groups.push([]);
        curr = visited.findIndex((v) => v === false);
      }
    }

    groups.sort((a, b) => b.length - a.length);
    result = Math.max(result, groups[0].length * groups[1].length);
  }
  return result;
}

🦾

슬럼프가 와서 거의 3주를 쉬었는데 다행히 30분도 걸리지 않아서 풀 수 있는 문제였다. 오랜만에 보니까 문제부터 잘 읽히지 않아서 역시 공부는 꾸준히 해야 하는구나 싶었다.

1. 콜라츠 수열을 구하면서 각 구간의 넓이를 배열에 저장 각 구간의 넓이: 작은 수 + (큰 수 - 작은 수) / 2
2. ranges에 대해 반복하면서 구간의 넓이 더해 결과에 담기

코드

function solution(k, ranges) {
  const collatz = [k];
  const area = [];
  while (k > 1) {
    if (k % 2 === 0) k /= 2;
    else k = k * 3 + 1;
    collatz.push(k);
    const [small, big] = [collatz.at(-1), collatz.at(-2)];
    area.push(small + (big - small) / 2);
  }

  const result = [];
  for (const r of ranges) {
    const [start, end] = [r[0], area.length + r[1]];
    if (start > end) {
      result.push(-1);
      continue;
    }
    let tmp = 0;
    for (let i = start; i < end; ++i) {
      tmp += area[i];
    }
    result.push(tmp);
  }
  return result;
}

🦾

요즘 계속 어려워서 좀 지쳐 있었는데 갑자기 쉬어가는 문제 감사합니다...

1. 키 조합 만들기
2. 해당 키 조합을 셋에 담으면서 중복되는지 검사 중복되지 않으면 유일성을 만족한 키 조합에 추가
3. 키 조합 중 이전에 유일성을 만족한 키 조합이 있으면 최소성을 만족하지 못하는 것이므로 제외하기 (이전 키 조합 중 하나가 현재 키 조합의 부분집합인 경우)

코드

function solution(relation) {
  const col = relation[0].length;
  const arr = Array.from(Array(relation[0].length), (_, i) => i);
  let comb = [];
  for (let i = 0; i < col; i++) {
    comb.push(...combination(arr, i + 1));
  }

  comb = checkUnique(relation, comb);
  comb = checkMinimal(comb);
  return comb.length;
}

function combination(arr, selectNum) {
  if (selectNum === 1) return arr.map((v) => [v]);

  const result = [];
  arr.forEach((fix, i, origin) => {
    const combi = combination(origin.slice(i + 1), selectNum - 1);
    const attach = combi.map((c) => [fix, ...c]);
    result.push(...attach);
  });
  return result;
}

function checkUnique(relation, comb) {
  let result = [];

  comb.forEach((c) => {
    let set = new Set();
    relation.forEach((rel) => set.add(c.map((e) => rel[e]).join(',')));
    if (set.size == relation.length) result.push(c);
  });

  return result;
}

function checkMinimal(comb) {
  let result = [];

  while (comb.length) {
    result.push(comb[0]);
    comb = comb.reduce((a, c) => {
      if (!comb[0].every((e) => c.includes(e))) a.push(c);
      return a;
    }, []);
  }

  return result;
}

🤔

절망.. 정말이라고 치려고 했는데 마음의 소리가 이렇게 밖으로.. 최초로 포기하고 싶었던 문제 ㅎㅎㅎ 어찌어찌 재귀로 1시간 붙잡고 있었는데 아무리 해도 테케 반밖에 통과를 못하고 왜인지는 모르겠고... 결국 다른 사람 풀이를 참고했다. 그러고서도 일단 조합 재귀에서부터 보기 싫어져서 내일로 미룰까 하다가 저녁 먹고 와서 종이에 하나씩 그려가면서 이해를 했다. 다시 풀려면 코드를 거의 외워야 할 듯.. 휴... 알고리즘 공부에 이렇게 시간 많이 쓰는 게 맞나... 면접이 코앞인데...

DFS

1. 앞으로 5가지 광물에 대해 3가지 경우의 수로 재귀 매번 피로도의 최솟값 갱신
2. 곡괭이가 없거나 모든 광물을 캤으면 리턴

코드

function solution(picks, minerals) {
  let result = Infinity;
  const recursion = (picks, fatigue, i) => {
    if (picks[0] + picks[1] + picks[2] === 0 || i >= minerals.length) {
      result = Math.min(result, fatigue);
      return;
    }
    const arr = Array(3).fill(0);
    for (let j = i; j < i + 5; ++j) {
      if (j === minerals.length) break;
      if (minerals[j] === 'diamond') {
        arr[0] += 1;
        arr[1] += 5;
        arr[2] += 25;
      } else if (minerals[j] === 'iron') {
        arr[0] += 1;
        arr[1] += 1;
        arr[2] += 5;
      } else {
        arr[0] += 1;
        arr[1] += 1;
        arr[2] += 1;
      }
    }
    for (let j = 0; j < 3; ++j) {
      if (picks[j] <= 0) continue;
      recursion(
        picks.map((e, i) => (i === j ? --e : e)),
        fatigue + arr[j],
        i + 5
      );
    }
  };
  recursion(picks, 0, 0);
  return result;
}

🤔

한번에 통과하긴 했는데 코드가 조잡해보여서 맘에 들진 않는다...

최대힙

• enemy 배열에 대해 반복하면서 라운드를 진행
• n이 음수가 되면 최대힙에서 이전 라운드 중 가장 많았던 병사 수를 꺼내 n에 더해주고 무적권 수 감소

코드

function solution(n, k, enemy) {
  let result = 0;
  const heap = new MaxHeap();
  for (const e of enemy) {
    heap.push(e);
    n -= e;
    if (n < 0) {
      if (k <= 0) break;
      n += heap.pop();
      --k;
    }
    ++result;
  }
  return result;
}

class MaxHeap {
  constructor() {
    this.heap = [];
  }

  size() {
    return this.heap.length;
  }

  swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
  }

  push(v) {
    this.heap.push(v);
    let i = this.size() - 1;
    let parentI = Math.floor((i - 1) / 2);
    while (i > 0 && this.heap[i] > this.heap[parentI]) {
      this.swap(i, parentI);
      i = parentI;
      parentI = Math.floor((i - 1) / 2);
    }
  }

  pop() {
    if (this.size() === 0) return null;
    if (this.size() === 1) return this.heap.pop();

    const maxV = this.heap[0];
    this.heap[0] = this.heap.pop();

    let i = 0;
    while (i < this.size()) {
      const leftI = i * 2 + 1;
      const rightI = i * 2 + 2;
      let big = leftI;
      if (rightI < this.size() && this.heap[leftI] < this.heap[rightI]) {
        big = rightI;
      }
      if (this.heap[big] > this.heap[i]) {
        this.swap(big, i);
      }
      i = big;
    }

    return maxV;
  }
}

🤔

처음에 DFS로 구현했는데, 하면서도 안 될 건 알았지만 제출하니 모두 시간초과 ㅎㅎㅎ 힌트를 보고 최대힙 방식으로 풀었다. 이전 라운드 중에서 가장 많았던 병사 수를 순차적으로 꺼내야 하니까 최대힙이 효율적이다. 힙 구현을 또 까먹어서 이전에 풀었던 문제를 참고해서 구현했다.

1. s 길이부터 1까지 감소하면서 반복
2. s를 복사한 문자열이 빈 문자열이 될 때까지 반복
3. 앞에서부터 i만큼 자른 문자열이 나오는 인덱스를 반복시킨 값의 인덱스가 0인지 검사: repeat(), indexOf()
4. 3의 반복 횟수와 자른 문자열을 새로운 문자열에 붙이고, 원본 문자열은 잘라내기
5. 문자열 길이의 최솟값 갱신

코드

function solution(s) {
  const len = s.length;
  let result = len;
  for (let i = len; i > 0; --i) {
    let copy = s;
    let tmp = '';
    while (copy) {
      let cnt = 1;
      const str = copy.slice(0, i);
      while (copy.indexOf(str.repeat(++cnt)) === 0);
      tmp += (--cnt === 1 ? '' : String(cnt)) + str;
      copy = copy.slice(i * cnt);
    }
    result = Math.min(result, tmp.length);
  }
  return result;
}

🦾

오늘도 한번에 통과 😁 별다른 알고리즘이 없어서 그냥 생각나는대로 풀면 되는 문제였다.

최단거리 BFS

• 다음 이동 위치가 게임판을 벗어나거나 D(장애물)일 때까지 이동 및 이동 횟수 +1
• 이동 후에 현재 위치가 G(목표 위치)면 종료

코드

function solution(board) {
  const [r, c] = [board.length, board[0].length];
  const dy = [-1, 0, 1, 0]; // 위 오른 아래 왼
  const dx = [0, 1, 0, -1];

  const q = [];
  for (let i = 0; i < r; ++i) {
    for (let j = 0; j < c; ++j) {
      if (board[i][j] === 'R') {
        q.push([i, j, 0]);
        break;
      }
    }
    if (q.length) break;
  }

  const visited = Array(r)
    .fill(0)
    .map(() => Array(c).fill(false));
  while (q.length) {
    const [y, x, cnt] = q.shift();
    if (board[y][x] === 'G') return cnt;
    visited[y][x] = true;
    for (let i = 0; i < 4; ++i) {
      let ny = y;
      let nx = x;
      while (true) {
        const nny = ny + dy[i];
        const nnx = nx + dx[i];
        if (
          nny < 0 ||
          nny >= r ||
          nnx < 0 ||
          nnx >= c ||
          board[nny][nnx] === 'D'
        )
          break;
        ny = nny;
        nx = nnx;
      }
      if (ny === y && nx === x) continue;
      if (visited[ny][nx]) continue;
      q.push([ny, nx, cnt + 1]);
    }
  }
  return -1;
}

🦾

우와 한번에 통과했다! 정말 뿌듯하다 😁 처음에 문제 이해가 좀 어려웠는데, G를 만나면 멈추는 게 아니라 R에서 출발하듯이 그냥 통과해서 지나간다는 걸 염두해야 한다.

1. 1번의 n개 중 n-1개를 2번으로 옮긴다. (재귀)
2. 1번의 가장 큰 n을 3번으로 옮긴다.
3. 2번의 n-1개를 3번으로 옮긴다. (재귀)

• n이 1이면 기록하고 빠져나오기

코드

function solution(n) {
  let result = [];
  const recursion = (n, src, through, dst) => {
    if (n === 1) {
      result.push([src, dst]);
      return;
    }

    recursion(n - 1, src, dst, through);
    result.push([src, dst]);
    recursion(n - 1, through, src, dst);
  };
  recursion(n, 1, 2, 3);
  return result;
}

🤔

하노이의 탑이라는 규칙 자체를 원래 잘 알고 있어야 수월하게 풀 수 있는 문제인 것 같다. 원래도 하노이의 탑 실제로 해볼 때 그냥 막 움직이면서 했던 터라... 규칙을 찾아내기가 힘들었다. 결국 다른 사람의 해설을 보고 풀어보았다. 사실 아직도 잘 이해가 안 된다...🥲 재귀를 따라서 실제로 실행해보면 맞긴 한데 어떻게 이 코드를 도출해낼 수 있었는지 너무 신기하다. 여기서 시뮬레이션해볼 수 있다.

1. 두 변 중 짧은 변이 w라고 하면 1부터 w까지 증가하면서 반복
2. 현재 반복하는 수가 x일 때 세로로 전체 직사각형 h개 중 대각선이 지나는 사각형의 수는 기울기 * x를 올림한 수 - 기울기 * (x - 1)을 버림한 수 기울기는 h / w
3. 2를 누적하면 대각선이 지나는 사각형의 수를 구할 수 있음

코드

function solution(w, h) {
  const [big, small] = [Math.max(w, h), Math.min(w, h)];
  let cnt = 0;
  for (let i = 1; i <= small; ++i) {
    cnt += Math.ceil((big * i) / small) - Math.floor((big * (i - 1)) / small);
  }
  return w * h - cnt;
}

🤔

처음에 그림 그려가면서 최대공약수로 나름 규칙을 찾았었는데, 최대공약수가 1인 경우에는 규칙이 잘 먹히지 않았다. 사람들의 힌트를 봐도 잘 이해가 안 되다가 다시 그림 그리면서 보니까 기울기 방법이 갑자기 이해가 됐다. (3, 5) 같은 경우를 그림 그리면서 해보는 걸 추천!

또 원래 기울기를 먼저 구해두고 값을 누적했는데, 테케 3개인가 통과를 못해서 찾아봤더니 나누기 연산 시에 소수점 이하 값이 정확하지 않아서 문제가 생기는 사람들이 많았다. 다른 사람 답을 참고해서 나누기를 나중에 수행했더니 통과가 돼서 이건 좀 어이가 없었다...

6월부터 프로그래머스 자바스크립트 문제를 레벨 0부터 차근차근 풀기 시작해서 드디어 오늘 1000위 안으로 들어왔다! 😁

x^2 + y^2 <= d^2인 좌표 중 k 간격을 지니는 값의 개수 구하기

• 2중 반복문은 시간 초과 발생
• d는 주어진 값이므로, x의 값을 대입해서 y의 최댓값을 알아낼 수 있음 => 반복문 하나로 해결 가능

코드

function solution(k, d) {
  let result = 0;
  for (let i = 0; i <= d; i += k) {
    const maxY = Math.trunc(Math.sqrt(d ** 2 - i ** 2));
    result += Math.trunc(maxY / k) + 1;
  }
  return result;
}

🤔

안 될 걸 알면서 일단 2중 반복문으로 풀었더니 역시나 몇 문제에 시간 초과가 났다. 사람들의 힌트를 보니 조금만 더 생각하면 풀 수 있는 문제였다. 너무 성급하게 힌트를 본 것 같아서 조금 후회했다.

1. 정렬: sort()
2. 각 튜플에 대한 S_i 구하기: map(), reduce()
3. row_begin부터 row_end까지 XOR: slice()

코드

function solution(data, col, row_begin, row_end) {
  --col, --row_begin, --row_end;
  data.sort((a, b) => a[col] - b[col] || b[0] - a[0]);
  const s = data
    .map((d, i) => d.reduce((a, c) => a + (c % (i + 1)), 0))
    .slice(row_begin, row_end + 1);
  let result = s[0];
  for (let i = 1; i < s.length; ++i) result = result ^ s[i];
  return result;
}

🦾

갑자기 너무 쉬운 문제가 나와서 조금 당황했지만 가끔 쉬어가는 날도 있어야 하니까 🐙

최단 거리 => BFS

1. 시작 위치, 레버 위치 찾기
2. 시작부터 레버까지 탐색
3. 레버부터 출구까지 탐색
4. 2 + 3의 결과 리턴

코드

function solution(maps) {
  const [row, col] = [maps.length, maps[0].length];

  const bfs = (start, dest) => {
    let q = [start];
    let visited = Array(row)
      .fill()
      .map(() => Array(col).fill(false));
    visited[start[0]][start[1]] = true;

    const dy = [-1, 0, 1, 0]; // 위 오 아래 왼
    const dx = [0, 1, 0, -1];

    while (q.length) {
      const [y, x, d] = q.shift();
      if (maps[y][x] === dest) return d;

      for (let i = 0; i < 4; ++i) {
        const ny = y + dy[i];
        const nx = x + dx[i];
        if (ny < 0 || ny >= row || nx < 0 || nx >= col) continue;
        if (maps[ny][nx] === 'X' || visited[ny][nx]) continue;
        q.push([ny, nx, d + 1]);
        visited[ny][nx] = true;
      }
    }
    return -1;
  };

  let startPos, leverPos;
  for (let i = 0; i < row; ++i) {
    for (let j = 0; j < col; ++j) {
      if (maps[i][j] === 'S') startPos = [i, j, 0];
      if (maps[i][j] === 'L') leverPos = [i, j, 0];
    }
    if (startPos && leverPos) break;
  }

  const leverCnt = bfs(startPos, 'L');
  const exitCnt = bfs(leverPos, 'E');
  if (leverCnt === -1 || exitCnt === -1) return -1;
  return leverCnt + exitCnt;
}

🦾

처음에 코드 쭉 쓰고 실행했는데 한번에 테스트 케이스를 통과해서 놀랐다. 제출했더니 시간 초과가 나서 디버깅하느라 거의 1시간 걸리긴 했지만 ㅋㅋㅋ visited 체크할 인덱스를 헷갈렸던 거였는데 찾기가 힘들었다...

1. P의 위치 모두 찾기
2. 2중 반복문 돌면서 P 좌표끼리 맨해튼 거리 비교
3. 맨해튼 거리가 2보다 큰 경우 => 성공 맨해튼 거리가 2보다 작은 경우 => 실패
4. 맨해튼 거리가 2인 경우
   • 가로로 한 칸 띄어져 있는 경우 (r1, c1 + 1)이 X면 성공 아니면 실패
   • 세로로 한 칸 띄어져 있는 경우 (r1 + 1, c1)이 X면 성공 아니면 실패
   • 대각선으로 한 칸 띄어져 있는 경우 (r1, c2)와 (r2, c1)이 모두 X면 성공 아니면 실패
5. 비교 중 하나라도 실패하면 해당 place 탐색 중단

코드

function solution(places) {
  const result = [];
  for (const place of places) {
    const ps = [];
    for (let i = 0; i < place.length; ++i) {
      for (let j = 0; j < place[0].length; ++j) {
        if (place[i][j] === 'P') ps.push([i, j]);
      }
    }

    let flag = true;
    for (let i = 0; i < ps.length - 1; ++i) {
      for (let j = i + 1; j < ps.length; ++j) {
        const [r1, c1] = ps[i];
        const [r2, c2] = ps[j];
        const d = Math.abs(r1 - r2) + Math.abs(c1 - c2);
        if (d > 2) continue;
        if (d < 2) {
          flag = false;
          break;
        }
        let partition = 1;
        if (r1 !== r2 && c1 !== c2) partition = 2;

        let cntX = 0;
        for (let y = Math.min(r1, r2); y <= Math.max(r1, r2); ++y) {
          for (let x = Math.min(c1, c2); x <= Math.max(c1, c2); ++x) {
            if (place[y][x] === 'X') ++cntX;
          }
        }
        if (partition !== cntX) flag = false;
      }
      if (!flag) break;
    }
    result.push(flag ? 1 : 0);
  }
  return result;
}

🤔

처음에 미로 찾기가 생각나서 DFS로 시도하다가 점점 복잡해져서 포기했다. 힌트를 보고 조건문으로 풀어보았다. 후 반복문 조건을 잘못 설정해서 디버깅하느라 거의 2시간이 걸렸다..

DP

1. 2번째 다음 행과 열부터 시작해서 2중 반복
2. 현재 칸이 0이 아니면 위, 대각선 왼쪽 위, 왼쪽 값의 최솟값 + 1을 채워넣기 매번 최댓값 갱신
3. 모두 완료 후 최댓값의 제곱을 리턴

코드

function solution(board) {
  let result = 0;
  const [r, c] = [board.length, board[0].length];
  if (r < 2 || c < 2) return 1;

  for (let i = 1; i < r; ++i) {
    for (let j = 1; j < c; ++j) {
      if (board[i][j] === 0) continue;
      const cnt =
        Math.min(board[i - 1][j - 1], board[i][j - 1], board[i - 1][j]) + 1;
      board[i][j] = cnt;
      if (result < cnt) result = cnt;
    }
  }
  return result ** 2;
}

🤔

어떻게 해도 시간 초과가 나서 결국 다른 사람의 풀이 참고... 혼자 힘으로 풀기 어려운 문제가 점점 더 많아지는 것 같다. 이런 것도 DP라고 한다는 걸 새로 알게 되었고, 이런 방식을 생각해낸다는 것이 대단하게 느껴졌다.

원소 수가 많아서 2중 반복문 실행 시 시간 초과 => 반복문 한 번으로 처리해야 함

1. 오름차순 정렬
2. 객체에 각 몸무게를 가진 사람의 수 저장
3. 배열에 대해 반복
4. 현재 몸무게와 짝꿍이 될 수 있는 몸무게를 가진 사람의 수만큼 결과 증가 이때 경우의 수는 1:1, 3:2, 2:1, 4:3으로 4가지 반복 끝마다 현재 몸무게의 사람 수 -1을 해주어야 다음에 중복으로 세지 않음

코드

function solution(weights) {
  weights.sort((a, b) => a - b);
  const obj = {};
  weights.forEach((w) => (obj[w] = (obj[w] || 0) + 1));

  let result = 0;
  for (const weight of weights) {
    if (obj[weight] > 1) result += obj[weight] - 1;
    if (obj[weight * (3 / 2)]) result += obj[weight * (3 / 2)];
    if (obj[weight * 2]) result += obj[weight * 2];
    if (obj[weight * (4 / 3)]) result += obj[weight * (4 / 3)];

    --obj[weight];
  }
  return result;
}

🤔

아무리 생각해도 반복문 하나로 처리하는 방법을 모르겠어서 다른 사람의 힌트 참고.. 객체를 쓸 생각을 전혀 하지 못했다.

• 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a => a는 철수 카드의 최솟값보다 같거나 작음
• 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a => a는 영희 카드의 최솟값보다 같거나 작음

1. 각 배열의 최솟값부터 시작해서 감소하면서 반복
2. 현재 배열의 모든 수를 나눌 수 있지만, 다른 배열의 수는 하나도 나누지 못하는 수가 있다면 바로 리턴 끝까지 없으면 0 리턴
3. 두 배열에 대한 결과 중 더 큰 값을 리턴

코드

function solution(arrayA, arrayB) {
  arrayA.sort((a, b) => a - b);
  arrayB.sort((a, b) => a - b);

  const findCandidate = (curr, other) => {
    for (let i = curr[0]; i > 1; --i) {
      if (curr.every((n) => n % i === 0) && !other.some((n) => n % i === 0))
        return i;
    }
    return 0;
  };
  return Math.max(findCandidate(arrayA, arrayB), findCandidate(arrayB, arrayA));
}

🤔

혼자 무식하게 풀려다 역시나 시간 초과가 나서 다른 사람의 힌트를 참고했다. 공약수 공배수 이런 개념 나오면 갑자기 취약해지는 기분... 사실 모든 경우의 수를 구해야 하는 것이 아니기 때문에 그렇게 어렵게 생각할 필요가 없는 문제였다.

다익스트라

1. 양방향 연결 상태 배열 생성, 노드까지 가는 최솟값을 저장할 배열 생성
2. DFS
3. 최솟값 배열에 담긴 값보다 현재 노드를 거쳐 우회하는 값이 더 작은 경우 최솟값 갱신 이 경우에만 큐에 담기
4. 최솟값 배열에서 값이 K보다 작은 노드의 수 리턴

처음 코드(틀린 풀이)

function solution(N, road, K) {
  const g = {};
  const times = {};
  for (const [a, b, c] of road) {
    const [key1, key2] = [a + '-' + b, b + '-' + a];
    if (!g[a]) g[a] = [];
    if (!g[b]) g[b] = [];
    g[a].push(b);
    g[b].push(a);

    if (!times[key1]) times[key1] = c;
    if (!times[key2]) times[key2] = c;
    if (times[key1] > c) times[key1] = c;
    if (times[key2] > c) times[key2] = c;
  }

  const visited = {};
  const q = [[1, 0]];
  const set = new Set();
  while (q.length) {
    const [s, t] = q.pop();
    if (visited[s] < t) continue;
    visited[s] = t;
    if (t <= K) set.add(s);
    if (set.size === N) break;
    for (const n of g[s]) {
      q.push([n, t + times[s + '-' + n]]);
    }
  }
  return set.size;
}

어찌어찌 DFS로 했더니 될 듯 말 듯 했다. 27번 테스트 케이스만 시간 초과가 나서 이것저것 해보다가 결국 포기했다.

정답 코드

function solution(N, road, K) {
  const g = Array.from(Array(N + 1), () => []);
  const arr = Array(N + 1).fill(Infinity);

  for (const [a, b, c] of road) {
    g[a].push({ to: b, cost: c });
    g[b].push({ to: a, cost: c });
  }

  const q = [{ to: 1, cost: 0 }];
  arr[1] = 0;
  while (q.length) {
    const { to, cost } = q.pop();
    for (const next of g[to]) {
      const tmp = arr[to] + next.cost;
      if (arr[next.to] < tmp) continue;
      arr[next.to] = tmp;
      q.push(next);
    }
  }

  return arr.filter((c) => c <= K).length;
}

결국 다른 사람의 풀이를 참고했다.

🦾

• 다익스트라 알고리즘 각 배열에 다음 노드와 가중치를 저장해둔다. 각 노드까지 도달하는 최솟값 배열을 만든다. 큐에는 해당 노드까지 가는 최솟값과 우회하는 값 중 작은 값을 담는다.
• Array.from(배열, map 함수)로 초기화된 배열을 더 쉽게 생성할 수 있다는 것도 알게 됐다.

1. 경우의 수 구하기: 팩토리얼 함수
2. 각 구간을 n으로 나눠서 k가 몇 번째 구간에 들어가는지 찾기

코드

function solution(n, k) {
  const arr = Array(n)
    .fill(0)
    .map((_, i) => i + 1);
  let result = [];
  while (result.length !== n) {
    const part = factorial(arr.length) / arr.length;
    const i = Math.ceil(k / part) - 1;
    result.push(arr[i]);
    arr.splice(i, 1);
    k -= part * i;
  }
  return result;
}

function factorial(n) {
  if (n < 2) return 1;
  return n * factorial(n - 1);
}

🦾

처음에 재귀로 풀었더니 효율성 테스트에서 탈락해서 힌트를 보고 구간을 나누어 풀었다.

1. 작은 자릿수부터 시작해서 숫자를 올림 또는 버림하면서 반복
2. 현재 자릿수가 5 보다 큰 경우 올림 현재 단위 버튼 누르는 수는 현재 단위 - 현재 자리의 수
3. 현재 자릿수가 5보다 작은 경우 버림 현재 단위 버튼 누르는 수는 현재 자리의 수만큼
4. 현재 자릿수가 5인 경우에는 다음 자릿수가 5 이상이면 올림, 아니면 버림

코드

function solution(storey) {
  const arr = [0, ...String(storey)].map(Number);
  let result = 0;
  for (let i = arr.length - 1; i >= 0; --i) {
    if (arr[i] > 5) {
      ++arr[i - 1];
      result += 10 - arr[i];
    } else if (arr[i] === 5 && i > 0) {
      if (arr[i - 1] >= 5) {
        ++arr[i - 1];
        result += 10 - arr[i];
      } else {
        result += arr[i];
      }
    } else {
      result += arr[i];
    }
  }
  return result;
}

🤔

난이도 순으로 치면 매번 푸는 문제가 지금까지 가장 어려운 문제가 맡긴 한데 진짜 어려웠다. 이래저래 노가다 하다가 사람들 힌트를 보고 올림, 버림 개념으로 푸는데도 못 통과하는 테스트 케이스 수두룩... 탐색하는 인덱스가 0일 때 예외가 생길 수 있기 때문에 그걸 신경써주어야 했다.