SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
<풀이>
1. 교환 횟수가 될 때 까지, 각 자리 숫자를 모두 교환해본다.
2. 교환된 최댓값을 갱신하고, 출력한다.
<해법>
1. 교환횟수가 많아질 경우, 시간초과 해결 방법
=> 백트래킹을 이용하여 숫자를 모두 교환하는 방식까지는 쉽게 생각할 수 있습니다. 하지만, 교환횟수가 많아지면 시간초과가 나옵니다. 여기서, 다른 방식으로 문제에 접근해야 겠다는 생각을 할 수 있습니다.
샘플 input인 456789, 10 으로 알아보겠습니다.
정답은 987645 입니다. 뒤 두 숫자가 45입니다.
이 말은 많은 반복을 하였음에도 불구하고, 최댓값이 아닐 수 있다 를 의미합니다. 그리고, 987654에서 교환 횟수를 맞추기 위해 987645로 교환을 했다는 것으로 생각할 수 있습니다.
만약 11번 교환할 경우 987654가 되고, 12번 교환할 경우 987645, 13번 987654 ... 이런 식으로 계속 나아갈 것이라고 유추할 수 있습니다.
그렇다면 여기서 중요한 것은 '최댓값을 만드는 동전의 최소교환횟수' 라고 생각할 수 있습니다.
그 횟수를 넘어설 경우, 뒤에 두 숫자만 바꾸어서 교환을 진행할 것이기 때문입니다.
다시, 위 샘플 input을 풀어보도록 하겠습니다.
456789는 3번의 교환만에 987654(최댓값)을 만들 수 있습니다.
이후 4번 교환시 987645, 5번 987654, 6번 987645 ... 이렇게 진행됩니다.
다른 예시로 풀어보겠습니다. 12345 5 입니다.
12345는 2번의 교환만에 54321을 만들 수 있습니다.
이후 3번 54312, 4번 54321, 5번 54312 이므로 정답은 54312 입니다.
규칙이 보이실 거라고 생각합니다.
저의 풀이 방식이었습니다. 더 길게 쓰면 어차피 안보실 것 같아서 쓰지 않았습니다.
위 문제는 테스트 케이스가 몇 개 없어서 정확한 정답이 아닌데도 정답을 맞을 수 있습니다.
예제 테스트 케이스를 몇개 만들어 보았습니다.
//input
14
49 1
49 2
49 3
12345 1
12345 2
12345 3
12345 4
12345 5
456789 1
456789 2
456789 3
456789 4
456789 5
456789 6
//output
#1 94
#2 49
#3 94
#4 52341
#5 54321
#6 54312
#7 54321
#8 54312
#9 956784
#10 986754
#11 987654
#12 987645
#13 987654
#14 987645
input을 반대로 해보셔도 도움이 될 것 같습니다.(49 -> 94, 12345 -> 54321)
|
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s;
int change;
//최대 s
string maxS;
//maxS를 만들 수 있는 최소교환횟수
int minChangeCnt;
//바뀐 change 값
int changeCnt;
//정답값
string answer;
//문자열 바꾸기
void swap(string& str, int x, int y) {
char tmp = str[x];
str[x] = str[y];
str[y] = tmp;
}
//완전탐색(각 자리에서 다른 자리와 교환 or 교환X)
void go(int index, int cnt) {
//모든 자리마다 탐색이 끝난 경우 : 종료
if (index > s.length()) {
return;
}
//maxS를 찾아 낼 경우 : 교환 최소 횟수 갱신
if (s == maxS) {
if (minChangeCnt == -1 || cnt < minChangeCnt) {
minChangeCnt = cnt;
}
}
//교환 횟수를 채운 경우 : 최대값 갱신 후 종료
if (cnt == changeCnt) {
if (answer == "" || stoi(s) > stoi(answer)) {
answer = s;
}
return;
}
//각 자리마다 바꾸기
for (int i = 0; i < s.length(); i++) {
if (i == index) {
go(index + 1, cnt);
}
else {
swap(s, index, i);
go(index + 1, cnt + 1);
swap(s, i, index);
}
}
}
//문자열에 같은 숫자가 있는지 없는지 판단
bool hasSame(string str) {
for (int i = 0; i < str.length() - 1; i++) {
char check = str[i];
for (int j = i + 1; j < str.length(); j++) {
if (check == str[j]) {
return true;
}
}
}
return false;
}
int main() {
int test_case;
int T;
cin >> T;
for (test_case = 1; test_case <= T; test_case++) {
//초기화
answer = "";
maxS = "";
minChangeCnt = -1;
changeCnt = 0;
//입력
cin >> s >> change;
//maxS : s로 만들 수 있는 최대값(s:12345 -> maxS:54321)
maxS = s;
sort(maxS.begin(), maxS.end(), greater<char>());
//교환 횟수 줄이기(최소 문자열 길이만큼만 바꿔도 최댓값을 만들 수 있으므로)
changeCnt = change > s.length() ? s.length() : change;
//탐색
go(0, 0);
//교환 횟수 안에 최댓값을 만들 수 있다면
if (minChangeCnt != -1) {
answer = maxS;
//s에 같은 숫자가 있는 경우, 같은 숫자끼리 무한 반복 -> 최댓값 유지
//s에 같은 숫자가 없는 경우, 뒤에 두 숫자를 바꿀지 말지 결정
if (!hasSame(s)) {
//(교환횟수 - 최댓값을 만들 수 있는 최소교환횟수)가 홀수일 경우 뒤 두 숫자 교환
if ((change - minChangeCnt) % 2 == 1) {
swap(answer, answer.length() - 2, answer.length() - 1);
}
}
}
//출력
cout << "#" << test_case << " " << answer << "\n";
}
//종료
return 0;
}
|
백트래킹에 대해 알아볼 수 있는 문제였습니다.
'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글
| [C++] SWEA 1215 - 회문1 (0) | 2021.01.05 |
|---|---|
| [C++] SWEA 1208 - Flattern (0) | 2021.01.02 |
| [C++] SWEA 2112 - 보호 필름 (0) | 2020.05.19 |
| [C++] SWEA 2117 - 홈 방범 서비스 (0) | 2020.05.19 |
| [C++] SWEA 5656 - 벽돌 깨기 (0) | 2020.05.19 |
