[C++] 프로그래머스 문자열 내 마음대로 정렬하기

programmers.co.kr/learn/courses/30/lessons/12915

코딩테스트 연습 - 문자열 내 마음대로 정렬하기

 

1. 서론

 

level 1 문제다. 본질을 파악하면 간단하고, 그걸 할 줄 모르면 나처럼 헤매게 된다.... 슬프게도. 이 문제를 통해 배웠다고 생각하자^^

 

2. 문제 설명

 

배열에 문자열이 담겨져 있다. index가 주어지는데 그 index의 문자형에 따라 오름차순으로 정렬한다. 그 값들이 전부 같은 경우는 그냥 사전 순으로 정렬한다.

 

sun, bed, car => 1

 

u, e, a => car, bed, sun

 

3. 코드 설명

 

1) 내가 생각한 경우 (궁금한 사람만 볼 것)

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(vector<string> strings, int n) {
    vector<string> answer;
    vector<pair<char, int>> t;
    vector<string> st;
    string s;
    int i, j, x, flag = 0;
    
    for (i = 0; i < strings.size(); i++)
    {
        s = strings[i];
        t.push_back(make_pair(s[n], i));
    }
    
    x = t[0].first;
    for (i = 1; i < t.size(); i++)
        if (x != t[i].first)
            flag = 1;
            
    if (flag == 1)
    {
        sort(t.begin(), t.end());
    
        x = t[0].first;
        st.push_back(strings[t[0].second]);
        for (i = 1; i < t.size(); i++)
        {
            if (x == t[i].first)
                st.push_back(strings[t[i].second]);
            
            else
            {
                x = t[i].first; 
                if (!st.empty())
                {
                    sort(st.begin(), st.end());
                    for (j = 0; j < st.size(); j++)
                        answer.push_back(st[j]);
                    for (j = 0; j < st.size(); j++)
                        st.pop_back();
                }
                answer.push_back(strings[t[i].second]);
            }          
           
        }
    }
    else
    {
        sort(strings.begin(), strings.end());
        answer = strings;
    }
 
    return answer;
}

 

진짜 어렵게도 풀었는데 참고로 이 코드는 주어진 테스트 케이스는 다 돌아가지만 실제로 제출하면 8점인가 맞는다 ㅎ

그리고 내가 테케를 몇 개나 만들어서 넣어봤는데 다 돌긴 했다.

 

처음에 주어진 문자열에서 주어진 index의 값만 따로 모으는 배열을 만들었다. pair로 앞에는 문자형이 뒤에는 그 문자가 속해있는 배열의 index를 저장했다. flag로 만약에 모든 문자형이 같으면 그냥 원래 배열을 정렬해서 return 하고 아니면 나머지 과정을 거친다.

내가 생각한 남은 경우는 몇 가지만 같은 문자형일 경우와 문자형이 전부 다른 경우였다. 그래서 st 배열을 통해서 문자형이 같은 값들은 따로 모아서 정렬을 해서 넣어주고 아닌 경우에는 문자형의 순서대로 정렬했다. 

 

내가 생각한 여러 테케는 다 맞았지만, 정확성 테스트 결과 8점을 맞았다. 엄청 조잡하고 이상하게 푼게 확실하긴 한데 푸는 방법이 저거 이외에는 생각이 안 났기 때문에 C++ sort() 함수에 대해서 써치 해봤다. 나는 C++ 배우거나 공부해본 적이 없어서 사실 잘 모른다.

난 C만 배운걸 가지고 귀동냥으로 닥치면서 vector만 공부한 게 전부였다. 정렬을 많이 해본 사람이면 바로 쉽게 풀었을 것 같지만, 나는 정렬의 종류만 배웠지 정렬을 여러 가지 방법으로 활용해본 경험이 거의 전무하다. 그래서... 너무 어렵게 생각했다.

 

2) 진짜 정답

 

intaehwang.tistory.com/16

[프로그래머스] 연습문제 - 문자열 내 마음대로 정렬하기, C++

결국엔 모르겠어서 힌트만 찾으려고 하다가 코드를 봐버렸다. 역시나 sort() 함수에서 커스텀 함수를 만들어 비교해서 정렬하는 간단한 문제였다. 근데 난 C++을 안 배워서 그런지 정렬한 경험이 부족해서 그런 건지 아니면 그냥 사고력이 부족한 건지는 모르겠지만 아직도 compare를 어떻게 짜야하는지 잘 모르겠다.

 

그런데 저 분의 코드를 보고 나는 깜짝 놀랐다. 너무 간결했고, 방법만 알았다면 진짜 쉬운 문제였던 것이다. (애초에 level 1 문제니까)

그래서 진지하게 C++ 책을 사야 하는지... 아니면 이렇게 문제를 풀면서 하나씩 배우는 게 맞는지 잘 모르겠다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int k;
bool cmp (string a, string b)  {
    if (a[k] != b[k]) return a[k] < b[k];
    else return a < b;
}
vector<string> solution(vector<string> strings, int n) {
    k = n;
    sort(strings.begin(), strings.end(), cmp);
    return strings;
}

 

이 cmp 함수에 a, b는 vector인 strings에서 값 두 개를 비교할 수 있게 해주는 것. 그럼 cmp 하나만으로 자동으로 strings의 시작부터 끝까지 훑으면서 하나하나 모든 값을 비교한다는 것일까? 와중에 전역 변수로 n을 끌고 와서 그 순서로 오름차순 비교할 수 있게 하는 아이디어까지 나는 아직도 한참 멀었다. 발상 자체가 안된달까... 코드를 보니 무슨 소리인지는 알겠지만 어떤 원리로 저게 작동하는지는 잘 모르겠다. 

compare 함수에 대한 활용법을 공부해 봐야겠다...

 

너무 간결해서 충격....