[백준] 카드2 (Node.js)

문제 풀고 다른 분들은 어떻게 풀었을까 하고 봤는데

이렇게도 풀 수 있다는 걸 알게되어 신선한 충격을 받아 작성했습니다

 

문제 - https://www.acmicpc.net/problem/2164

2164번: 카드2

 

- 문제 풀이는 굉장히 간단하게 접근할 수 있습니다.

  1. (index + 1)의 값이 저장된 n 만큼의 배열을 만들고

  2. while 문을 돌려 (index % 2 === 1) 이면 배열에 해당 값을 push 해주고 인덱스 값을 늘려서 확인.

  3. index가 arr.length 보다 커지면 배열의 마지막 값을 출력.

어느 쪽으로 풀이를 접근하든 배열 값을 확인하고 push 해주는 것이 가장 일반적인 접근입니다.

( arr.push(arr.shift()) 로 진행할경우 시간초과 됨 )

 

다만 위와 같은 형태로 하게되면 n이 500000일때

배열의 총 길이는 999999가 됩니다.

물론 문제 푸는데는 아무런 지장이 없긴 합니다.

 

다만 위 문제에서 규칙을 찾는다면

n	answer	role
1	1	1
1, 2	2	2
1, 2, 3	2	(3-2) * 2
1, 2, 3, 4	4	4
1, 2, 3, 4, 5	2	(5-4) * 2
1, 2, 3, 4, 5, 6	4	(6-4) * 2
1, 2, 3, 4, 5, 6, 7	6	(7-4) * 3
1, 2, 3, 4, 5, 6, 7, 8	8	8
1, 2, 3, 4, 5, 6, 7, 8, 9	2	(9-8) * 2
1, 2, 3, 4, 5, 6, 7, 8, 9, 10	4	(10-8) * 2
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11	6	(11-8) * 2
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12	8	(12-8) * 2
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13	10	(13-8) * 2

 

규칙이 보이시나요??

1. n이 2^x 일 경우 값은 n

2. (n - (n보다 작은 2^x)) * 2

 

2진법만 알면 배열이고 뭐고 다 필요없이

굉장히 쉽게 풀수 있는 문제였습니다.

 

그러면 문제를 쉽게 풀어봅시다.

 

- 답안 (참고용)

const n = Number(require('fs').readFileSync('dev/stdin'))

const solution = (n) => {
	//숫자를 2진법으로 변환
	const binArr = n.toString(2).split("");
    
    	//n보다 작은 2^x 값 빼기 
	binArr.shift();
    
	//남은수 10진법으로 변환
	const answer = parseInt(binArr.join(""), 2);
    
    //answer가 0이면 그 수는 2^x 이므로 n
    return answer ? answer * 2 : n;
}

console.log(solution(n));