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

https://programmers.co.kr/learn/courses/30/lessons/12915

코딩테스트 연습 - 문자열 내 마음대로 정렬하기

 

문제 설명

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

제한 조건

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

---

 

문제 자체는 어렵지 않았다.

간단히 String 배열을 n번째 글자 기준으로 오름차순 정렬하면 되는 것이다.

문제를 보자마자 떠오른 건 버블 정렬이었다.

 

버블 정렬이란 인접한 두 수를 비교하여 작은 수와 큰 수를 교환하는 간단한 정렬 알고리즘이다.

예를 들면 다음과 같다.

5,3,4,7,2 숫자를 가지는 배열을 오름차순 정렬해보자.

 

첫 번째 인덱스를 기준으로 배열 끝까지 값을 비교하면 배열 끝에 가장 큰 값이 위치하게 된다.

결과 > 3 4 5 2 7

 

가장 큰 값은 정렬되었고 두 번째로는 0번째 인덱스부터 배열 크기의 -1까지 비교하여 정렬해주면 된다.

결과 > 3 4 2 5 7

 

5와 7이 정렬되었다. 세번째는 0번째 인덱스부터 배열 크기의 -2까지 비교하여 정렬한다.

결과 > 3 2 4 5 7

 

마지막으로 0번째 인덱스 부터 배열 크기의 -3까지 비교하여 정렬한다.

결과 > 2 3 4 5 7

 

배열 크기의 -1만큼의 단계가 필요하며 각 단계마다 비교 횟수가 하나씩 줄어든다.

즉, 5개의 숫자 오름차순 정렬을 위한 비교 횟수는 총 4+3+2+1=10회이다.

시간 복잡도 : O(N * N)

---

n번째 글자 기준으로 버블 정렬을 구현하였다.

단, 같은 문자열일 경우 사전 순으로 앞선 문자열이 앞쪽에 위치해야 하기 때문에 compare()이라는 함수를 구현하였다.

compare(s1, s2)은 비교해야 하는 문자열을 인자로 받아 한 글자씩 비교하여 앞글자부터 사전적으로 큰 문자가 나오는 경우 해당 문자열을 반환하는 함수이다.

if문을 통해 만약, 앞쪽에 있는 문자열이 사전적으로 뒤에 있을 문자열일 경우 서로 값을 교체해준다.

 

내 코드

class Solution {
    public String[] solution(String[] strings, int n) {
        String[] answer = {};
        String temp ="";
        
        for(int i=0;i<strings.length-1;i++){
            for(int j=0;j<strings.length-1-i;j++){
                if(strings[j].charAt(n)>strings[j+1].charAt(n)){
                    temp=strings[j+1];
                    strings[j+1]=strings[j];
                    strings[j]=temp;
                }
                else if(strings[j].charAt(n)==strings[j+1].charAt(n)){
                     String ss = compare(strings[j],strings[j+1]);
                        if(ss.equals(strings[j])){
                            temp=strings[j+1];
                            strings[j+1]=strings[j];
                            strings[j]=temp;
                        }
                }
        }  
}
        return strings;
    }
    
    String compare(String s1,String s2){
        String s="";
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i)>s2.charAt(i)) {
                s=s1; break;
            } 
            else if(s1.charAt(i)==s2.charAt(i)) continue;
            else{
                s=s2; break;
            }
        }
        return s;
    }
}

 

다른 풀이

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;
    }
}

 

arr이라는 ArrayList를 만들어 각 요소의 n번째 글자와 해당 문자열을 이어 붙인 문자열을 하나씩 추가한다.

예제를 예를 들면 배열 [sun,bed,car]를 [usun, ebed, acar]로 만드는 것이다.

리스트는 앞글자를 기준으로 정렬될것이고 반환하는 배열 answer는 리스트 항목에서 첫 번째 글자를 잘라 저장하면 된다.