유진수

문제

백준 1356번 - 유진수

언어

JavaScript

순서도

앞부분 자리수의 곱과 뒷부분 자리수의 곱의 모든 경우를 만들어보기
앞부분 자리수의 곱과 뒷부분 자리수의 곱이 같은 경우가 있다면 “YES” 출력, 없다면 “NO” 출력

문제 풀이 step 1

유진수는 어떤 수를 10 진수로 표현한 뒤 그 수를 두 부분으로 나눴을 때, 앞부분 자리수의 곱과 뒷부분 자리수의 곱이 같을 때를 말합니다.
예를 들어, 1221 은 유진수입니다. 12 와 21 로 나눴을 때, 앞부분 자리수의 곱 1 * 2 는 뒷부분 자리수의 곱 2 * 1 과 같기 때문입니다.
1236 도 마찬가지로 유진수입니다. 하지만, 1234 는 아닙니다.
수를 나눌 때 항상 연속된 자리수를 나눠야하고, 각 부분에 적어도 한자리는 있어야 합니다.
예를 들어, 12345 는 총 4 가지 방법으로 나눌 수 있습니다. (1-2345, 12-345, 123-45, 1234-5)
어떤 수 N 이 주어질 때, 이 수가 유진수인지 아닌지 구하는 문제입니다.

문제 풀이 step 2

문제에서 나온 예시처럼 주어진 수를 나눌 수 있는 모든 경우를 나눠봅니다.
그리고 모든 경우의 앞부분 자리수의 곱과 뒷부분 자리수의 곱이 같은지 검사하고, 같다면 “YES” 를 출력, 다르다면 “NO” 를 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

요즘 알고리즘을 풀면서 느끼는게 있습니다.
조금이라도 반복을 줄여서 더 빠른 로직을 구현하려고 하면 틀리는 경우가 생깁니다. 그 이유는 반례가 아닌 경우가 반례가 되어버리기 때문입니다.
- 위의 문제도 반복을 줄이기 위해서 전체 곱을 구해놓고 수열을 순회하며, 각 자리의 수를 앞부분 자리수의 곱에 곱하고, 뒷부분 자리수의 곱에서 나눠가며 검사를 진행했습니다.
  - 이렇게 하면 시간복잡도가 O(N) 이 나오게 됩니다. 하지만 이 경우 “1001” 과 같은 수는 0 으로 나누기 연산을 하게 되기 때문에 잘못된 결과를 도출합니다.
- 반면에, 각 경우를 만들고 매번 반복문을 통해서 곱셈을 해주면, 시간 복잡도는 O(N^2) 이지만, 저런 반례가 생기지 않게 됩니다.
방향을 바꿔야겠습니다. 시간과 메모리가 충분하다면, 솔직하고 정석적인 로직을 구현하는 것을 지향해야겠습니다.
딜레마에 빠지게 된 것 같아서 흔들리네요.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const numsArr = String(Number(input[0])).split("").map(Number);

	for (let i = 0; i < numsArr.length - 1; i++) {
		let [left, right] = [1, 1];

		for (let j = 0; j < i + 1; j++) left *= numsArr[j];
		for (let j = i + 1; j < numsArr.length; j++) right *= numsArr[j];

		if (left === right) return "YES";
	}

	return "NO";
};

console.log(solution(input));