[코딩테스트] 문자열 내 마음대로 정렬하기 (12915, Lv1)

Ⅰ. 문제

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

 

---

 

Ⅱ. 접근 방법

이 문제의 핵심은

정렬 기준을 어떻게 설정할 것인가

입니다.
 
정렬 기준을 언어로 풀면 다음과 같습니다.

1. 두 문자열 s1, s2를 비교할 때
   • s1.charAt(n)과 s2.charAt(n)을 먼저 비교한다.
2. 만약 두 문자의 값이 다르면
   • 그 차이를 그대로 반환한다. (앞에 올지 뒤에 올지 결정)
3. 두 문자가 같다면
   • 문자열 전체를 s1.compareTo(s2)로 비교한다.

 
자바에서는 이 로직을 Comparator<String>으로 구현해서
Arrays.sort 또는 Collections.sort에 넘기면 됩니다.
 

---

Ⅲ. 정답 풀이

Arrays.sort + 익명 Comparator 사용

import java.util.Arrays;

class Solution {
	public String[] solution(String[] strings, int n) {
    	Arrays.sort(strings, (s1, s2) -> {
        	// 1. n번째 문자 비교
            char c1 = s1.charAt(n);
            char c2 = s2.charAt(n);
            
            if (c1 == c2) {
            	// 2. n번째 문자가 같다면 문자열 전체를 사전순 비교
                return s1.compareTo(s2);
            }
            
            // 3. n번째 문자가 다르면 그 차이로 정렬 기준 결정
            return c1 - c2;
        });
        
        return strings;
    }
}

• Arrays.sort(strings, (s1, s2) -> ...)
• charAt(n)으로 n번째 문자를 꺼내 기준으로 사용
• c1 == c2이면 s1.compareTo(s2)로 사전순 비교

이렇게 작성하면 문제에서 요구하는 정렬 규칙을 그대로 코드로 옮긴 것이 됩니다.
 

---

Ⅳ. 핵심 개념 정리

- Comparator와 람다식

Arrays.sort에 두 번째 인자로 Comparator를 넘기면 정렬 기준을 바꿀 수 있습니다.
기본 형태는 다음과 같습니다.

Arrays.sort(strings, new Comparator<String>() {
	@Override
    public int compare(String s1, String s2) {
    	// s1이 s2보다 앞에 와야 하면 음수
        // s1과 s2의 순서가 같으면 0
        // s1이 s2보다 뒤에 와야 하면 양수
        return 0;
    }
});

이걸 람다식으로 줄이면 다음과 같습니다.

Arrays.sort(strings, (s1, s2) -> {
	// 비교 로직
    return 0;
});

문자열 비교에서 자주 쓰는 메서드는 compareTo입니다.

• s1.compareTo(s2)
  • s1이 사전순으로 s2보다 앞이면 음수
  • 같으면 0
  • 뒤면 양수

 

---

 

- char 비교

char끼리는 정수처럼 비교할 수 있습니다.

char c1 = 'a';
char c2 = 'b';

int diff = c1 - c2;	// 'a' - 'b'은 97 - 98 → 음수

사전순으로 앞에 있는 문자의 코드값이 더 작기 때문에
c1 - c2가 음수면 c1이 앞에 오는 순서입니다.
 

---

 

- 새 배열을 만들 필요 없이 정렬만 해도 되는 이유

문제를 읽다 보면 정렬된 결과를 담는 새 배열을 만들어야 할지,
기존 strings 배열을 그대로 써도 되는지 고민될 수 있습니다.
프로그래머스에서는 매개변수 strings는 그대로 정렬해도 되고
그 결과를 그대로 반환해도 됩니다.
즉, 별도의 배열을 만들 필요 없이 strings 자체를 정렬한 후 반환하면 됩니다.
 
만약 원본 배열을 보존해야 하는 상황이라면,
정렬 전에 clone()이나 Arrays.copyOf로 복사해서 쓰면 됩니다.

String[] result = strings.clone();
Arrays.sort(result, ...);
return result;

이 문제에서는 굳이 그럴 필요는 없습니다.
 

---

 

Ⅴ. 시간 복잡도 분석

Arrays.sort는 내부적으로 TimSort 게열의 알고리즘을 사용하며,
일반적으로 O(NlogN)의 시간 복잡도를 가집니다.

• N = 문자열의 개수
• 각 비교에서 하는 일은
  • charAt(n) 접근: O(1)
  • compareTo는 최악의 경우 문자열의 길이만큼 비교하지만, 대부분의 입력에서 비교 길이는 짧은 편

이 문제의 입력 크기에서는 충분히 빠르게 동작합니다.
 

---

 

Ⅵ. 자주하는 실수와 체크 포인트

1. n번째 문자 비교만 하고, 문자열 전체 비교를 안 하는 경우
   • n번째 문자가 같을 때 원래 문자열 순서대로 남겨야 하는 것 아닌가 생각하기 쉽지만, 실제 요구사항은 문자열 전체를 사전순으로 정렬입니다.
   • 즉, if (c1 == c2) return s1.compareTo(s2); 이 부분이 꼭 필요합니다.
2. n번째 문자가 같은 경우에 직접 반복문을 돌려서 비교하는 경우
   • char 배열로 바꿔서 직접 비교해도 되지만 자바에서는 compareTo가 이미 잘 구현돼 있으므로 그대로 사용하는 편이 간단합니다.
3. Comparator 반환값 의미를 헷갈리는 경우
   • compare(a, b)의 반환값이
     • 음수 → a가 b보다 앞
     • 0 → 위치 같음
     • 양수 → a가 b보다 뒤
   • 이 규칙만 기억하면 정렬 기준 설계가 훨씬 편해집니다.

 

---

 
이 문제는 정렬 자체보다는 정렬 기준을 어떻게 설계하는지를 연습하기 좋은 문제입니다.
이번 문제를 통해 다음 내용을 정리할 수 있습니다.

• Arrays.sort에 Comparator를 넘겨 정렬 기준을 바꾸는 방법
• 문자열에서 특정 인덱스의 문자를 기준으로 정렬하는 방법
• 기준 1순위, 2순위(보조 기준)를 함께 적용하는 방법

이 문제를 확실히 이해하고 나면,

• "가장 큰 수"처럼 문자열을 이어 붙이는 기준을 직접 설계하는 문제
• 여러 필드(나이, 이름, 점수 등)를 가진 객체 리스트를 정렬하는 문제

에서도 훨씬 수월하게 Comparator를 구성할 수 있습니다.