백준 1193번: 분수찾기(Find Fraction) Node.js(JavaScript)

https://www.acmicpc.net/problem/1193

Code

제출 코드(머릿속으로 이해가 끝난 후)

 

제출 코드(직관적으로 보기 좋은 코드)

😢 어떻게 빠르게 해당 집단을 찾아낼 것인지, 해당 집안에서 정답을 어떻게 도출할 것인지가 핵심

😊 2번째 제출코드를 먼저 보면 이해하기 편하다.

다음 표는 지그재그 순서로 진행하는 분수를 더 보기 편하게 정리한 것이다.

1/1
1/2	2/1
3/1	2/2	1/3
1/4	2/3	3/2	4/1
5/1	4/2	3/3	2/4	1/5
...	...	...	...	...	...

분모는 짝수일 때, 오름차순으로(1 2 3 4 5...) 숫자가 진행되는 것을 알 수 있고,
분자는 짝수일 때, 내림차순으로(5 4 3 2 ...) 숫자가 진행되는 것을 알 수 있다. 홀수는 그 반대다.

패턴을 파악했으니, 어떻게 답을 찾아낼 지 생각해보자.

먼저, 최대로 입력받을 수 있는 수의 크기는 10,000,000이므로 배열이나 테이블로 만드는 건 시간 초과가 날 것이다.
따라서, 찾고자하는 X번을 포함하고 있는 그룹을 찾고, 그 그룹 안에서 X번째 분모/분자 값을 찾아내야 한다.

1/1부터 시작한다고 생각할 때, 해당 그룹의 분수 개수는 1부터 1씩 증가한다.
그룹 개수가 증가할 때마다 입력 받은 X에서 그룹을 빼주면 해당 그룹에 도달했을 때, X는 0 또는 음수가 된다.
위 과정을 while문에서 진행해주면 된다.

여기서 중요한 것은 groupCounter가 곧 해당 그룹의 분수 개수라는 것이다. 이 것을 기억하고 다음 단계로 넘어가보자.

이제 if (group % 2 === 0)을 이용해서 짝수일때, 분모 출력을 groupCounter + X 로 해주면
해당 그룹의 끝 기준으로 자신의 순번을 찾는다.(12345 처럼 오름차순 기준이기 때문)
그리고 분자는 1 + (-X) 를 해주면 역시 그룹의 끝 기준으로 자신의 순번을 찾는다.( 54321처럼 내림차순이기 때문)

예를 들어 11번째 분수를 찾아보자.

while(X > 0){} 코드를 통해 groupCounter는 5, X는 -4라는 것을 알아낼 수 있다.
그룹은 5번째이므로 홀수이기 때문에, 분모는 내림차순, 분자는 오름차순이다.
분모 그룹은 54321
분자 그룹은 12345
이며 분모는 1+ -(-4) = 5이므로, 5번째 그룹의 1번째 수이며,
분자는 5 + (-4) = 1이므로, 역시 5번째 그룹의 1번째 수다.

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)

// Find Fraction

// 1st Solution

// For submit

// const fs = require('fs');

// const X = Number(fs.readFileSync('/dev/stdin').toString().trim());

// For local test

let X = 14;

let counter = 0;

while (X > 0) {

counter++;

X = X - counter;

}

if (counter % 2 === 0) {

console.log(`${counter + X}/${1 + -X}`);

} else {

console.log(`${1 + -X}/${counter + X}`);

}

// 2nd Solution

// For submit

// const fs = require('fs');

// let X = Number(fs.readFileSync('/dev/stdin').toString().trim());

// For local test

// let X = 11;

// let groupCounter = 0;

// let ascendingNumArr = [];

// let descendingNumArr = [];

// while (X > 0) {

// groupCounter++;

// X = X - groupCounter;

// }

// for (let i = 0; i < groupCounter; i++) {

// ascendingNumArr.push(i + 1);

// descendingNumArr.push(groupCounter - i);

// }

// if (groupCounter % 2 === 0) {

// console.log(

// `${ascendingNumArr[groupCounter - 1 + X]}/${

// descendingNumArr[groupCounter - 1 + X]

// }`

// );

// } else {

// console.log(

// `${descendingNumArr[groupCounter - 1 + X]}/${

// ascendingNumArr[groupCounter - 1 + X]

// }

// `

// );

// }