내가 푼 코드
- 첫번째는 역시 실패
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');
let answer = '';
let [N, K] = input[0].split(' ').map(x=>+x);
let arr = [];
for(let i=1; i <= N; i++) {
arr.push(i);
}
let index = 0;
while(true) {
if(arr.length >= K) {
index = (index + K-1) > arr.length-1 ? (index + K-1) - arr.length : (index + K-1);
} else {
index = (0 + K-1) > arr.length-1 ? (0 + K-1) - arr.length : (0 + K-1);
}
answer += arr[index] + ', ';
arr.splice(index,1);
if(index === 0) {
answer += arr[0];
arr.splice(index,1);
break;
}
}
answer = '<' + answer + '>'
console.log(answer);index계산을 이상하게 했다. arr의길이가 K보다 작을 때를 잘못작성.
- 제대로 됨! 근데 외않되?
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');
let answer = '';
let [N, K] = input[0].split(' ').map(x=>+x);
let arr = [];
for(let i=1; i <= N; i++) {
arr.push(i);
}
let index = 0;
while(arr.length !== 0) {
if(arr.length >= K) {
index = (index + K-1) > arr.length-1 ? (index + K-1) - arr.length : (index + K-1);
} else {
index = (index + K-1) % arr.length;
}
answer += arr[index] + ', ';
arr.splice(index,1);
}
answer = '<' + answer + '>'
console.log(answer);바로 출력이 거지같이 됐기 때문! <1,1,1> 가 아니라 <1,1,1,> 이렇게 출력됨..^^
- 진짜 최종
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');
let answer = [];
let [N, K] = input[0].split(' ').map(x=>+x);
let arr = [];
for(let i=1; i <= N; i++) {
arr.push(i);
}
let index = 0;
while(arr.length !== 0) {
if(arr.length >= K) {
index = (index + K-1) > arr.length-1 ? (index + K-1) - arr.length : (index + K-1);
} else {
index = (index + K-1) % arr.length;
}
answer.push(arr[index]);
arr.splice(index,1);
}
console.log(`<${answer.join(', ')}>`);출력만 고치면 되는 것이라 바로 구글링함. join이 은근 헷갈리는데 이참에 정리 타임 가지자.
🔑 arr의 배열이 K보다 작아졌을때와 아닐때를 구분해서 푸는 것이 관건이였다.
K보다 클때는 몇번째가 아닌 index인 것을 감안해 index + K -1 or (index + K -1) - arr.length 그리고 K보다 작을 때, 특정 배열안에서 계속 숫자가 도는 상황이 발생한다. 이때 숫자 % 배열크기 이렇게 하면 숫자의 인덱스 값이 나온다!!
2022-04-27 복습
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');
let answer = [];
let [N, K] = input[0].split(' ').map(x=>+x);
let arr = [];
for(let i=0; i < N; i++) {
arr.push(i+1);
}
let x =0;
while(arr.length !== 0) {
x = ((x+K-1)%arr.length);
let smallArr = arr.splice(x, 1)[0];
answer.push(smallArr);
}
console.log(`<${answer.join(', ')}>`);구분해서 풀지 않아도되는 방법을 찾았다.
그리고 x = ((x+K)%arr.length) - 1로 했을때 오류가 났다. 이유는 ((1+3)%4) - 1같은 경우일때 발생했다. -1을 x+K괄호 안에 넣어야 제대로 작동했다.
arr배열이 빈배열이 될때까지 x+K-1에 배열의 길이로 나눈 나머지가 index가 된다. 한배열을 일정 규칙대로 돌아가며 해당하는 index를 구하고싶을때 num%배열길이 를 하면된다.
다른 사람 풀이
- 문제 의도와 부합한 풀이
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');
let [N, K] = input[0].split(' ').map(x=>+x);
const arr = new Array(N).fill(0).map((el, i) => i + 1);
let x =0;
let answer = "<";
while (arr.length) {
for (let i = 0; i < K; i++) {
arr.push(arr.shift());
}
console.log(arr);
if (arr.length === 1) {
answer += `${arr.pop()}>`;
} else {
answer += `${arr.pop()}, `;
}
}
console.log(answer);파란색: push해준 수
pop해준 수(=push해준 마지막 수)
4,5,6,7,1,2,3
7,1,24,5,6
4,5,7,1,2
1,4,5,7
1,45
4,1
4
K만큼 뽑아서 앞에서 뽑아서 arr에 push해주고 pop으로 뽑아서 answer에 더해준다. 와우
위: 이 코드
아래: 복습에서 쓴 코드
shift를 사용해서 느린감이 있다. 하지만 이렇게 푸는게 문제의 의도에 맞는 풀이같다. 알고리즘 분류가 자료구조,큐니까.
- 큐
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');
let [N, K] = input[0].split(' ').map(x=>+x);
const queue = new Array(N).fill(0).map((el, i) => i + 1);
const answer = [];
let count = 1;
while(queue.length) {
const shiftItem = queue.shift();
if(count % K === 0) {
answer.push(shiftItem);
} else {
queue.push(shiftItem);
}
count++;
}
console.log(`<${answer.join(', ')}>`);1부터N까지의 값을 가지는 배열 queue를 만들고 이 배열이 빈배열이 될때까지 while문을 돌린다. 큐에서 하나빼주고(큐니까 선입선출)count가 K번째가 맞을때 answer에 push 아니라면 큐배열에 push. 색으로 나타낸 과정과 같게나온다.
