[Algorithm] 문자열 내 마음대로 정하기

'문자열 내 마음대로 정하기' 정의는 다음과 같다.

 

문제 설명

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car]이고 n이 1이면 각 단어의 인덱스 1의 문자 u, e, a로 strings를 정렬합니다.

제한 조건

• strings는 길이 1 이상, 50이하인 배열입니다.
• strings의 원소는 소문자 알파벳으로 이루어져 있습니다.
• strings의 원소는 길이 1 이상, 100이하인 문자열입니다.
• 모든 strings의 원소의 길이는 n보다 큽니다.
• 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

입출력 예

strings	n	return
[sun, bed, car]	1	[car, bed, sun]
[abce, abcd, cdx]	2	[abcd, abce, cdx]

입출력 예 설명

입출력 예 1
sun, bed, car의 1번째 인덱스 값은 각각 u, e, a 입니다. 이를 기준으로 strings를 정렬하면 [car, bed, sun] 입니다.

입출력 예 2
abce와 abcd, cdx의 2번째 인덱스 값은 c, c, x입니다. 따라서 정렬 후에는 cdx가 가장 뒤에 위치합니다. abce와 abcd는 사전순으로 정렬하면 abcd가 우선하므로, 답은 [abcd, abce, cdx] 입니다.

 

다음과 같이 코드를 작성했다.

class Solution {
    public String[] solution(String[] strings, int n) {
        String[] answer = {};
        
        int length = strings.length;
        answer = new String[length];
        char[] idxValues = new char[length];
        int[] sortedIdx = new int[length];
        
        for (int i = 0; i < length; i++) {
            idxValues[i] = strings[i].charAt(n); 	// n번째 문자
            sortedIdx[i] = i;				// 정렬된 인덱스
        }
        
        int temp;
        char tmp;
        // 버블 정렬
        for (int i = length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
            	// 인덱스 문자 중복 확인
                if (idxValues[j] == idxValues[j + 1]) {
                    // 사전순 문자열 정렬 후 인덱스 저장 (sortedIdx)
                    if (strings[sortedIdx[j]].compareTo(strings[sortedIdx[j + 1]]) > 0) {
                        tmp = idxValues[j];
                        idxValues[j] = idxValues[j + 1];
                        idxValues[j + 1] = tmp; 
                        
                        temp = sortedIdx[j];
                        sortedIdx[j] = sortedIdx[j + 1];
                        sortedIdx[j + 1] = temp;
                    }
                }
                else if (idxValues[j] > idxValues[j + 1]) {
                    tmp = idxValues[j];
                    idxValues[j] = idxValues[j + 1];
                    idxValues[j + 1] = tmp;
                    
                    temp = sortedIdx[j];
                    sortedIdx[j] = sortedIdx[j + 1];
                    sortedIdx[j + 1] = temp;
                }
            }
        }
        
        // 정렬된 인덱스 배열 저장
        for (int i = 0; i < sortedIdx.length; i++) {
            answer[i] = strings[sortedIdx[i]];
        }
        
        return answer;
    }
    
}

1. idxValues[]에 n번째 문자를 저장한다.

2. n번째 문자 기준으로 스트링을 정렬(bubbleSort)한다.

3. 만약 n번째 문자 중복이 존재할 경우 해당 스트링들을 사전순으로 정렬한다.

4. sortedIdx[]에 strings[]를 정렬한 오름차순 인덱스 순서를 저장한다.

5. sortedIdx[]를 이용하여 strings[]로부터 정렬된 스트링 배열을 answer[]에 저장한다.

 

n번째 문자가 중복이 발생할 경우, 해당 스트링들을 사전순으로 정렬하는것이 문제라고 생각한다.

버블 정렬을 이용하여 스트링들을 비교하고, n번째 문자 중복시에는 String.compareTo()로 비교하여 사전순 정렬하였다.

idxValues[]도 정렬하고 있지만, 핵심은 sortedIdx[]이다. 정렬할 때마다 인덱스 값을 업데이트 한다.

정렬이 끝난 후에 sortedIdx[]를 strings[]의 인덱스 값으로 사용하여 정렬된 스트링배열 값을 얻을 수 있다.