프로그래머스 코딩테스트 연습: 문자열 내 마음대로 정렬하기

Q. 문자열 내 마음대로 정렬하기

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

제한 조건

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

 

*주의*   첫번 째 접근방법은 삽질의 끝판왕이니 임산부나 심신미약자들은 과감히 스킵하시기를 추천드립니다. 

 

접근 방법 1)

substring을 이용하여 strings를  (0~ n-1) , (n ~ end) 인덱스로 잘라내어 두가지 배열에 저장한 뒤                              strings[i].toCharArray()[0] :  index = n 을 기준으로 오름차순으로 정렬 ( index = n 의 원소가 같은경우에 while문을 통해서 strings 의 첫번째 원소부터 오름차순 정렬) 하는 방식이였다.

문제점: strings를 substring 으로 두개로 분리하였을 때, index = n 의 원소를 가지고 있는 배열을 오름차순으로 정렬하면, n의 원소를 가지고 있지 않은 배열도 같은 순서로 이동시켜야 하는 문제가 있었다. (결국 해결방법을 못찾아서 n원소를 포함하는 배열을 오름차순으로 정렬하는 이중 for문을 돌릴 때, 두 배열을 같이 이동시켰다. (효율성 따윈 개나줘버렷 ㅠㅠ...) 

public class Solution {

    public static String[] solution(String[] strings, int n) {

        String[] save = new String[strings.length];

        for (int i = 0; i < strings.length; i++) {
            String temp = strings[i].substring(0, n); //index 0 부터 n개까지 자른다!
            save[i] = temp;
            strings[i] = strings[i].substring(n);

        }

        for (int i = 0; i < strings.length - 1; i++)
            for (int j = i + 1; j < strings.length; j++) {
                int cnt = 0;
                if (strings[i].toCharArray()[cnt] >= strings[j].toCharArray()[cnt]) {

                    String temp = strings[i];
                    strings[i] = strings[j];
                    strings[j] = temp;

                    temp = save[i];
                    save[i] = save[j];
                    save[j] = temp;

                } else {

                    for (int k = 0; k < strings.length; k++) {
                        strings[k] = save[k] + strings[k];
                    }

                    while (cnt < strings[i].toCharArray().length && cnt < strings[j].toCharArray().length) {

                        if (strings[i].toCharArray()[cnt] >= strings[j].toCharArray()[cnt]) {

                            String temp = strings[i];
                            strings[i] = strings[j];
                            strings[j] = temp;

                            temp = save[i];
                            save[i] = save[j];
                            save[j] = temp;

                            break;
                        } else {
                            cnt++;
                        }
                    }
                    return strings;
                }
            }

        for (int i = 0; i < strings.length; i++) {
            strings[i] = save[i] + strings[i];
        }

        return strings;
    }

    public static void main(String[] args) {

        String[] strings1 = {"sun", "bed", "car"};
        int n1 = 1;
        for (String s : solution(strings1, n1))
            System.out.print("{" + s + "} ");
        System.out.println();


        String[] strings2 = {"abce", "abcd", "cdx"};
        int n2 = 2;
        System.out.println();
        for (String s : solution(strings2, n2))
            System.out.print("{" + s + "} ");

    }
}

 결과는 정확성 100점만점에 8.3점...   이라는 굴욕을 안고 고민을 거듭하다가 구글링을 하기로 마음먹었다.

(참조 : https://cnwlcjf.tistory.com/40 )

프로그래머스 level1 문제 : 문자열 내 마음대로 정렬하기(java)

접근 방법 2)  

index 가 n 인 글자가 첫번째 정렬 순서가 되는 점을 이용하여 첫번째 글자에 index = n 의 원소를 추가하여 오름차순으로 정렬한 뒤 

첫번째 원소를 substring으로 잘라내는 방법이다.

import java.util.ArrayList;
import java.util.Collections;

public class Solution {

    public static String[] solution(String[] strings, int n) {

        String[] answer = {""};
        ArrayList<String> list = new ArrayList<>();

        for(int i = 0; i < strings.length; i++)
            list.add(strings[i].charAt(n) + strings[i]);

        Collections.sort(list);
        answer = new String[list.size()];
        for(int i = 0; i < list.size(); i++)
            answer[i] = list.get(i).substring(1);

        return answer;
    }
}

코드 길이도 매우 간결하고 심지어 정확하기까지하다... 세상에 이런 풀이가 나올 수 있다는 것에 감탄을 금치 못하였다. 

이외에도 '버블정렬' 을 이용한 풀이방법도 있었다.

버블정렬에 대한 설명 (출처: https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html ) 

 

접근 방법3)  

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 

public class Solution {

        public static String[] solution(String[] strings, int n) {

        int range = strings.length - 1;
        for (int i = 0; i < range; i++) {
            for (int j = 0; j < range - 1; j++) {
                if (compareString(strings[j], strings[j + 1], n, n)) {
                    swapString(strings, j, j + 1);
                }
            }
        }
        return strings;
    }

    public static boolean compareString(String a, String b, int n, int now) {
        if (a.charAt(now) > b.charAt(now))
            return true;
        else if (a.charAt(now) == b.charAt(now)) {
            int next = (n == now) ? 0 : ++now;
            if (n == next) next++;
            return compareString(a, b, n, next);
        } else {
            return false;
        }
    }

    public static void swapString(String[] strings, int a, int b) {
        String temp = strings[a];
        strings[a] = strings[b];
        strings[b] = temp;
    }
 }

 

Collections 함수에 sort 기능으로 정렬이 가능하다는 것을 알게되었고, 추가적인 다른 기능들도 공부해야겠다.

버블정렬외에도 선택정렬, 삽입정렬, 셸정렬, 합병정렬, 퀵정렬, 힙정렬 등 다른 정렬들도 많고 각 정렬마다 시간복잡도에서 많은 차이를 보인다고 한다. 코딩테스트에서 효율성을 보는 곳도 많기 때문에 정렬에 대한