문제
정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다.
정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.
왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시 계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다.
이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.
예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 왕자가 3 을 외쳐 제외된다. 이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고 마지막까지 남게 된 7 번 왕자에게 공주를 구하러갑니다.
N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램을 작성하시오.
[입력설명]
첫 줄에 자연수 N(5<=N<=1,000)과 K(2<=K<=9)가 주어진다.
[출력설명]
첫 줄에 마지막 남은 왕자의 번호를 출력합니다.
입력예제 1
8 3
출력예제 1
7
문제 풀이
예습이론
- queue(큐)는 배열로써, 앞에서 살펴본 stack과 달리 FIFO구조이다. 즉, 선입선출이다.
queue.shift()를 통해 배열 가장 앞에 있는 원소를 꺼낼 수 있으며,
queue.push(queue.shift())은 가장 앞에 있는 원소를 꺼내서 가장 뒤에 삽입한다.
- let queue=Array.from({length:n}, (v, i)=>i+1)은 length가 n인 유사배열을 생성한다. 이때 v는 value, i는 index이다. i+1은 return v=i+1로 생각하면 된다.
코드
큐를 사용해서 풀 수 있는 문제이다. 큐에 대해서는 위 예습이론을 참고하자. 1~k-1까지 부른 왕자는 살아남고(push&shift), k를 부른 왕자는 탈락이다.(shift)
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(n, k){
let answer;
let queue=Array.from({length:n}, (v, i)=>i+1); //길이가 n인 유사배열 객체 만듦, 왕자들 queue에 있음
while(queue.length){
for(let i=1; i<k; i++) queue.push(queue.shift()); //1부터 k전까지 번호 외치는 코드! 1,2번 왕자는 제외 후 push(i는 인덱스 번호x)
queue.shift(); //3번왕자는 그냥 제외됨
if(queue.length===1) answer=queue.shift();
}
return answer;
}
console.log(solution(8, 3));
</script>
</body>
</html>
9/13
유사배열을 통해 큐 생성하기