.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
브루투포스 알고리즘, 211105
문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
예제 입력 1
5457
3
6 7 8
Plain Text
복사
예제 출력 1
6
Plain Text
복사
예제 입력 2
100
5
0 1 2 3 4
Plain Text
복사
예제 출력 2
0
Plain Text
복사
예제 입력 3
500000
8
0 2 3 4 6 7 8 9
Plain Text
복사
예제 출력 3
11117
Plain Text
복사
예제 입력 4
100
3
1 0 5
Plain Text
복사
예제 출력 4
0
Plain Text
복사
예제 입력 5
14124
0
Plain Text
복사
예제 출력 5
5
Plain Text
복사
예제 입력 6
1
9
1 2 3 4 5 6 7 8 9
Plain Text
복사
예제 출력 6
2
Plain Text
복사
예제 입력 7
80000
2
8 9
Plain Text
복사
예제 출력 7
2228
Plain Text
복사
힌트
예제 1의 경우 5455++ 또는 5459--
My solution
힌트를 보면 가능한 경우의 수(5455++ 또는 5459--)를 전부 다 구해서 그 문자열의 길이가 가장 짧은 경우만 answer에 담아서 마지막에 반환해주면 된다고 생각했다.
5457
3
6 7 8
JavaScript
복사
N이 5457이고 3개의 고장난 버튼이 있다(0이면 3번째 줄은 들어오지 않음, Button에 undefined 들어옴).
미리 0~9가 들어있는 배열을 만들고 들어온 고장난 버튼을 제외시켜주는 로직을 만들었다.
function solution(i) {
...
[N, M, Button] = input;
let btn = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
if (M && Button !== undefined) {
Button = Button.split(" ").map((v) => +v);
btn = btn.filter((v) => {
for (let x of Button) {
if (x !== v) continue;
else return false;
}
return true;
});
}
JavaScript
복사
100번 채널에서 시작하므로 N에서 빼서 차이의 절댓값을 answer에 저장해두어야 한다.(+나 -로 이동했을 때 횟수)
이렇게 풀어서 테스트케이스 7번에서 시간이 너무 오래 걸렸다. 나머지 테스트케이스만 모두 통과되었다. 그래서 N이 100보다 큰 경우에만 + 버튼을 누르는 연산을 하도록 if( 100 < N )으로 감쌌다.
틀린 코드
하지만 제출해보니 5%에서 fail되었다. 그래서 브루투포스 알고리즘을 사용하라는 힌트를 보고 접근 방식을 다시 생각해보았다.
다른 사람의 코드(https://kwangkyun-world.tistory.com/entry/Python파이썬-1107-백준-리모컨)를 보니 가능한 모든 숫자를 탐색했다. 0~100만까지 숫자가 현재 가지고 있는 버튼으로 만들 수 있는지 전부 검사했을 때 버튼을 눌러 이동이 가능한 경우일 때마다 result를 비교했고 최솟값이면 result에 저장했다.
내 방식과 다른 점이 나는 N에서 ++, — 연산자를 이용해서 얼마나 이동해야 그 값에 도달할 수 있는지 찾는 것이었는데 이렇게 하면 N이 1이고 사용가능한 버튼이 [0]인 경우에 N에서 계속 더해나가면서 무한루프에 빠지는 등 코드가 지저분해졌는데, 다른 코드를 보면 N이 기준이 아니라 아예 i라는 숫자를 잡아 0부터 100만까지 전부 검사하는 것이다. (N을 기준으로 — 연산을 하더라도 0보다 내려가서는 안되고 50만보다는 더 올라갈 수 있다는 것을 알아야 한다.) 이렇게 하면 - 버튼으로 찾아내려가는 것과 +버튼으로 찾아올라가는 것으로 로직을 나눌 필요가 없어 깔끔해졌다.
여기서 i의 범위가 100만인 이유는 N의 최댓값이 50만인데 그보다 더 큰 60만(예)부터 내려오는 것이 더 가까운 경우가 존재하기 떄문이다.
이동이 가능한 숫자 i인 경우, 그 숫자 i를 문자열화해서 i의 자릿수 + (i - N) 를 계산해서 최솟값을 구했다.
i가 N보다 작을 때에도 +/- 버튼에 상관없이 절댓값으로 얼마나 차이가 나는지를 판단하면 되기 때문에 Math.abs()메서드로 절댓값을 측정해준다. i의 최솟값은 0보다 작아질 수 없어서 0~100만인 것이다.
위의 로직은 제외된 버튼이 존재했을 때의 방식이고, 만약 제외된 버튼이 없는 경우 위의 로직을 수행할 필요가 없다.
이때의 에지케이스 처리를 해주었는데, 제외된 버튼이 없는 경우 포함된 버튼의 개수가 10개이므로 else문에서 버튼으로 바로 이동할 수 있는 것을 result와 비교해서 최솟값을 저장한다.
소스코드
function solution(i) {
const input = i.toString().trim().split("\n");
[N, M, Button] = input;
let btn = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
// 고장난 버튼이 0개일 때 btn 배열을 새로 만듦
if (Button !== undefined && M !== 0) {
Button = Button.split(" ").map((v) => +v);
btn = btn.filter((v) => {
for (let x of Button) {
if (x !== v) continue;
else return false;
}
return true;
});
}
// 들어온 숫자가 버튼으로 이동 가능한 숫자인지 검사
function check(num) {
num = num
.toString()
.split("")
.map((v) => +v);
for (let i of num) {
if (!btn.includes(i)) return false;
}
return true;
}
// 제외된 버튼이 존재하면 0~1,000,000까지 검사해서 최솟값을 찾음
// 모든 버튼이 가능하다면 기존 result와 버튼으로 바로 이동하는 횟수를 비교해서 최솟값 할당
let result = Math.abs(N - 100);
if (btn.length < 10) {
for (let i = 0; i < 1000001; i++) {
if (check(i)) {
result = Math.min(
result,
i.toString().length + Math.abs(i - N)
);
}
}
} else result = Math.min(result, N.length);
console.log(result);
return result.toString();
}
test("solution", () => {
expect(
solution(`14124
0`)
).toStrictEqual("5");
expect(
solution(`5457
3
6 7 8`)
).toStrictEqual("6");
expect(
solution(`100
5
0 1 2 3 4`)
).toStrictEqual("0");
expect(
solution(`500000
8
0 2 3 4 6 7 8 9`)
).toStrictEqual("11117");
expect(
solution(`100
3
1 0 5`)
).toStrictEqual("0");
expect(
solution(`80000
2
8 9`)
).toStrictEqual("2228");
expect(
solution(`1
9
1 2 3 4 5 6 7 8 9`)
).toStrictEqual("2");
});
JavaScript
복사
