24/08/02 - 문자열 내 마음대로 정렬하기(C++, JS)

1. 문자열 내 마음대로 정렬하기(https://school.programmers.co.kr/learn/courses/30/lessons/12915)

 

문제를 요약하자면, 문자열의 인덱스 n번째 글자를 기준으로 문자열을 오름차순 정렬하는 것이다. 이때, 만약 n번째 글자가 같다면 해당 문자열은 사전순으로 정렬한다.

 

해서, 내가 맨 처음 사용한 방법은 다음과 같다.

1. 문자열을 사전 순으로 정렬
2. 반복문을 돌려 i번째 문자열과 i + 1 번째 문자열의 인덱스 n을 비교
3. 만약 i번째 문자열의 인덱스 n 쪽이 i + 1 번째 문자열의 인덱스 n 보다 크다면 swap()을 사용해 서로 교환
4. 2 ~ 3 을 계속 반복
5. i + 1 이 문자열 개수 만큼 오면 반복문 종료

while(1)
{
    if(answer[i][n] > answer[i + 1][n] && i + 1 <= strings.size() - 1)
    {
        answer[i].swap(answer[i + 1]);
    }
    i++;
    
    if(i + 1 == strings.size())
    	break;
}

 

하지만 이렇게 되면 작은 문제가 있다.

반복문 특성상 이미 한 번 지났던 부분은 다시 돌아갈 수 없는데, 그렇게 되면 앞 부분에 아직 정렬이 덜 끝난 상태가 될 수 있다. 글로는 설명을 다 못하여 간단한 예시를 들자면, 다음과 같다.

• 3    2    1    // 초기 상태. 첫번째와 두번째 값을 비교
• 2    3    1    // 비교 후 교환 완료. 두번째와 세번째 비교
• 2    1    3    // 반복문 끝

 

반복문에서 i는 계속 더해지고 있다. 그래서 문자열은 첫번째와 두번째, 두번째와 세번째, 세번째와 네번째, i번째와 i+1번째를 비교하는 형식이다.

 

하지만 이렇게 되면 예시처럼 제대로 된 정렬이 되지 않는다.

그래서 나는 i + 1이 마지막에 도달하면 다시 i를 초기화 시켜주기로 했다. 하지만 이렇게 되면 계속 반복될 뿐이다. 이를 해결하기 위해 나는 교환이 일어날 때마다 changeCount를 더해주기로 했다. changeCount != 0은 정렬이 1번 이상은 일어났다는 소리고, changeCount = 0은 더이상 정렬이 일어나지 않았다는 소리다. 즉, 이미 정렬된 상태라는 뜻이다.

하여, 최종적인 코드는 다음과 같다. 

// c++ 첫번째 방법
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(vector<string> strings, int n) {
    vector<string> answer = strings;
    int i=0;
    int changeCount = 0;
    
    sort(answer.begin(),answer.end());
    
    while(1)
    {
        if(answer[i][n] > answer[i + 1][n] && i + 1 <= strings.size() - 1)
        {
            answer[i].swap(answer[i + 1]);
            changeCount++;
        }
        i++;
        
        if(i + 1 == strings.size() && changeCount != 0)
        {
            i = 0;
            changeCount = 0;
        }
        else if(i + 1 == strings.size() && changeCount == 0) // 정렬이 일어나지 않았다는 건 이미 정렬이 끝났다는 소리다.
            break;
    }
    
    return answer;
}

 

 

다음은 조금 더 간단한 방법이다. 문자열 맨 앞에 문자열 n번째 인덱스에 있는 문자를 붙인다. 그 다음 사전 순으로 정렬을 하고, 맨 앞에 붙였던 문자를 제거한다.

 

// c++ 두번째 방법
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(vector<string> strings, int n) {
    vector<string> answer = strings;
    
    for(int i=0; i<strings.size(); i++)
    {
    	// n번째 글자를 맨 앞에 붙인다.
        answer[i] = answer[i][n] + answer[i];
    }
    
    sort(answer.begin(),answer.end());	// 사전 순으로 정렬
    
    for(int i=0; i<strings.size(); i++)
    {
    	// 맨 앞에 있던 문자를 제거한다.
        answer[i].erase(answer[i].begin());
    }
    
    return answer;
}

 

 

 

JS 도 C++ 두번째 방법과 같은 방법을 사용했다.

// js
function solution(strings, n) {
    var answer = strings;
    
    for(var i=0; i<answer.length; i++){
        answer[i] = answer[i][n] + answer[i];
    }
    answer.sort();
    
    for(var i=0; i<answer.length; i++){
        answer[i] = answer[i].replace(answer[i][0], "");
    }
    
    return answer;
}