최근 다시 알고리즘 문제 풀이를 다시 시작했다.
알고리즘을 다시 시작한 이유에는 여러가지가 있지만 알고리즘을 풀이하는 것은 서비스를 개발하는 것과는 또 다른 재미가 있어서 최근에 즐겁게 문제를 풀고 있다.
한동안 알고리즘에 손을 놓았기 때문에 당분간은 백준의 단계별로 풀이를 하나씩 풀어보려고 하고 있는데 오늘은 Brute Force에 있는 문제 중 개인적으로 재밌기도 했고, 엉뚱한 삽질을 했던 2231번 풀이를 적어보려고 한다.
문제 설명
해당 문제는 위에서 언급했듯 Brute Force를 이용한 문제이다. (https://www.acmicpc.net/problem/2231)
문제의 조건은 다음과 같다.
- 분해합 N은 1 ≤ N ≤ 1,000,000으로 주어진다.
- N의 가장 작은 생성자를 출력한다.
- 생성자가 존재하지 않을 경우 0을 출력한다.
Brute Force, 흔히 완전탐색으로 여겨지는 문제답게 1부터 N까지 루프를 순회하며 부분합을 구하고, 부분합이 N과 같은 숫자, 즉 생성자를 구하면 되는 문제이다.
루프를 1부터 순회하기 때문에 가장 먼저 N과 일치하는 부분합을 가진 숫자가 바로 문제에서 요구하는 N의 가장 작은 생성자가 된다.
코드
const fs = require('fs');
const input = fs
.readFileSync("/dev/stdin", "utf8")
.toString()
.trim();
const number = parseInt(input, 10);
let result = 1;
for (let i = 1; i < number; i++) {
result = i;
const stringValue = i.toString();
for (let j = 0; j < stringValue.length; j++) {
result += parseInt(stringValue[j], 10);
}
if (result === number) {
console.log(i);
return;
}
}
console.log(0);
풀이는 위에서 설명했던 그대로 굉장히 간단하다.
1부터 입력으로 주어진 N만큼 루프를 돌며, 해당 숫자의 부분합을 구하고, 부분합이 N과 일치한다면 해당 숫자가 N의 가장 작은 생성자가 된다.
작년에 취업 준비를 하며 코딩테스트를 준비할 때는 파이썬을 주로 사용했었는데, 현재는 TypeScript를 사용하여 개발을 하고 있기 때문에 익숙한 JavaScript로 문제를 풀었다.
하지만 프로그래머스나 릿코드와 같이 입력이 주어지는 함수를 구현할 경우에는 문제가 없지만 백준이나 코드업처럼 입출력을 직접 구현해야 하는 경우에 NodeJS 런타임을 이용하는 것은 굉장히 불편한 것 같다.
필자 또한 로컬에서 fs로 입출력을 제어하기에는 불편하기 때문에 동일한 로직을 가진 가상의 입력으로 구성된 함수로 코드를 실행시켰었는데 실제 제출한 코드에서는 분기문에 들어 갔을 때 프로그램을 종료하지 않아 예제를 실행한 경우 0, 198, 207이 나란히 출력되어 여러번 실패했었다.
따라서 백준 같은 곳에서 NodeJS 런타임을 사용할 경우 fs 보다는 readline을 사용하는 것이 더 편할 수 있다.
하지만 readline 스트림을 사용할 경우 백준에서는 EOF가 발생해야 close 이벤트가 실행되기 때문에 시간 초과에 걸릴 수 있다.
코딩 테스트를 준비한다면 가장 자신있는 언어로 하는게 맞지만 그게 JavaScript라면 백준 문제에서는 조금의 귀찮음과 고생을 할 수 밖에 없을 것 같다. (will be back python....?)
마지막으로 꿀팁은 인풋을 처리할 때 꼭 trim을 사용하자! (마지막에 공백이 붙는 경우가 더러있다.)
안녕하세요. 평범한 대학생 개발자 yorr입니다.
포스팅을 읽고 궁금한 점 또는 문의가 있으신 분은 메일 또는 댓글을 남겨주세요.
Mail: twysg@likelion.org
Github: https://github.com/sangyeol-kim