[프로그래머스/Lv.1] 문자열 내 마음대로 정렬하기(선택정렬)

문제 설명

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

 

 

 

❌ 실패풀이

for(int i=1;i<arr.length;i++) {
    for(int j=i;j>0;j--) {

        if(arr[j].charAt(n)<arr[j-1].charAt(n)) {
            String temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
        }else if(arr[j].charAt(n)==arr[j-1].charAt(n)){
            for(int k=0;k<arr[j].length();k++) {
                if(arr[j].charAt(k)<arr[j-1].charAt(k)) {
                    String temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                    break;
                }
            }
        }
    }
}
// 테스트케이스
String[] arr = {"abzcd","cdzab","abzfg","abzaa","abzbb","bbzaa"};
int n = 2;
/*
abzaa bbzaa abzbb abzcd cdzab abzfg 
*/

 

처음에 문제설명대로 주어진 n인덱스에대한 정렬을 먼저 수행하기위해

삽입정렬(어느정렬이든 상관없을것같다)을 사용해 해당 문자열의 charAt(n) 번째를 비교해 정렬했다.

하지만 문제에서 주어진 테스트케이스는 통과했지만

코드제일 윗줄처럼 n인덱스의 자리를 모두 z로 같게하고 순서를 섞어놓으면 원하는 결과가 나오지 않았다.

 

주어진 n인덱스에 대한 정렬을 먼저수행하며 정렬수행 도중 해당 n자리의 문자가 같을경우

다시 한번 for문을 반복하며 정렬과정을 수행하므로 설령 정답이라해도 코드도 복잡해보이고 뒤죽박죽이다.

map을 활용해서 각 순서를 넣어야하나.. list를 써볼까 하다가 생각을 조금 바꿔보았다.

 

굳이 n번째 인덱스로 정렬하고 동일한경우에 한해서 사전순으로 재정렬하는것보다

처음부터 사전순으로 정렬해둔 뒤 n번째 인덱스순으로 정렬하면 되지않을까?

 

 

 

⭕ 풀이

import java.util.*;

class Solution {
    public String[] solution(String[] arr, int n) {
    
        Arrays.sort(arr);// 1차정렬 (사전순)
        
        for(int i=1;i<arr.length;i++) { // 2차정렬 (n번째인덱스순)
            for(int j=i;j>0;j--) {
                if(arr[j].charAt(n)<arr[j-1].charAt(n)) {
                    String temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }else{
                    break;
                }
            }
        }
        return arr;
    }
}

//테스트 케이스
String[] arr = {"abocd","cdoab","abofg","aboaa","abobb","bboaa","abddd","abzpp","zzaaa"};
int n = 2;
/*
1차정렬 후(사전순)
abddd aboaa abobb abocd abofg abzpp bboaa cdoab zzaaa 
2차정렬 후(n번째인덱스순)
zzaaa abddd aboaa abobb abocd abofg bboaa cdoab abzpp
*/

 

✅ 흐름

 

주어진 String배열 arr를 Arrays.sort로 사전순 정렬을 먼저 수행해준다.

그 다음 삽입정렬을 활용해 n번째 인덱스기준으로 정렬을 다시 수행해준다.

 

사전순으로 정렬한다면 첫글자가 a이므로 가장 뒤에있어야할 abzpp는 중간에 위치하게되고

가장 앞에있어야할 zzaaa가 제일 뒤로가지만

 

이렇게 정렬된 arr에서 2번째 인덱스의 글자 기준으로 다시한번 정렬을 수행해주면

zzaaa과 abzpp 둘다 원하는 결과의 위치로 가게된다.

 

 

삽입정렬에대해서 진행되는 과정은 이전에 포스팅해두었던 글을 참고하면 도움이 될것같다.

[Java] - JAVA - 삽입정렬(Insertion Sort)

 

 

 

채점에 통과한 뒤 다른분의 풀이를 보니 ArrayList를 사용해 주어진 strings문자열 앞에 n번째 인덱스를 더하셨다.

예를들면 car bed sun 이라면 usun ebed acar 이런식으로 list를 만들어준뒤 list자체를 정렬하였고

이렇게되면 acar ebed usun의 순서가 될것이며 이를 옮겨담는식으로 풀이하셨다.

역시 다른사람의 풀이를 보는게 재밌다.

 

 

 

-출처

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