알고리즘 문제풀이
프로그래머스 레벨2 <튜플> C++ 풀이
steeringhead
2023. 9. 22. 14:28
https://school.programmers.co.kr/learn/courses/30/lessons/64065
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제를 끝까지 읽고나면 규칙이 하나 보이게 됩니다.
제일 앞에 위치하는 숫자가 튜플의 size만큼 등장하고 그 뒤로는 한번씩 덜나옵니다. 즉 만약 [2,1,4,3]이 정답이라면 2가 4번 1이 3번 4가 2번 3이 1번 등장하는 구조입니다. 이렇게 어떤 숫자가 몇번 등장하는지를 체크하기에 가장 좋은 자료구조는 map이기 때문에, map을 사용하면 쉽게 풀 수 있습니다. map<int,int>로 map을 하나 생성하고 Input으로 받은 문자열을 끝까지 순회하면서 숫자에 대해서 카운팅을 해줍니다. 그러면 어렵지 않게 답을 구할 수 있습니다.
|
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
|
#include <string>
#include <vector>
#include <map>
using namespace std;
//map쓰면 될거같음
vector<int> solution(string s) {
vector<int> answer;
map<int,int> info;
int maxVal = 0;
string frag ="";
for (int i=0;i<s.length();i++)
{
if (s[i] == ',' || i == s.length()-1)
{
int tmp = stoi(frag);
info[tmp]++;
frag="";
if (info[tmp] > maxVal)
maxVal = info[tmp];
}
else if (s[i] == '{' || s[i] == '}')
continue;
else
frag += s[i];
}
while(maxVal>0)
{
for (auto iter=info.begin();iter!=info.end();iter++)
{
if (iter->second == maxVal)
answer.push_back(iter->first);
}
maxVal--;
}
return answer;
}
|
cs |