[코딩테스트 합격자 되기(Java)] 문제 50. 계수정렬 구현하기★

문제

인자로 받은 문자열s를 계수정렬로 정렬하여 반환하는 solution() 함수를 구현하세요.

 

제약조건

• string `s`의 길이는 1 이상 10,000 이하입니다. 

• `s`는 알파벳 소문자로 이루어져 있습니다.

 

 

입출력 예

s	return
hello	ehllo
algorithm	aghilmort

 

 

풀이 & 코드

계수 정렬 또는 카운팅 소트(counting sort):
컴퓨터 과학에서 정렬 알고리즘의 하나로서, 작은 양의 정수들인 키에 따라 객체를 수집하는 것.

쉽게 말하자면, 정렬된 어떠한 키에따라 빈도를 저장하는 정렬 알고리즘이다. 시간복잡도는 `O(n)`

때문에 키가되는 숫자를 알고있어야 하고, 키의 범위가 너무 크지 않아야한다.

 

위 문제에서는 a~z를 키로하고, String s에 나오는 문자의 빈도를 계산하면 된다.

 

1. 알파벳 소문자 개수만큼의 크기를 가진 배열을 생성한다 `arr = new int[26]`

 

2. s를 앞에서부터 순회하면서 `arr[문자에 맞는 index]`를 1씩 증가시킨다.

 

3.  arr 을 순회하면서 `index에 맞는 문자`를 나온 횟수만큼 출력한다.

 

문자에 맞는 index, index에 맞는 문자를 찾는 것은 쉽다.

index 0 이 a이고, 문자 `char`는 연산이 가능하므로,

`index  = 문자 - 'a'`

`문자 찾기 = index+'a'`

 

 

class Solution{
    String solution(String str){
        int[] arr = new int[26]; // a~z까지 빈도를 저장하는 배열
        for (int i = 0; i < str.length(); i++) {
            arr[str.charAt(i) - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            for(int j = 0; j < arr[i]; j++) sb.append((char)(i + 'a'));
        }
        return sb.toString();
    }
}

 

 

문제 답안 바로가기

codingtest_java/solution/50.java at main · retrogemHK/codingtest_java