제코베 JS 100제 / 86 / 회전 초밥

쉔은 회전 초밥집에 갔습니다.

초밥집에 간 쉔은 각 초밥에 점수를 매기고 낮은 점수의 순서로 초밥을 먹으려 합니다.

이때 n위치에 놓여진 초밥을 먹고자 할 때 접시가 몇 번 지나가고 먹을 수 있을지 출력하세요.

 

1.  초밥은 놓여진 위치에서 옮겨지지 않습니다.
2. 지나간 초밥은 나머지 초밥이 지나간 후에 다시 돌아옵니다.
3. 초밥은 1개 이상 존재합니다.

 

예)

A, B, C, D, E 초밥이 있고 각 점수가 1, 1, 3, 2, 5 일 때 3번째(C초밥)을 먹게 되는 순서는

점수가 1인 초밥 A와 B를 먹고 다음으로 점수가 2인 D 초밥을 먹어야

A B C D E 순서로 접시가 도착하지만 C가 도착했을때 먹지 못하는 상황이 옵니다.

2점을 주었던 D를 먼저 먹어야 C를 먹을 수 있습니다.

즉, A B C D E C 의 순서로 접시가 5번 지나가고 먹게 된다.

 

/**
 * 점수 배열인 point에서 낮은 점수의 순서로 초밥을 먹는데,
 * dish번째 초밥을 먹고자 할 때
 * 접시가 몇 번 지나가고 먹을 수 있을지 반환하는 함수
 *
 * @param {Number[]} point 각 초밥의 점수
 * @param {Number} dish 위치
 * @returns {Number} 접시가 지나간 횟수
 */
function getHowManyPassedDishes(point, dish) {
  let idx = 0;
  let cnt = -1;
  let min = Math.min(...point);
  while (true) {
    // 회전해서 맨 끝 인덱스 다음은 맨 처음 인덱스가 와야 한다.
    // Circular Queue의 인덱스 참조처럼 인덱스 접근.
    idx = idx % point.length;

    // 이미 먹은 초밥(Infinity)이 아닐경우 +1을 해준다.
    // (먹은 초밥은 카운트 하지 않기때문에)
    if (point[idx] !== Infinity) cnt += 1;

    // 현재 인덱스의 값이 최솟값이라면,
    if (point[idx] === min) {
      // 현재 값을 무한대로 바꿔주고
      point[idx] = Infinity;
      // 다시 최솟값을 구한다.
      // 가장 낮은 점수의 초밥을 먹었기 때문에 무한대로 바꿔주어서
      // 그 다음 최솟값을 구하는 과정이다.
      min = Math.min(...point);

      // 문제에서 dish는 0이 아니라 1부터 시작한다.
      if (idx + 1 === dish) return cnt;
    }

    idx += 1;
  }
}

const point = [5, 2, 3, 1, 2, 5];
const dish = 1;

const result = getHowManyPassedDishes(point, dish);

console.log(result); // 10

---

내가 푼 방법에서 이 문제의 핵심은 아무래도 인덱스에 대한 접근이 아닐까 싶다.

끝에서 다시 처음으로 돌아와야 하기 때문에 마치 원형 큐가 생각났다.

그래서 인덱스 접근을 똑같이 modular 연산자를 통해 원형 큐 처럼 구현했다.

 

그리고 가장 작은 점수를 가진 초밥을 먹었다면 그 다음 가장 낮은 점수를 찾아야 하기 때문에,

이미 먹은 초밥은 Infinity로 바꿔주었다.

 

인덱스에 대한 생각만 잘 한다면 크게 어려울것 없는 문제였다.