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

 

📝 TIL

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

 

제한사항

strings는 길이 1 이상, 50이하인 배열입니다.

strings의 원소는 소문자 알파벳으로 이루어져 있습니다.

strings의 원소는 길이 1 이상, 100이하인 문자열입니다.

모든 strings의 원소의 길이는 n보다 큽니다.

인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

 

 

입출력 예

입출력 예 #1

strings	n	return
["sun", "bed", "car"]	1	["car", "bed", "sun"]
["abce", "abcd", "cdx"]	2	["abcd", "abce", "cdx"]

 

---

🦔 설계 및 시도

처음에 map을 사용하여 각 strings의 n을 key로,

나머지는 value로 묶어서 처리하려고 했는데

중요한 사실을 놓치고 있었다

 

바로 Map은 key가 중복될 수 없다 😅

따라서 n번째 인덱스 값이 동일하면 기존의 값이 덮어 씌워짐...

 

또 값이 동일할 경우 사전순으로 정렬해야 하기 때문에

다른 방법을 고안해야 했다

 

이런 저런 방식을 찾아보니 ..!

자바 배열 기본 정렬인 Arrays.sort()와 함수형 인터페이스인 Comparator를 써야했다

이펙티브 자바를 읽으면서 Comparator에 대해 몇 번 찾아봤지만

직접 구현한 경험이 적어 연관짓지 못했다

 

 

🔥 풀이에 사용된 개념

Arrays.sort()

- 자바에서 배열을 정렬할 때 사용하는 기본 메서드

- java.util.Arrays 클래스에 포함됨

- String[]은 사전순, int[], double[]은 오름차순

 

Arrays.sort(array)

- 배열을 기본 기준으로 오름차순 정렬

 

Arrays.sort(array, comparator)

- 배열을 직접 정의한 기준으로 정렬

- comparator 자리에는 두 값을 비교하는 로직(비교 함수)

 

 

Comparator

- 정렬 기준 인터페이스

- 정렬을 직접 정의하고 싶을 때 사용

- Comparator<T>는 함수형 인터페이스, compare(T o1, T o2) 메서드를 구현해야 한다!

 

"string".compareTo(String anotherString)

- 두 문자열을 유니코드 기준으로 사전순 기준 정렬할 때 사용

- 두 수의 차를 이용하기에, 음수면 현재 문자열이 더 앞, 양수면 현재 문자열이 뒷 순서

 

Character.compare(char x, char y)

- 두 문자 char 을 비교할 때 사용

- x<y 음수, x==y 0, x>y 양수

- 

 

 

예시) 문자열 n 번째 문자 기준으로 비교하기

 Comparator<String> comp = new Comparator<String>() {
     public int compare(String s1, String s2){
         return Character.compare(s1.charAt(n), s2.charAt(n));
     }
}

 

람다식으로도 작성 가능하다

 

Arrays.sort(strings, (s1, s2) -> {
      if(s1.charAt(n) == s2.charAt(n)){
          return s1.compareTo(s2);
      }
      return Character.compare(s1.charAt(n), s2.charAt(n));
});

---

 

💡 풀이 소스 코드

 

시간복잡도 : O(n log n)

공간복잡도 : O(1) / Comparrator 객체는 생성되지만 고정된 크기

 

import java.util.*;
class Solution {
    public String[] solution(String[] strings, int n) {
        String[] answer = {};
        
        Arrays.sort(strings, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2){
                if(s1.charAt(n)==s2.charAt(n)){
                    // 사전순 정렬
                    return s1.compareTo(s2); 
                } else {
                    // n번째 문자 비교
                    return Character.compare(s1.charAt(n), s2.charAt(n));
                }
            }
        });
        return strings;
    }
}

 

---

🚀 새로 배운 내용

- Arrays.sort(array, Comparator)을 사용해 배열을 원하는 기준으로 정렬할 수 있음

- Comparator<String> 인터페이스를 사용하여, compare(s1, s2)를 오버라이딩 하여 정렬 기준을 직접 지정할 수 있음

- s1.compareTo(s2)를 이용하여 문자열 사전순 비교가 가능하다

 

 

 

---

😺  느낀점

- 각 자료구조의 특징 및 제한 조건을 정확하게 이해할 필요가 있다고 느꼈다

- util이나 다양한 함수형 인터페이스에 대해서 좀 더 공부해야겠다

 

 

*소스 코드는 다음 깃허브에 올라옵니다 - https://github.com/s0ooo0k/Algorithm_Study

GitHub - s0ooo0k/Algorithm_Study: Algorithm Study 문제 및 풀이