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

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

 

---

Comparable 인터페이스를 구현한 Word라는 클래스를 만들었다. Comparable을 구현한 이유는 Collections.sort() 메서드를 사용하기 위해서이다. 보통 String이나 int같은 타입은 대소관계가 명확하지만, 이 문제같은 경우 주어진 문자열의 n번째 문자의 대소를 비교해야하기 때문에 일반적인 정렬로는 불가능하다.

 

따라서 Comparable을 구현하여 정렬의 기준을 커스터마이징 한 것이다.

    static class Word implements Comparable<Word>{

        String word;
        char c;

        public Word(String w, char c){
            word=w;
            this.c = c;
        }

        @Override
        public int compareTo(Word o) {

            return c - o.c;
        }
    }
    //나보다 Word o가 클 때
    //return -1
    //나보다 Word o가 작을 때
    //return 1
    //나랑 Word o가 같을 때
    //return 0

그리고 n번째 문자의 대소관계가 동일할 경우, 문자열의 사전순으로 출력해야 하므로 미리 주어진 문자열 strings를 정렬 해준다.

 

List<Word>라는 리스트를 만들어 strings가 갖는 문자열을 이용해 Word 객체를 생성하여 담아준다.

        Arrays.sort(strings);

        List<Word> list = new ArrayList<>();

        for(int i=0; i<strings.length; i++) {
            String word = strings[i];
            char character = strings[i].charAt(n);

            list.add(new Word(word, character));
        }

이제 Comparable을 구현한 것이 제 역할을 해줄 때이다.

Collections.sort(list);

위에서도 말했듯 List<Integer> 같이 정수를 담는 리스트는 Comparable을 구현하지 않아도 대소관계가 명확하기에 구현할 필요가 없으나, Word라는 클래스는 멤버 변수로 문자열과 문자를 갖는데 어떤 것을 정렬 기준으로 삼을지 모르기에 알려주는 작업이라고 생각하면 쉬울 것 같다.

# Code </>

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution {

    static class Word implements Comparable<Word>{

        String word;
        char c;

        public Word(String w, char c){
            word=w;
            this.c = c;
        }

        @Override
        public int compareTo(Word o) {

            return c - o.c;
        }
    }

    public static String[] solution(String[] strings, int n) {

        Arrays.sort(strings);

        List<Word> list = new ArrayList<>();

        for(int i=0; i<strings.length; i++) {
            String word = strings[i];
            char character = strings[i].charAt(n);

            list.add(new Word(word, character));
        }

        Collections.sort(list);
        String[] answer = new String[list.size()];

        int idx = 0;
        for(Word w : list)
            answer[idx++] = w.word;

        return answer;
    }
/*
    public static void main(String[] args) {

        String[] str = {"abce", "abcd", "cdx"};
        int n = 2;

        System.out.println(Arrays.toString(solution(str, n)));
    }*/
}

 

다음은 버블정렬을 이용하여 푼 코드이다.

import java.util.Arrays;

public class Solution {

    public static String[] solution(String[] strings, int n) {

        Arrays.sort(strings);

        for(int i=0; i<strings.length; i++)
            for(int j=1; j<strings.length; j++) {

                String front = strings[j];
                String before = strings[j - 1];
                String tmp = "";

                if (front.charAt(n) < before.charAt(n)) {
                    tmp = strings[j];
                    strings[j] = strings[j - 1];
                    strings[j - 1] = tmp;
                }
            }

        String[] answer = strings;
        return answer;
    }
/*
    public static void main(String[] args) {

        String[] str = {"abce", "abcd", "cdx"};
        int n = 2;

        System.out.println(Arrays.toString(solution(str, n)));
    }*/
}