쉔은 회전 초밥집에 갔습니다.
초밥집에 간 쉔은 각 초밥에 점수를 매기고 낮은 점수의 순서로 초밥을 먹으려 합니다.
이때 n위치에 놓여진 초밥을 먹고자 할 때 접시가 몇 번 지나가고 먹을 수 있을지 출력하세요.
- 초밥은 놓여진 위치에서 옮겨지지 않습니다.
- 지나간 초밥은 나머지 초밥이 지나간 후에 다시 돌아옵니다.
- 초밥은 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로 바꿔주었다.
인덱스에 대한 생각만 잘 한다면 크게 어려울것 없는 문제였다.
'PS > 제코베 JS 100제' 카테고리의 다른 글
제코베 JS 100제 / 88 / 지식이의 게임 개발 (1) | 2022.09.30 |
---|---|
제코베 JS 100제 / 87 / 천하제일 먹기 대회 (1) | 2022.09.30 |
제코베 JS 100제 / 85 / 숫자놀이 (0) | 2022.09.29 |
제코베 JS 100제 / 84 / 숫자뽑기 (0) | 2022.09.29 |