1515 수 이어쓰기

문제

세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다.

세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다.

세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다.

남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.)

입력

첫째 줄에 지우고 남은 수를 한 줄로 이어 붙인 수가 주어진다. 이 수는 최대 3,000자리다.

출력

가능한 N 중에 최솟값을 출력한다.

====

문제 풀이

실버 3인데 나한텐 골드처럼 느껴졌던 문제

1부터 N까지의 수들을 쭉 나열한 뒤 몇 개의 숫자들을 지운 입력값으로부터 N을 구하는 문제였다.

입력값은 최대 3,000자리 인것을 생각하면 N은 1028까지 올 수 있었다.

우선 N을 1이라고 가정하고 이것을 string화 시켜서 temp에 넣어준다.

const str = input[0];
const n = str.length;
let idx = 0;
let num = 1;
let tempString = '1';
let checkedIdx = -1;

idx는 입력값에서 비교할 값을 추출하기 위해 저장할 인덱스다.

num은 정답인 N이 된다.

tempString에는 지금까지의 N을 스트링화 시킨 뒤 저장할 용도

checkedIdx는 str[idx]를 tempString과 비교할 때 시작 인덱스를 저장할 용도이다.

로직은 아래와 같다.

1. 입력값의 첫번째 인덱스부터 tempString의 checkedIdx+1 ~ tempString.length까지 비교해간다. 

2. 이 때 tempString의 엘리먼트와 str[idx]가 같다면 성공한 것이므로 checkedIdx에는 tempString의 검사한 인덱스를 저장.

3. 이제 str의 다음 엘리먼트와 비교해야 하므로 idx에는 ++,

4. 만약 tempString의 엘리먼트 중 str[idx]가 없다면 num의 범위를 확대시켜야 한다는 것이므로 num++ 해준다.

그리고 늘어난 num을 스트링화 시킨 뒤 tempString에 넣어주고 1번부터 다시 시작해주면 된다.

while (idx < n) {
    const target = str[idx];
    let isSuccess = false;

    for (let i = checkedIdx + 1; i < tempString.length; i++) {
        if (target === tempString[i]) {
            checkedIdx = i;
            isSuccess = true;
            idx++;
            break;
        }
    }

    if (!isSuccess) {
        num++;
        tempString += String(num);
    }
}

이렇게 tempString을 사용한 이유는 str이 1111 이라면 -> num이 1일때, 10, 11 일때가 성립되어 정답은 11이 나와야한다.

그런데 tempString없이 num만으로 비교를 한다면 세번째 1을 체크했을 때 num이 11이 되는데 그 다음 네번째 1을 체크할려면 무조건적으로 num이 +가 되어서 12인채로 검사를 하게 된다. 따라서 무조건 num을 ++ 시켜주는 것이 아닌 스트링화 시켜서 현재까지 tempString중 써먹지 않은 1을 그대로 두는 것으로 num을 ++ 할지 조건을 더해준거다.

정답 코드

 

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const str = input[0];
const n = str.length;
let idx = 0;
let num = 1;
let tempString = '1';
let checkedIdx = -1;

while (idx < n) {
    const target = str[idx];
    let isSuccess = false;

    for (let i = checkedIdx + 1; i < tempString.length; i++) {
        if (target === tempString[i]) {
            checkedIdx = i;
            isSuccess = true;
            idx++;
            break;
        }
    }

    if (!isSuccess) {
        num++;
        tempString += String(num);
    }
}

console.log(num);