[Java] 자바 알고리즘, 문자열 내 마음대로 정렬하기, Programmers level

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

문제 설명

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

 

나의 풀이

import java.util.*;

class Solution {
	public String[] solution(String[] strings, int n) {
		List<String> list = new ArrayList<String>();
		for (String str : strings) {
			list.add(str);
		}

		list.sort(new Comparator<String>() {
			@Override
			public int compare(String str1, String str2) {

				return str1.charAt(n) - str2.charAt(n) == 0 ? 
						str1.compareTo(str2) : str1.charAt(n) - str2.charAt(n);
			}
		});
		String[] answer = new String[list.size()];
		for (int i = 0; i < list.size(); i++) {
			answer[i] = list.get(i);
		}
		return answer;
	}
}

- 이런 문제는 수준급 알고리즘 경험자가 아니라면 순수배열보다는 Collection 객체들(List, Map, Set 등)의 라이브러리 기능을 이용하는 것이 저같은 초보자에게 더 적당할 것 같다고 생각하여. 배열의 요소들을 먼저 list 객체에 담았다. 

List 컬렉션은 sort메소드를 이용하여 요소들을 정렬하는 라이브러리 메소드를 제공하고 있는데 까다로운 것이 Comparator 익명객체를 파라미터로 받아 compare 메소드를 오버라이딩 해주어야한다. 

이전 글 https://sas-study.tistory.com/105 을 참조하여 해당 오버라이딩 메소드를 작성하였다. 기본적으로 미리 알아두면 좋을만한 기능이지만, 업무를 하다보면 사용할 일이 거의 없기 때문에 알고리즘을 쓸때 수시로 써야겠다고 생각했다.

return 문을 간단히 설명하자면 charAt은 char 형 값을 반환한다.(ASCII 코드값으로 떨어진다.) 그렇기 때문에 값비교가 가능하고 둘을 뺀 값이 0이라는 것은 같은 값이기 때문에 이경우는 문자열 비교 메소드인 compareTo 메소드를 사용하여 사전에서 빠른 문자열이 앞으로 오도록 처리하였다.

 

다른사람의 풀이

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

- 프로그래머스의 다른사람 풀이를 가져와봤다. 생각만 했던 풀이방법이었는데 실제로 구현하는 코드를 보니 더 신기했다. 처음에는 이분의 알고리즘처럼 풀어보려고 했으나 자잘자잘한 변환과정이 너무 많은것 같아 성능이슈가 발생할 가능성이 많다고 생각했다. 왜냐하면 위의 알고리즘은 index를 가지고 있어야 하는데 그것을 자르던 어떻게하던 변환과정이 하나 더 추가되기 때문이었다. 레벨1정도의 문제에서는 굳이 중요하지는 않겠지만 좀더 좋은 성능을 내고자하는 욕심이 생긴것 같아서 뿌듯했다.

 

 

나의 다른 풀이

좀더 적은 코드로 효율적인 풀이방법이 떠올라서 풀어보았습니다.

import java.util.*;

class Solution {
	public String[] solution(String[] strings, int n) {
		Arrays.sort(strings, new Comparator<String>() {

			@Override
			public int compare(String s1, String s2) {
				return s1.charAt(n) - s2.charAt(n) != 0 
                    ? s1.charAt(n) - s2.charAt(n) 
                    : s1.compareTo(s2); // 두 문자중 사전순으로 빠른거.
			}
			
		});
        return strings;
	}
}

- n 번째의 인덱스 문자를 비교하고 0(같은경우) 인 경우는 compareTo 메소드를 이용하여 사전순으로 더 빠른 문자가 앞으로 오도록 정렬하도록 풀이를 더욱 간단하게 변경.

- 그리고 List로 굳이 변환하지 않고 바로 정렬함.