[JavaScript 자바스크립트] 백준 1515번 - 수 이어 쓰기

2024년 7월 1일

문제 링크 :  백준 1515번 - 수 이어 쓰기

문제

 

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

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

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

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

입력

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

출력

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

알고리즘 분류

• 구현
• 그리디 알고리즘
• 문자열
• 브루트포스 알고리즘

---

 

문제 접근

 

원래 수는 1부터 N까지 모든 수를 차례대로 썼는데, 중간에 일부 숫자를 없앤 상황에서 원래 나열했던 수를 다시 찾을 때 N으로 올 수 있는 최대값을 구하는 문제이다.

 

만약 1230이라면 여러가지 경우의 수 중 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]이 최대값으로 올 수 있는 수 중에서 최소값이므로 N은 10이라는 것을 알 수 있다.

 

처음 문제를 보고 어떻게 접근해야 할지 정말 막막했다. 30분은 고민한 것 같다...

 

그러다 문제를 이해하는 과정에서 처음에 가정했던 1230의 경우를 다시 생각해보았다.

 

비교할 수를 1부터 계속 증가시키며, 입력값으로 받은 수를 맨 앞 인덱스부터 비교해보며 현재 비교하는 수에 해당 인덱스 위치의 수가 존재하는지 확인해보는 것이다.

 

수를 계속 증가시키며 매칭되는 수가 존재하면, 각 자리수마다 매칭되는 개수만큼 인덱스를 옮기다가, 마지막 인덱스에서까지 매칭이 되는 그 순간, 해당 비교하는 수가 최대값이 될 것이다.

 

고민 끝에 찾은 풀이 방법은 다음과 같다.

 

 

초기 상태는 위와 같다.

 

현재 비교하는 수 now와, 주어진 입력 값에서 비교할 수의 위치 인덱스를 맨 앞으로 설정해둔다.

 

이제부터 now 와 현재 탐색 인덱스 위치의 수와 매칭되는 부분이 있는지 체크해 나아갈 것이다.

 

now = 1 이고, 현재 탐색 인덱스의 값은 2 이므로 둘은 매칭되지 않으므로 now를 1 증가시킨다.

 

 

now = 2 이고, 현재 탐색 인덱스 값은 2 이므로 둘은 매칭되는 부분이 존재한다.

 

그러므로 인덱스를 1 증가시키고, 다음 수를 확인하기 위해 now 또한 1 증가시킨다.

 

 

now = 3 이고, 현재 탐색 인덱스 값은 3 이므로 둘은 매칭되는 부분이 존재한다.

 

그러므로 인덱스를 1 증가시키고, 다음 수를 확인하기 위해 now 또한 1 증가시킨다.

 

 

now = 4 이고, 현재 탐색 인덱스 값은 4 이므로 둘은 매칭되는 부분이 존재한다.

 

인덱스를 1 증가시키고, 다음 수를 확인하기 위해 now 또한 1 증가시킨다.

 

 

now = 5 이고, 현재 탐색 인덱스 값은 0 이다. 둘은 매칭되는 부분이 존재하지 않으므로 now만 1 증가시킨다.

 

 

now를 1씩 증가시켰을 때, 6 ~ 9 까지 모든 수는 0과 매칭되는 부분이 존재하지 않는다.

 

 

now = 10 이고, 0과 매칭되는 부분이 존재한다.

 

여기까지의 로직을 보았을 때, 원래 나열했던 숫자들 조합은 다음과 같았음을 추측할 수 있다.

 

1 2 3 4 5 6 7 8 9 10

 

 

지금까지 수행했던 방식대로 입력값 끝까지 탐색을 진행하며 매칭되는지 비교해 나아간다.

 

 

 

 

now 가 11 ~ 18일 때에는 9와 매칭되지 않으므로 계속 증가시키며 넘어간다.

 

 

now 가 19 일 때, 9와 매칭되는 부분이 존재하므로 인덱스를 한 칸 이동하고 now를 1 증가시킨다.

 

 

now 가 20 일 때, 2와 매칭되는 부분이 존재한다.

 

인덱스가 입력값의 마지막 위치에서 매칭되었으므로 원래 나열되었던 수 들의 최대값은 최소 20이라는 점을 알 수 있다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

 

여기서 주의해야 할 점은, 매칭되는 자릿수만큼 인덱스를 이동시켜주는 것이다.

 

다음과 같은 경우를 보자.

 

입력값 = ... 02238... 
현재 인덱스 : 굵게 쓰여진 2를 가리키고 있음

now = 23

 

위와 같은 경우, now와 현재 인덱스가 가리키는 수와 매칭이 되고 있다.

 

하지만 바로 뒤에 있는 수까지 보았을 때 now의 1의 자릿수까지 매칭이 되기 때문에 인덱스를 2칸 이동시킬 수 있다.

 

now의 각 자리수와, 현재 인덱스 기준으로 자리수만큼 뒤에 있는 수까지 비교해봐야하는 이유이다.

 

우리는 최대값으로 올 수 있는 수 중에 최소값을 구하고 싶은 것이기 때문에 더 많은 수를 한 번에 매칭시킬수록 좋기 때문이다.

---

입력 예제

 

234092

 

 

 

출력 예제

 

20

 

 

---

전체 코드

 

// 1515

const file = process.platform === "linux" ? "dev/stdin" : "./input.txt";
const numArr = require('fs').readFileSync(file).toString().trim().split('').map(Number);
let now_num = 0;
let now_idx = 0;

while (true) {
    now_num += 1

    nowArr = now_num.toString().split('').map(Number);
    for (let i = 0; i < nowArr.length; i++) {
        if (nowArr[i] === numArr[now_idx]) {
            now_idx += 1;
            if (now_idx >= numArr.length) {
                break;
            }
        }
    }

    if (now_idx >= numArr.length) {
        console.log(now_num);
        break;
    }
}

 

 

---

풀이 후기

 

요즘 문제가 난해하면 브루트포스 방식을 적용해보고 있다.

 

때로는 무식한 방법이 해답이 될 때가 있는데, 이런 문제가 그런 문제였다고 생각한다.

 

브루트포스와 그리디를 적절히 섞은 재미있는 문제였다고 생각한다.