오늘은 sql 공부하다가 몸이 슬슬 간지로워서, 백준에서 새로 추가된 N으로 만들기 (17255번) 문제를 풀어 봤습니다.
이 문제는 2019년 전북대학교 프로그래밍 경진대회 출제 문제입니다.
https://www.acmicpc.net/problem/17255
풀이
그냥 단순히 중간과정을 저장하는 시뮬레이션으로 푸시면 됩니다.
뭔가 계산적으로 풀어도 될 거 같긴 한데…
제가 사용한 방법은 unordered_set 을 이용하여 풀었습니다.
굳이 unordered_set 대신 그냥 set을 쓰셔도 큰 차이가 없을 듯 합니다.
unordered_set 은 탐색 속도에서 우위이고, 데이터 추가하는데 오래 걸릴 수 있으니까요.
set 에 대한건 https://mountrivers.github.io/setsandmaps/ 를 참고 해주시기 바랍니다.
풀이 방법은 예시를 들어 설명하겠습니다.
(예시)
9111 -> 9 / 1 / 1 / 1로 쪼갭니다.
저는 어차피 9111로 하나, 1119 로 하나 결과는 똑같기에 짜르기 편하게 잘라서 역방향으로 넣었습니다.
그래서 1 / 1 / 1 / 9 로 쪼갰습니다.
왼쪽 포인터와 오른쪽 포인터를 나눠서
탐색을 합니다.
1 -> 11 -> 111 -> 1119 순으로 탐색을 하는데요, 결과만 가지고는 같은 순서로 탐색 되었는지 알 수 없기 때문에
이걸 모두 이어붙여줍니다.
1111111119 이렇게요.
그리고 이 결과를 set 에 넣어 줍니다.
당연히 multi set 이 아니라서 중복된 데이터는 알아서 걸러집니다.
그리고 set의 size를 구해주시면 문제는 끝납니다.
코드 및 주석
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <unordered_set>
using namespace std;
int leftMax = 0;
int rightMax = 0;
void doubleWay(vector<int> &list, unordered_set <string> & availables, vector<int> & checked, int lp,int rp, int n,string sum) {
if (n == rightMax+1) { // 모든 글자 탐색 완료
availables.insert(sum);
}
else {
/* 왼쪽 방향 탐색 */
if (lp != leftMax && checked[lp-1] ==0) {
checked[lp - 1] = 1;
string temp = sum;
sum = sum + to_string(list[lp - 1]) + sum;
doubleWay(list, availables, checked, lp -1,rp,n+1, sum);
sum = temp;
checked[lp - 1] = 0;
}
/* 오른쪽 방향 탐색 */
if (rp != rightMax && checked[rp + 1] ==0) {
checked[rp + 1] = 1;
string temp = sum;
sum = sum + sum + to_string(list[rp + 1]);
doubleWay(list, availables, checked,lp, rp + 1, n + 1, sum);
sum = temp;
checked[rp + 1] = 0;
}
}
}
int main() {
int n;
vector <int> list;
unordered_set <string> availables;
string sum;
cin >> n;
while (n != 0) {
// 정방향으로 넣을 필요 없이, 역박향도 똑같은 결과임으로 간결하게 역방향으로 넣는다.
list.push_back(n % 10);
n /= 10;
}
rightMax = list.size() - 1; // 오른쪽 끝
vector <int> checked(rightMax+1,0);
for (int i = 0; i <= rightMax; i++) {
sum = to_string(list[i]);
checked[i] = 1;
doubleWay(list, availables, checked, i,i, 1,sum);
checked[i] = 0;
}
if (availables.size())
cout << availables.size();
else
cout << 1;
cin >> n;
return 0;
}