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

문제 설명

문자열로 구성된 리스트 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] 입니다.

 

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/12915

---

생각보다 문제를 제대로 이해하기가 어려웠습니다. 푸는 방법 자체는 쉽습니다. 컬렉션 프레임워크를 안 쓰고 쓰고 풀려고 하다 보니까 코드 자체가 효율성이 좋아 보이진 않습니다. 버블 정렬이니까요. 괜한 짓을 한 것 같네요. 컬렉션에서 제공되는 sort가 더 빠를 것이기 때문입니다. 컬렉션을 적극 활용하면 더 간결한 코드를 만들어낼 수 있습니다.

 

위 문단을 써놓은 시점에서 이 문제의 풀이 중 좋아요를 가장 많이 받은 신박한 코드로 채점을 해보니까 제 코드보다 20배가 느리다는 걸 발견했습니다. 심지어 제 풀이는 이중반복문을 썼는데도 말이죠. 잠시 그 이유를 생각해보면 다른 분의 풀이는 ArrayList를 새로 만들고, strings 개수만큼 add()하는 연산, sort(), answer 변수로 String 배열을 다시 만들고 답을 위해 다시 substring을 하는 연산 등이 필요 이상의 자원을 소모하는 것 같습니다.

 

반면에 제 코드는 정렬 자체는 버블 정렬을 사용하고 이중반복문까지 들어갔지만 스왑을 위한 temp 변수가 만들어지는 것 외에는 메모리 낭비가 없습니다. answer 변수도 사용하지 않고 파라미터로 받은 참조변수 strings을 정렬하기 때문에 strings를 리턴합니다. import도 하지 않습니다. 생각보다 연산 속도에서 차이가 많아 신기하네요. 나름대로 불필요한 연산을 줄이기 위해 고민하면서 작성한 보람이 있습니다. 코드가 길다고 해서 복잡하다고 해서 성능이 안 좋으리란 법이 없습니다. 버블 정렬은 구현이 매우 간단하지만 느리고 퀵 정렬이나 힙 정렬은 복잡하지만 엄청 빠른 것과 같습니다. 좋아요를 많이 받은 분의 코드는 다시 봐도 신박합니다. 같이 보시죠.

 

>mine(문제당 1ms ~ 2ms)

class Solution {
  public String[] solution(String[] strings, int n) {
        for (int i = 0; i < strings.length-1; ++i) {
            for (int j = i+1; j < strings.length; ++j) {
                if(strings[i].charAt(n) == strings[j].charAt(n)) {
                    if (strings[i].compareTo(strings[j]) > 0) {
                        String temp = strings[i];
                        strings[i] = strings[j];
                        strings[j] = temp;
                    }
                }
                else if (strings[i].substring(n).compareTo(strings[j].substring(n)) > 0 ) {
                    String temp = strings[i];
                    strings[i] = strings[j];
                    strings[j] = temp;
                }
            }
        }
        return strings;
  }
}

 

>someone's(문제당 20ms 내외)

import java.util.*;
class Solution {
    public String[] solution(String[] strings, int n) {
        String[] answer = {};
        ArrayList<String> arr = new ArrayList<>();
        for (int i = 0; i < strings.length; i++) {
            arr.add("" + strings[i].charAt(n) + strings[i]);
        }
        Collections.sort(arr);
        answer = new String[arr.size()];
        for (int i = 0; i < arr.size(); i++) {
            answer[i] = arr.get(i).substring(1, arr.get(i).length());
        }
        return answer;
    }
}