문제
용태와 유진이가 재미있는 소수 부르기 게임을 하려고 한다. 게임의 진행은 다음과 같다.
용태가 부를 소수의 범위 A, B를 정한다. 용태는 A 이상 B 이하의 소수만 부를 수 있다.
유진이가 부를 소수의 범위 C, D를 정한다. 유진이는 C 이상 D 이하의 소수만 부를 수 있다.
용태부터 시작해서 서로 번갈아가면서 자신이 부를 수 있는 범위의 소수를 부른다. 단, 지금까지 게임에서 아무도 부르지 않은 소수를 불러야 한다.
더 이상 소수를 부를 수 없는 사람이 패배한다.
용태와 유진이가 부를 수 있는 소수의 범위가 주어졌을 때, 용태와 유진이가 모두 최선을 다해 게임을 플레이한다면 누가 이기게 될까?
입력
첫째 줄에 용태가 부를 소수의 범위인 정수
A, B(2 ≤ A ≤ B ≤ 1,000)가 주어진다.
둘째 줄에 유진이가 부를 소수의 범위인 정수
C, D(2 ≤ C ≤ D ≤ 1,000)가 주어진다.
출력
용태와 유진이가 모두 최선을 다해 플레이했을 때 용태가 이기게 된다면 yt를, 유진이가 이긴다면 yj를 출력한다.
예제 입력
2 3
5 11
예제 출력
yj
내가 했던 풀이 방법
- 유진이와 용태가 부를 수 있는 소수를 구한 뒤, 겹치는 소수를 제외한 개수를 비교하여 출력 (같을 경우, 유진이가 승리한다.) -> 실패 (겹치는 소수의 개수에 따라 다름을 파악함)
2-1. 유진이와 용태가 부를 수 있는 수 A, B, C, D를 num 배열에 넣은 뒤, max값과 min값을 찾는다.
2-2. min값을 start로 max를 end로 하는 소수를 all_prime에 저장한다. 소수를 계산하는 방법은 에라토스테네스의 체 방법을 이용하여 계산하였다. 계산은 범위 내에서가 아닌 1부터 end까지 계산하며, 반환하는 result(소수)에는 start값 이상일 경우에만 push하도록 하였다. 소수를 계산하는 방법에 대한 자세한 풀이는 프로그래머스, 소수 찾기를 참고하자.
2-3. YT_prime과 YJ_prime, nesting 배열을 초기화해준다. 각 배열은 순서대로 용태의 소수, 유진의 소수, 중복된 소수이다. YT, YJ에는 중복된 소수는 포함하지 않고 들어간다. 즉, 본인만 부를 수 있는 소수가 들어간다. all_prime 배열을 순환하면서 YT의 범위에 들어가는 경우, YJ에 범위에 들어가지 않으면 YT_prime에 넣고, YJ 범위에 들어간다면 nesting에 넣어준다. YJ도 같은 방법으로 진행하지만, nesting은 YT와 같으므로, 수행하지 않는다.
2-4. YT_prime과 YJ_prime의 length를 비교했을 때 더 큰 사람이 승리한다. 같을 경우, nesting의 개수에 따라 변한다. 만약, nesting이 짝수일 경우 유진이가 승리하고 홀수일 경우 용태가 승리한다. (짝수(2개)일 경우, 용태-유진이 똑같은 횟수로 말하므로, 마지막으로 말한 유진이 승리하게 되는 것이다.)
코드
const fs = require('fs');
let [YT, YJ] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');
YT = YT.trim().split(' ');
YJ = YJ.trim().split(' ');
let max = 0;
let min = 1001;
let num = [parseInt(YT[0]), parseInt(YT[1]), parseInt(YJ[0]), parseInt(YJ[1])];
for (let i = 0; i < num.length; i++) {
if (max < num[i]) max = num[i];
if (min > num[i]) min = num[i];
}
let all_prime = prime(min, max);
let YT_prime = [];
let YJ_prime = [];
let nesting = [];
for (let i = 0; i < all_prime.length; i++) {
if (all_prime[i] >= num[0] && all_prime[i] <= num[1]) {
if (!(all_prime[i] >= num[2] && all_prime[i] <= num[3])) {
YT_prime.push(all_prime[i]);
} else {
nesting.push(all_prime[i]);
}
}
if (all_prime[i] >= num[2] && all_prime[i] <= num[3]) {
if (!(all_prime[i] >= num[0] && all_prime[i] <= num[1])) YJ_prime.push(all_prime[i]);
}
}
if (YT_prime.length > YJ_prime.length) {
console.log('yt');
} else if (YT_prime.length < YJ_prime.length) {
console.log('yj');
} else {
if (nesting.length % 2 === 0) {
console.log('yj');
} else {
console.log('yt');
}
}
function prime(start, end) {
let prime = Array.from({ length: end + 1 }, () => true);
let result = [];
prime[0] = false;
prime[1] = false;
for (let i = 2; i <= end; i++) {
if (prime[i]) {
if (i >= start) result.push(i);
for (let j = i * 2; j <= end; j += i) {
prime[j] = false;
}
}
}
return result;
}
회고
딱 보자마자 알고리즘이 생각나서 구현을 해봤는데 생각보다 신경써주어야 할 게 많아서 계속 추가되고 추가되게 되었다. 원래는 둘의 소수를 비교하려고 했는데, "지금까지 게임에서 아무도 부르지 않은 소수를 불러야 한다."라는 조건 때문에 중첩된 소수를 신경쓰게 되었다. 그래서 중첩된 소수를 그냥 무시하는 방법으로 풀이했는데 틀린 답이 나오게 된 것이다.. 제출하자마자 중첩된 소수 개수에 따라 영향을 받지 않나?라는 생각이 들어 그렇게 코드를 수정하니 정답이 되었다. (조금만 더 일찍 생각하지..) 제출하면서 중간점검용으로 작성한 코드들이 삭제되지 않고 제출돼서 몇 번 쓸데없이 틀렸습니다를 만들었다. (심지어 다른 문제에 제출해버려서 맞은 문제에 이상한 코드를 제출하기도..) 틀린게 잘못은 아니지만 최소화하고 싶었는데 자꾸 이런 말도 안 되는 실수를 하니...ㅜㅜ 그래도 이번 문제를 스스로 풀이한 게 뿌듯하구만.
