백준 - 크게 만들기(2812번)
정답 비율에 겁먹지 말자는 생각으로 선정하게 된 문제이다.
다양한 방법을 시도해보았으나 스택으로 풀이하는 문제였다.
코드 설계
문제 해결의 단계는 아래와 같다.
N으로 숫자의 길이,K로 지워야할 숫자의 갯수를 받는다.numArr에 숫자를 한자리씩 배열로 저장한다.counter로 지워야할 남은 갯수를 센다. 초기값은K로 설정한다.stack배열을 생성한다.numArr에 있는digit의 갯수 동안 반복한다.- 이때
stack의 길이가 0보다 크고,stack의 마지막 요소가 새로 들어올digit보다 작으면서counter가 0보다 크다면stack에서 pop을 하며counter를 감소시킨다. - 만약 하나라도 만족하지 않는다면
digit값을stack에 push한다. stack에 남은 갯수가 지워져야할만큼(N-K만큼) 지워지지 않았다면, 반복하며 pop을 통해 지운다.
제출한 답
const input = require("fs")
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
.toString()
.trim()
.split("\n")
.map((el) => el.split(" "));
const N = Number(input[0][0]);
const K = Number(input[0][1]);
let counter = K;
let numArr = Array.from(input[1][0]);
let stack = [];
for(let digit of numArr){
while(stack.length && stack[stack.length - 1] < digit && counter){
stack.pop();
counter--;
}
stack.push(digit);
}
while(stack.length > N-K){
stack.pop();
}
console.log(stack.join(''));
시행착오 1
처음 생각했던 방식은 처음 숫자부터 K번째의 숫자까지 중에서 가장 작은 값을 선택하여 삭제하는 방식을 택했다.
예를들어 입력값이
4 2
1924로 들어온다면 [1,9,2,4] 중에서 첫번째 숫자를 제외한 제일 앞 두자리인 [1, 9, 2] 중에서 가장 작은 수인 1을 삭제한다. 아직 삭제할 횟수가 남았으므로 [9, 2, 4] 중 [9, 2] 중 가장 작은 수인 2를 삭제한다. 그러면 최종적으로 [9, 4]가 남게된다.
이 방식은 예제로 제시된 3가지는 통과하였으나 반례를 더 찾아본 후 옳지 않은 방법임을 알아차렸다. 이 방법의 반례는 아래와 같다.
9 3
543211211일 경우 541211 가 나온다.
const input = require("fs")
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
.toString()
.trim()
.split("\n")
.map((el) => el.split(" ").map(Number));
const N = input[0][0];
const K = input[0][1];
let num = String(input[1][0]);
let numArr = Array.from(num, (el)=>Number(el));
let len = num.length;
let end = K;
while(len > N-K){
if(end > len){
numArr.splice(0, 1);
len--;
end = K;
}
let newNum = numArr.slice(0, end);
let min = Math.min(...newNum);
let max = Math.max(...newNum);
if(min === max){
end++;
continue;
}
for(let j=0; j<N; j++){
if (newNum[j] === min){
numArr.splice(j, 1);
len--;
end = K;
break;
}
}
}
console.log(Number(numArr.join('')));시행착오 2
두 번째 생각한 방식은 현재 숫자보다 큰 숫자가 뒤에 있을 경우 삭제하는 방식이다. 예를들어 입력값이
4 2
1924라면 i=0일 때 i번째 자리는 1이다. 그럼 현재 삭제가능한 횟수가 2번이므로 1을 제외한 2자리인 [9, 2] 중 큰 수가 9이고, 9가 i번째 자리인 1보다 크므로 1을 삭제한다.
이 방법은 반례가 없었으나 메모리 초과로 인해 위에서 언급한 스택으로 문제 풀이를 하였다.
const input = require("fs")
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
.toString()
.trim()
.split("\n")
.map(el => el.split(" "));
// .map((el) => el.split(" ").map(Number));
const N = Number(input[0][0]);
const K = Number(input[0][1]);
const num = input[1][0];
let numArr = Array.from(num);
let len = numArr.length;
let count = 0;
for(let i = 0; i<N; i++){
if(count === K)
break;
tempArr = numArr.slice(i+1, i + 1 + K-count);
let max = Math.max(...tempArr);
if(numArr[i] < max){
numArr.splice(i,1);
len--;
count++;
i--;
}
}
if(count != K){
numArr.splice(-(K-count), (K-count));
}
console.log(numArr.join(''));
이때 중요했던 부분이 처음에는 아래 코드에서와 같이 배열을 숫자로 정하고 풀었는데 수의 자리수가 커지면 오버플로우로 제대로 값이 나오지 않는 경우가 발생하였다. 그래서 숫자를 문자열로 두고 최종 출력에서 join을 통해 문자열을 붙여서 숫자처럼 출력했다.
const input = require("fs")
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
.toString()
.trim()
.split("\n")
.map((el) => el.split(" ").map(Number));
const N = input[0][0];
const K = input[0][1];
const num = String(input[1][0]);
let numArr = Array.from(num, (el)=>Number(el)); // 숫자 배열 생성
let len = numArr.length;
let count = 0;
for(let i = 0; i<N; i++){
if(count === K)
break;
tempArr = numArr.slice(i+1, i + 1 + K-count);
let max = Math.max(...tempArr);
if(numArr[i] < max){
numArr.splice(i,1);
len--;
count++;
i--;
}
}
if(count != K){
numArr.splice(-(K-count), (K-count));
}
console.log(Number(numArr.join('')));문제에서 주어지는 숫자가 최대 500,000자리까지 될 수 있는데,
입력받을 때 이미 .map((el) => el.split(" ").map(Number))를 사용해서 숫자형으로 변환하고 있다.
이 경우 15~16자리 이상의 정수는 자바스크립트의 Number(IEEE‑754 64비트 부동소수점)로 표현할 때 정밀도가 깨져서 잘못된 값이 된다.
예를 들어, 아래와 같이 20자리 이상의 숫자가 주어지는 경우,
20 1
123456789012345678902345678901234567890 가 되어야 한다.
그러나 이 코드가 출력하는 결과는 2345678901234567000이다.
💡한줄평
이 문제를 풀며 조금 방황했다. 위에서 보았듯이 두 가지 시행착오를 거치며 꽤 오랜 시간을 소모했다. 그러나 그 시행착오를 통해 스택을 사용해야하는 타당한 이유를 찾을 수 있었고, 스택을 사용하는 과정에서 코드를 설계하는데 보다 짧은 시간을 들일 수 있었다. 역시 실패없는 배움은 없는 것 같다.
