[LeetCode] 791. Custom Sort String

https://leetcode.com/problems/custom-sort-string/

Custom Sort String - LeetCode

Custom Sort String.

 

 

문자를 정렬하면 되는 문제다.

하지만 조금 다른점이 있다면 문자가 a,b,c,d,... 순서가 아닌 임의로 정한 순서로 정렬을 해야 한다.

문제의 예시에서는 order = "cba"로 정렬순서는 c가 1등, b가 2등, a가 3등 순서이고,

str = "abcd"로 이걸 order에 맞게 정렬해야한다.

c,b,a 순서이므로 abc=>cba가 된다. 

이때 d는 어떻게 하느냐? 상관없다고 한다. 어디에든 붙여주자.

 

풀이는 어떻게 해야할까?

간단하다! order대로 알파벳-수와 수-알파벳을 매핑시켜준다.

그리고 알파벳을 그 수로 바꾼 후 수를 정렬해준다.

마지막으로 수를 다시 알파벳으로 치환하면 끝난다.

 

1. order대로 알파벳-수와 수-알파벳을 매핑시켜준다.

 

알파벳은 26자가 최대이고 이는 문제에서도 언급되었으므로 배열의 길이는 26이면 된다.

알파벳을 숫자로 매핑시키기 위한 c2i (char to int)와 i2c (int to char) 를 만들어준다.

이 때 알파벳을 나타내는 방법은 a=0, b=1, c=2,...로 나타낸다.

c2i는 순서에 쓰이지 않을 -1로 초기화 시켜준다.

int c2i[26];
int i2c[26];
for (int i=0; i<26; i++) c2i[i] = -1;

 

본격적으로 매핑을 시켜준다.

알파벳을 a=0, b=1, c=2와 같이 바꾸는 방법은 아래와 같다.

기본적으로 알파벳을 int로 변환하면 아스키코드값으로 바뀌는데, 아스키코드값 내에서도 알파벳은 알파벳순서대로 되어 있다.

따라서 알파벳을 아스키코드로 바꿔주고 가장 첫번째는 a의 아스키코드값을 빼면 우리가 원하는 대로 나온다.

order 배열을 살펴보며 order의 순서대로

c2i[alphabet] = _order 로,

i2c[_order] = alphabet 으로 만들어 주자. (위의 for문)

그리고 order에 들어있지 않은 알파벳은 상관없으므로 order의 마지막 순서 이후부터 그냥 차례로 넣어주자. (아래 for문)

for (int i=0; i<order.size(); i++) {
	c2i[order[i]-'a']=i;
	i2c[i] = order[i]-'a';
}
int idx = order.size();
for (int i=0; i<26; i++) {
	if (c2i[i]==-1) {
		c2i[i] = idx;
		i2c[idx++] = i;
	}
}

 

마지막으로 최대 길이가 200이므로 정답을 넣을 200 길이의 배열 arr을 만들어준다.

이 arr에 들어갈 수는 c2i를 참고하여 주어진 알파벳들의 중요도로 넣어주면 된다.

그리고 이를 정렬하고, 이걸 다시 알파벳으로 바꿔 결과값에 추가해주면 된다.

정렬에는 다양한 방법이 있지만, 여기서는 따로 구현하지 않고 <algorithm>에 제공되는 

quick sort기반의 sort()를 사용했다.

 

string ret = "";
int arr[200];
for (int i=0; i<str.size(); i++) arr[i] = c2i[str[i]-'a'];
sort(arr,arr+str.size());
for (int i=0; i<str.size(); i++) ret.push_back((char)(i2c[arr[i]]+'a'));

다시 풀이를 살펴보자.

 

예시에서 order = "cba" , str = "abcd" 였으므로

 

c2i는 아래와 같고

Alphabet	0(a)	1(b)	2(c)	3(d)
Order	2	1	0	3

 

i2c는 아래와 같다.

Order	0	1	2	3
Alphabet	2(c)	1(b)	0(a)	3(d)

 

이때 arr은 아래와 같이 만들어 주면 된다.

str	0	1	2	3
order	2	1	0	3

 

그리고 이 arr을 정렬 시켜준다.

str	2	1	0	3
order	0	1	2	3

 

마지막으로 str 부분을 다시 알파벳으로 바꿔 결과에 추가해준다.

str	c	b	a	d
order	0	1	2	3

 

전체 코드는 아래와 같다.

class Solution {
public:
    string customSortString(string order, string str) {
        int c2i[26];
        int i2c[26];
        string ret="";
        for (int i=0; i<26; i++) c2i[i] = -1;
        for (int i=0; i<order.size(); i++) {
            c2i[order[i]-'a']=i;
            i2c[i] = order[i]-'a';
        }
        int idx = order.size();
        for (int i=0; i<26; i++) {
            if (c2i[i]==-1) {
                c2i[i] = idx;
                i2c[idx++] = i;
            }
        }
        int arr[200];
        for (int i=0; i<str.size(); i++) arr[i] = c2i[str[i]-'a'];
        sort(arr,arr+str.size());
        for (int i=0; i<str.size(); i++) ret.push_back((char)(i2c[arr[i]]+'a'));
        return ret;
    }
};