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

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

문자열 문자들의 n번째 인덱스를 기준으로 문자열들을 정렬하는 문제이다.

 

이 문제는 쉬운문제이긴하지만 함정이 하나 있다. 

바로 인덱스 N의 문자가 같다면 사전 순으로 앞선 문자열이 앞쪽에 위치한다는 점이다.

이 문장을 헷갈리면 안된다. N의 문자가 같다면 그 뒤의 문자열로 사전순 정렬하는 것이 아닌 전체 문자열로 사전순 정렬한다는 것이다.

 

예를 들어 [abcd, abce, accd] , 2가 문제로 주어졌다고 하자.

2번째 인덱스가 모두 c로 같기 때문에 사전순으로 정렬해야한다. 

이때 2번째 인덱스 뒤의 문자열을 기준으로 사전순 정렬을 하게 되면 정답은 [abcd, acce, abcf]가 된다.

하지만 이 문제는 같다면 전체 문자열로 사전순 정렬해야한다. 따라서 [abcd,  abcf, acce]가 돼야 한다.

 

이를 구현하기 위해선 두 가지의 과정을 거쳐야한다.

 

1. 먼저 사전순으로 정렬한다.

2. 그 이후 N번째 알파벳순으로 정렬한다. 

 

뭔가 순서가 바뀐듯한 느낌이 들기도 하지만 먼저 사전 순으로 정렬을 해놔야 이후 N번째 알파벳 순으로 정렬해도 전체 문자열에 대한 사전순서가 유지된다.

이제 코드를 보자.

3. 내 코드

---

import java.util.*;
class Solution {
    public String[] solution(String[] strings, int n) {
        
        Arrays.sort(strings); // 먼저 사전순으로 정렬
        Arrays.sort(strings, (s1, s2) 
                    -> s1.substring(n, n + 1).compareTo(s2.substring(n, n + 1))); // n번째 문자 순으로 정렬
        
        return strings;
    }
}

시간 복잡도

• O(NlogN)

두 번의 sort()메서드를 사용했다. sort()메서드는 O(NlogN)으로 작동한다.