Table of Contents
문제
10개의 숫자 버튼과 채널을 1씩만 바꿀 수 있는 +- 버튼이 달린 리모컨이 있는데, 숫자 버튼 몇 개가 고장났다. 기본값 100번 채널에서 원하는 채널로 이동하고자 할 때, 버튼을 눌러야 하는 가장 적은 횟수를 구하라.
예제 입출력은 생략한다. 여기에 다 쓰기엔 길다.
계획
문제 이해부터 해봤다. 고장난 숫자 버튼을 알려줄 테니 원하는 채널로 이동하기 위해 최대한 적게 버튼을 누르라는 문제다. 문제집에서 찾아 풀고 있기 때문에 이 문제가 브루트포스 문제라는 건 이미 알고 있었다. 가능한 숫자 버튼올 목표 채널과 가장 가까운 채널로 이동한 다음 +- 버튼으로 숫자를 맞추면 된다.
저장할 방법부터 생각해봤다. 눌러도 되는 버튼과 누르면 안 되는 버튼이 있으니, 모든 버튼을 준비하고 눌러도 되는지를 기록하는 방법이 있고, 애초부터 되는 버튼만 기록하는 방법이 있었는데, 전자는 버튼을 누를 때마다 그게 되는 버튼인지 아닌지 보면서 눌러야 해서 후자로 골랐다.
할 일은 숫자 버튼만으로 이동할 수 있는 채널 중 목표값과 가장 가까운 것을 찾는 것. 가능한 숫자를 나열해서 순열을 만들면 된다. 여기서 처음에 생각했던 게 두 가지 있는데, 하나는 모든 순열을 만든 후 이분탐색으로 목표값과 가장 가까운 값을 찾는 방법, 하나는 순열을 만드는 동시에 목표값과 가장 가까운 값을 찾는 방법이었다. 전자는 순열을 만드는 것 자체는 괜찮은데, 딱 그 값을 찾는 게 아니라 ‘가장 가까운’ 값을 찾아야 한다는 점에서 검색이 제대로 이루어지지 않을 가능성이 높아 보였고(이걸 해결한다고 시간을 들이느니 다른 알고리즘을 쓰는 게 낫다), 후자는 말은 괜찮은데 결국 마지막에 가선 전자와 똑같은 검색 문제가 생겼다.
이런저런 시도 끝에 일단은 다른 건 다 넘겨두고, 순열을 만드는 것부터 구현해보기로 했었고, 그와중에도 재귀를 반복으로 바꿔보겠다고 또 헤매느라 며칠 썼다. 말이 계획이지 자꾸 과거형으로 쓰는 것도 며칠동안 삽질하다가 문제 해결하고 나서 글을 쓰고 있어서 그런 거다.
많은 일이 있었다
- 초기 계획
- 순열을 만든 후 적절한 값을 찾는 방법과 순열을 만들면서 동시에 적절한 값을 찾는 방법 중 어떤 게 빠른지 직접 코드를 돌려서 비교해보자(시간복잡도 계산하기 귀찮았을 뿐임)
- 그럼 일단 순열을 만드는 코드부터 쓰자
- 보통 재귀를 쓰는 것 같으니 나는 이걸 반복으로 바꿔보겠다 -> 여기서 3일 날렸다.
- 계획 재검토 -> 이 부분만 두세 시간 정도 걸렸다.
- 이론적으로는 모든 재귀를 반복으로 바꿀 수 있다고는 하지만, 그렇게 하기 위해 함수 호출 스택을 전부 그대로 저장할 거라면 그것은 더이상 반복으로 구현하는 의미가 없다. 이 알고리즘의 구현 방식을 재귀에서 반복으로 바꾸는 것은 호출 스택을 그대로 구현하려고 시도한 시점에서 의미가 없어졌다.
- 초기 계획 또한 문제가 있다. 똑같은 값을 검색하는 방법은 잘 알지만 비슷한 값을 검색하는 방법은 잘 모른다. 고로 정렬을 이용해 목표값과 가장 차이가 적은 값을 찾기로 했다. 다만 순열이 얼마나 나올지는 모르니 완성 후 정렬하는 것이 아니라, 항상 정렬이 유지되는 방식으로.
- 재귀를 이용한 순열 구현 방식을 그대로 써서 일단 뭐라도 답이 나오는 코드를 쓰는 것부터 해보자.
- 첫 번째 코드를 완성하고 실행해보니 답이 제대로 안 나왔다. 확인해보니 버튼을 중복하지 않고 누르게 만든 것이 문제. 여기서 아주 중요한 문제점이 발견됐다. 이 문제는 버튼을 중복해서 누르면 안된다는 말이 한 마디도 없었는데 중복이 없는 순열을 구현한 것.
- 문제 이해가 아주 기본적인 부분에서부터 잘못되어있었다는 점을 확인하고 중복이 가능한 순열을 만들도록 코드를 고쳤다.
- 목표값과 가장 가까운 값을 찾는 것에도 약간 문제가 있었다. 단순히 목표값에서 채널값을 뺀 값으로 나온 음수와 양수를 그대로 저장하면 정렬이 완료되었을 때 반대로 목표값과 가장 먼 값이 나올 수 있으니 절댓값을 저장해야 했다. 하지만 목표값과 채널값에 따라 그 차이가 음수인지 양수인지는 숫자의 자릿수와도 관계가 있어서 이 정보를 그냥 버릴 수는 없었다.
- 우선순위 큐에 목표값과 채널값의 차이 절댓값, 차이 자체를 pair로 저장하기로 했다. 이후 숫자가 작은 채널이 우선시되도록 하기 위해 커스텀 비교 연산자를 만들었다.
순열은 DFS
이번 문제에서 가장 시간을 많이 잡아먹은 부분은 순열 구현이었다(대부분이 삽질이긴 했지만). 순열은 늘어놓고 보면 숫자가 작은 것부터 큰 것으로 점차 증가한다는 점에서 처음엔 BFS일 줄 알았는데, 알고리즘을 찾아보니 DFS였다.
왜 DFS인지 간단하게 말하자면, 앞에서부터 먼저 숫자를 채운 후 남은 마지막 자리에, 가능한 숫자를 하나씩 다 넣어본다. 그 후 바로 앞 자리 숫자를 바꿔서 다시 마지막 자리를 차례로 채워본다. 이를 트리로 나타내면 맨 앞자리를 나타내는 루트 노드에서부터 노드를 하나 지날 때마다 숫자가 채워지고, 마지막 자리를 채우기 위해 리프 노드를 모두 순회하는 모양이 된다. 최대한 깊이 들어간 다음 모두 순회하므로 DFS가 맞다. 중복 순열도 노드의 개수가 많아질 뿐 흐름은 같다.
풀이
애초부터 금방 맞을 거라는 기대가 없었기 때문에 따로 시간은 재지 않았고, 날짜로 4일 걸렸다.
이 문제에서 내게 중요했던 부분은 다음과 같다.
- 중복 순열(+ 중복 없는 순열) 구현
- 생성된 순열에서 빠르게 답 찾기
- 꼭 목표값의 자릿수와 같은 자릿수를 갖는 채널만 눌러야 하는 건 아님 <- 이건 반례 때문에 알게 됐다
중복 순열
중복 순열 생성 알고리즘은 다음과 같은 과정으로 이루어진다. 중복이 없는 순열은 visited 배열을 따로 생성해서 중복 여부만 확인하면 된다. [Algorithm] 순열(Permutation) 구현 코드를 참고했다.
사용할 숫자의 개수와 만들 숫자의 자릿수를 정한다.
만들 숫자의 0번 인덱스에서부터 다음 과정을 시작한다.
만약 지금 인덱스가 만들 숫자의 자릿수와 같다면 현재 채워진 수를 모두 꺼내 하나의 숫자로 만들고 돌아간다(return).
그렇지 않다면 다음을 수행한다.
사용할 숫자를 차례로 현재 인덱스의 자리에 채운다.
인덱스를 1 증가시키고 재귀호출한다.
코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct cmp {
bool operator()(pair<int, int> a, pair<int, int> b) {
if (a.first == b.first) {
return b.second > a.second;
}
return a.first > b.first;
}
};
int goal, len;
vector<int> valid_btns;
vector<int> order;
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> channels;
void make_permute(int now, int len) {
if (now == len) {
int temp = 0;
for (int i = 0; i < len; i++)
temp = temp * 10 + valid_btns[order[i]];
channels.emplace(abs(goal - temp), goal - temp);
return;
}
for (int i = 0; i < valid_btns.size(); i++) {
order[now] = i;
make_permute(now + 1, len);
}
}
순열에서 조건에 맞는 답 찾기
이 문제에서 답의 조건은 목표값과 가장 차이가 적은 것이다. 단순히 가장 작은 값이어서는 안 되고, 방향도 필요했다. 목표값과 거리가 같아도 자릿수가 더 적은 숫자가 있다면 그걸 답으로 해야 한다. 여기서 나는 두 가지 정보를 사용했다. 목표값과 채널값의 차이, 그 값의 절댓값. 이 두 값을 pair로 묶어 우선순위 큐에 넣고, 절댓값은 작아지게, 차이 값은 커지게 정렬했다. 사용한 코드는 다음과 같다.
모든 버튼이 고장나 누를 수 있는 채널이 없어서 큐가 비어있는 경우가 반례로 생기기도 했는데, 그건 top()을 꺼내기 전에 empty() 여부를 확인하면 해결된다.
1
2
3
4
5
6
7
8
9
10
struct cmp {
bool operator()(pair<int, int> a, pair<int, int> b) {
if (a.first == b.first) {
return b.second > a.second;
}
return a.first > b.first;
}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> channels;
답이 될 수 있는 채널 찾기
예를 들어 목표값이 5자리 채널이라고 하자. 이때 이 채널로 가기 위해 눌러야 할 가장 가까운 채널 값은 일반적으로는 똑같이 5자리인 경우가 많긴 할 것이다. 하지만 가끔은 자릿수가 다른 게 더 가까운 숫자가 되는 경우도 있다. 그런 경우도 모두 고려하기 위해 목표값의 자릿수보다 하나 적은 수, 하나 많은 수의 채널까지 모두 순열을 생성하게 했다. 다만 목표값이 한 자리라면 그보다 자릿수가 적은 수는 없으니 이 부분만 확인하게 했다.
1
2
3
4
if (len - 1 > 0)
make_permute(0, len - 1);
make_permute(0, len);
make_permute(0, len + 1);
좀 더 효율적인 코드
다시 생각을 해보자. 문제에서 요구하는 것은 최솟값 하나뿐이지, 가능한 모든 경우에 대한 정보가 아니다. 그렇다면 나도 그 정보들을 모두 저장할 필요가 없는 게 맞지 않을까? 물론 모든 정보가 있어야만 답을 찾을 수 있는 경우도 있을 테지만 이 문제는 그런 경우가 아니다. 항상 최솟값 하나만 기억하고 있어도 답을 찾는 데에는 문제가 없다.
앞선 풀이에서 우선순위 큐를 빼고 최솟값만 기억하는 int 변수로 대체했다. 이렇게 해서 백준 제출 기록 기준으로 메모리는 198860KB에서 2124KB로 줄고 시간은 288ms에서 108ms로 줄었다. 모든 순열 값을 저장하지 않으니 메모리가 대폭 줄고, 힙 삽입 연산도 안 하니 시간도 절반 가량 줄었다. 필요 없는 정보는 굳이 갖고 있지 말고 제때 버리자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int min_dist = INT_MAX;
void make_permute(int now, int len) {
if (now == len) {
int temp = 0;
for (int i = 0; i < len; i++)
temp = temp * 10 + valid_btns[order[i]];
temp = goal - temp;
if (abs(temp) < abs(min_dist) || (abs(temp) == abs(min_dist) && temp > min_dist))
min_dist = temp;
return;
}
for (int i = 0; i < valid_btns.size(); i++) {
order[now] = i;
make_permute(now + 1, len);
}
}
전체 코드 보기
전역변수로 생성된 것들은 사용하는 영역이 한정적이라면 특정 스코프 내의 static 변수로 선언해도 똑같이 쓸 수 있다. 이번 문제에서는 관리가 어려워 그냥 전역변수로 썼다. 시도는 해봤는데 안 하던 짓을 해서 그런지 영 안맞았다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <climits>
using namespace std;
int goal, len;
vector<int> valid_btns;
vector<int> order;
int min_dist = INT_MAX;
void make_permute(int now, int len) {
if (now == len) {
int temp = 0;
for (int i = 0; i < len; i++)
temp = temp * 10 + valid_btns[order[i]];
temp = goal - temp;
if (abs(temp) < abs(min_dist) || (abs(temp) == abs(min_dist) && temp > min_dist))
min_dist = temp;
return;
}
for (int i = 0; i < valid_btns.size(); i++) {
order[now] = i;
make_permute(now + 1, len);
}
}
int main()
{
// 빠른 입출력
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, temp_int;
set<int> invalid_btns;
pair<int, int> buffer;
cin >> goal >> n;
len = floor(log10(max(1, goal))) + 1;
order.resize(len + 1);
for (int i = 0; i < n; i++) {
cin >> temp_int;
invalid_btns.emplace(temp_int);
}
for (int i = 0; i <= 9; i++) {
if (invalid_btns.find(i) == invalid_btns.end())
valid_btns.emplace_back(i);
}
if (len - 1 > 0)
make_permute(0, len - 1);
make_permute(0, len);
make_permute(0, len + 1);
if (min_dist != INT_MAX) {
temp_int = abs(min_dist) + floor(log10(max(1, goal - min_dist))) + 1;
if (abs(goal - 100) < temp_int) {
temp_int = abs(goal - 100);
}
}
else {
temp_int = abs(goal - 100);
}
cout << temp_int << "\n";
return 0;
}