문제

[프로그래머스] 튜플

접근

순서가 바뀔 수 없으니 튜플길이만큼 등장하는 것이 첫번째요소

1. key 에 등장횟수 저장
2. map을 vec로 바꿔 value 기반으로 정렬하여 출력

map을 커스텀 정렬

map의 데이터구조는 자동으로 오름차순으로 구성되어 있다

이것을 내림차순으로 바꾸려면 vec로 map을 옮긴 후 커스텀 배열을 써야 한다

map은 key value를 쓰기 위해서 사용하는데 이런부분은 불편하다

다른방법

다른 풀이가 있다면 배열의 idx에 저장해서 사용하는 방법이 있을 것 같다
하지만 찾는 비용이 배열의 크기에 따라 크게 작용할 것이다
idx를 저장하는 다른 배열을 생성해서 쓰는 것도 가능할까

음 이것도 꽤 복잡하겠다
메모리가 많이 필요할 것 같다

풀이

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

#define pii pair<int,int>
using namespace std;

// value 값을 비교하는 함수
bool cmp(const pii& a, const pii& b) {
	if (a.second == b.second) return a.first > b.first;		// second가 value
	return a.second > b.second;								// value가 다르다면 비교결과 반환
}


vector <int> solution(string s) {
	vector<int> answer;
	map<int, int> m;									 // key value 로 저장됨

	string tmp;
	for (int i = 1; i < s.length() - 1; i++)
	{
		if (s[i] != '{' && s[i] != '}' && s[i] != ',')	 // 숫자일 경우
		{
			tmp += s[i];
			if (s[i + 1] == ',' || s[i + 1] == '}') {
				m[stoi(tmp)]++;							  // 카운팅 : 해당 키의 value 증가
			}
			else continue;								  // 기호가 나오지 않았다면 tmp에 계속 담음
		}
		tmp = "";
	}

	// 여기까지 하면 
	// map key   : tuple의 요소
	// map value : 요소가 등장한 횟수

	// value 기반 정렬
	vector<pii> vec(m.begin(), m.end());	// map 기반 vec 형성
	sort(vec.begin(), vec.end(), cmp);		// cmp에서 value비교를 넣었으니 vector가 value기준으로 정렬됨

	for (auto num : vec) {
		answer.push_back(num.first);		//emplace_back을 써도 됨;
	}
	
	return answer;
}

int main() {
	string input;
	cin >> input;
	solution(input);
}

참고블로그
감사합니다!