[프로그래머스] 튜플

링크

https://programmers.co.kr/learn/courses/30/lessons/64065

프로그래머스

풀이

 

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 반환하는 문제이다.

 

먼저 문제에서는 집합의 원소의 순서는 바뀌어도 상관이 없다고 한다.

 

그렇다면 집합을 집합이 가지고 있는 원소의 개수대로 정렬을 시킨 후

새롭게 추가되는 원소들을 계속 세어준다면 집합이 표현하는 튜플을 구 할 수 있을거라 생각하였다.

4,2,3	3	3
3	2,3	3, 2
2,3,4,1	4,2,3	3, 2, 4
2,3	2,3,4,1	3, 2, 4, 1

위의 표에서 왼쪽은 주어진 집합 오른쪽은 원소의 개수대로 정렬을 시킨 것인데

오른쪽의 정렬된 차례대로 탐색을 하여 새로운 숫자를 찾을 수 있다.

튜플 -> [3, 2, 4, 1]

 

 

그런데 우리에게 주어진 것은 집합이 하나의 문자열로 주어지고 그러므로

문자열의 문자를 하나씩 탐색하며 집합을 구해야 된다는 것이다.

 

문자열을 봤을 때 집합을 구하기 위해서는 맨 앞과 맨 뒤의 괄호는 필요가 없다는 것을 알 수 있다.

 

집합을 구하기 위해서는 집합을 이루는 요소 즉 괄호와 콤마(,)가 중요하다고 생각했다.

콤마의 개수에 따라서 집합 원소의 개수가 정해지기 때문이고,

 

그런데 콤마는 집합을 이루는 부분 말고도 밖에도 있기 때문에

우리가 필요한 집합 안에 있는 콤마를 카운트하기 위해서는 집합의 시작을 나타내는 괄호가 필요했다.

 

그래서 집합의 시작을 나타내는 괄호에 도착하면 inner_comma라는 변수를 true로 주어 현재 집합이 시작된다라는 것을 알려주고 괄호의 끝에 도착하면 inner_comma를 false로 바꾸어 집합이 끝났음을 알려주어 집합 안에 있는 콤마를 카운트할 수 있도록 하였다.

 

map은 key값에 대해 정렬이 되기 때문에

map <집합 원소의 개수, map <집합 원소, 사용 여부 체크>> 와 같은 map을 만들면

집합 원소의 개수에 대해 정렬이 되고 차례대로 탐색을 하면

튜플의 원소를 구할 수 있게 된다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 100100
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

map<int, map<string,int>> _map;
map<string,bool> visited;
vector<int> solution(string s) {
   int comma_cnt = 0;
   string num = "";
   map<string, int> _m;
   
   //집합의 시작을 알려주는 변수
   bool inner_comma= true;
   int inner_cnt = 0;
   for (int i = 1; i < s.size() - 1; i++) {
       //집합의 시작
      if (s.at(i) == '{') {
         num = "";
         comma_cnt = 0;
         _m.clear();
         inner_comma = true;
         inner_cnt = 0;
      }
      else if (s.at(i) == '}') {
          //집합의 끝
         _m[num] = true;
         _map[comma_cnt + 1] = _m;
         inner_comma = false;
      }
       //콤마 일때
      else if (s.at(i) == ',') {
          //집합안에 있는 콤마 일때
         if (inner_comma == true) {
            _m[num] = true;
            comma_cnt++;
            num = "";
            inner_cnt++;
         }

      }
       //숫자 일때 콤마를 만나기 전까지 그냥 계속 붙여줌
      else {
   
         num+= s.at(i);
      }
   }
   vector<int> answer;

   int m_size = _map.size();
   for (int i = 1; i <= m_size; i++) {
      for (auto _map : _map[i]) {
         if (visited[_map.first] == false) {
            answer.push_back(stoi(_map.first));
            visited[_map.first] = true;
         }
      }
   }
   return answer;
}

 

 

포스팅을 하고나서 다른 방법으로도 풀어봤는데

 

원소가 중복이 되지 않기 때문에 집합에서 원소가 각가 몇개 나오는지 카운팅을 해주고

카운팅된 개수가 가장 큰 원소가 가장 작은 원소의 개수를 가지는 집합임을 이용하여 풀었다.

 

#include<iostream>
#include<map>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

map<string, int> _map;

bool cmp(pair<string, int> p1, pair<string, int>p2) {
	return p1.second > p2.second;
}
vector<int> solution(string s) {
	string num = "";
	for (int i = 1; i < s.size() - 1; i++) {
		if (s[i] == '}' || s[i] == '{' || s[i] == ',') {
			if (s[i] == ',' && num != "" || s[i] == '}' && num != "")
				_map[num]++;
			num = "";
		}
		else {
			num = num + s[i];
		}
	}

	vector <pair<string, int>> arr(_map.begin(), _map.end());
	sort(arr.begin(), arr.end(), cmp);

	vector<int> answer;
	for (auto a : arr) {
		answer.push_back(stoi(a.first));
	}
	return answer;
}