튜플 문제 바로가기
이번문제의 핵심은 2가지 이다.
- 문자열파싱
- 문자열 크기대로 정렬
첫번째로, 문자열 파싱이다.
{1,2,3} 각 괄호마다 떼어내서 vector v에다가 넣어야한다.
두번째로, 문자열 크기대로 정렬해야한다.
왜그래야할까? 만약 {2},{2,3},{4,2,3} 이렇게 있다면 만족하는 튜플은 맨처음에 2=>그다음 {2,3}에서 2는 이미 있으니까 없는 3 => 그다음 {2,3}에서 없는 4를 찾아서 {2,3,4} 이런식으로 튜플을 만들 수 있다.
그래서 코드를 보면
문자열을 파싱하는 부분이다.
for (int i = 1; i < s.size() - 1; i++) {
if (s[i] == '{') { sw = true; }
else if (s[i] == '}') {
sw = false;
v.push_back(stoi(temp));
temp = "";
}
else if (sw && s[i] != ',') {
temp += s[i];
}else if (sw && s[i] == ',') {
v.push_back(stoi(temp));
temp = "";
}
else if (!sw && s[i] == ',') {
for (int i = 0; i < v.size(); i++) {
map[v.size()].push_back(v[i]);
}
cnt++;
v.clear();
}
}
for (int i = 0; i < v.size(); i++) {
map[v.size()].push_back(v[i]);
}for에서 1과, s.size()-1로 양측 괄호는 무시하고 하였다.
1. { 를 만난다면 맨처음 시작이므로 sw를 true로 만들어준다. sw가 true여야만, temp에다가 숫자를 넣을 수 있다.
2. 만약에 } 이면 sw를 false로 만들어준다. 왜냐하면 } 뒤에 , 가 나오므로 이 ,를 temp에 넣지 않기 위해서이다. vector에 넣어주고 temp를 초기화해준다.
3. sw가 true인데 ,가 아니면 숫자이므로 temp에다가 넣어준다.
4. sww가 true인데 ,이면 숫자가 끝났으므로 stoi로 int로 바꾸어서 vector에 넣어준다. 마찬가지로 temp를 초기화 해준다.
5. 마지막으로 sw가 false 즉,}를 만나서 이미 다 끝났는데 ,가 나오면 각 size에 해당하는 vetor에 넣을 숫자를 다 넣었다는 뜻이므로, 위에서 말한 핵심 2번째에서, size별로 확인하기 위해서 vector 배열 map에 넣어준다. 그리고 v를 clear로 초기화해준다.
여기까지하면
map[1]=2
map[2]=2,1
map[3]=2,1,3
map[4]=2,1,3,4
이렇게 되어있을 것이다.
이제 map을 방문하면서 answer에 넣어주면된다.
bool check[100000] = { false, };
for (int i = 1; i < cnt+1; i++) {
if (i == 1) {
answer.push_back(map[i][0]);
check[map[i][0]] = true;
}
else {
for (int j = 0; j < map[i].size(); j++) {
if (!check[map[i][j]]) {
answer.push_back(map[i][j]);
check[map[i][j]] = true;
}
}
}
}check를 통해서 answer에다 값을 넣었는지 넣지 않았는지 확인한다.
i==1일때는 숫자 1개니까 answer에 넣고 방문처리를 해준다.
2부터는 check배열과 확인하여 answer에 넣지 않은 숫자인지 확인후 answer에 넣는다.
총 코드
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> solution(string s) {
vector <int> map[100000];
vector<int> answer;
string temp;
bool sw = false;
vector <int> v;
int cnt = 1;
for (int i = 1; i < s.size() - 1; i++) {
if (s[i] == '{') { sw = true; }
else if (s[i] == '}') {
sw = false;
v.push_back(stoi(temp));
temp = "";
}
else if (sw && s[i] != ',') {
temp += s[i];
}else if (sw && s[i] == ',') {
v.push_back(stoi(temp));
temp = "";
}
else if (!sw && s[i] == ',') {
for (int i = 0; i < v.size(); i++) {
map[v.size()].push_back(v[i]);
}
cnt++;
v.clear();
}
}
for (int i = 0; i < v.size(); i++) {
map[v.size()].push_back(v[i]);
}
bool check[100000] = { false, };
for (int i = 1; i < cnt+1; i++) {
if (i == 1) {
answer.push_back(map[i][0]);
check[map[i][0]] = true;
}
else {
for (int j = 0; j < map[i].size(); j++) {
if (!check[map[i][j]]) {
answer.push_back(map[i][j]);
check[map[i][j]] = true;
}
}
}
}
return answer;
}문제 총평
난이도 중하.
파이썬으로는 다들 쉽게 짜는데, c++이라 조금 까다로웠다. 사실 이문제는 ide를 조금 활용하였는데, 계속 coredump가 떠서 도저히 못찾아 디버깅을 했다.
if else if 가 아닌 맨처음에 if if로 짯는데 여기서 오류가 발생했다.
문자열에서는 항상 예외처리와 조건문을 살피는 습관을 가져야겠다.
