프로그래머스 - 문자열 내림차순으로 배치하기 java

12917번

코딩테스트 연습 - 문자열 내림차순으로 배치하기 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 문자열 내림차순으로 배치하기

---

풀이

✅ 대문자는 소문자보다 작은 것으로 간주한다.

=> 코드 상에서 문자 비교 시 기본으로 대문자가 소문자보다 작다. ex) 'A' < 'a'

 

• 풀이1

public String solution(String s) {
	char[] array = s.toCharArray();
	Arrays.sort(array);
	return new StringBuilder(new String(array)).reverse().toString();
}

✅ Arrays.sort()

: 배열을 오름차순으로 정렬

✅ StringBuilder reverse()

: StringBuilder 내의 문자열들을 역순으로 반환

 

오름차순 정렬 후 역순으로 바꾸어 내림차순 정렬을 만들었습니다.

 

✔ 테스트 케이스 처리 속도: 평균 0.43ms / 최대 0.57ms

 

• 풀이2

public String solution(String s) {
	return Stream.of(s.split(""))
			.sorted(Collections.reverseOrder())
			.collect(Collectors.joining());
}

Stream 을 활용했습니다. 역시 Stream으로 푸는 게 간단하고 이쁘긴 하네요.

 

만약 변수 s를 그냥 Stream화 시키면 통째로 Stream이 되어서 문자 하나하나를 정렬하기가 더 복잡해져요.

그래서 우선 문자열 stream을 만들기 위해 split으로 자른 후 Stream으로 변환했어요.

 

✅ Stream<T> sorted(Comparator<? super T> comparator)

✅ public static <T> Comparator<T> reverseOrder()

: sorted와 reverseOrder를 활용해 내림차순으로 바로 정렬할 수 있어요.

✅ public static Collector<CharSequence, ?, String> joining()

: 나열된 stream을 붙여서 String 타입으로 반환하면 끝입니다.

 

✔ 테스트 케이스 처리 속도: 평균 3.5ms / 최대 5.07ms

 

• 풀이3

public String solution3(String s) {
	char[] s_arr = s.toCharArray();
	for(int i=0; i<s_arr.length-1; i++) {
		int max = i;
		for(int j=i+1; j<s_arr.length; j++) {
			if(s_arr[max] < s_arr[j]) max = j;
		}
		
		char tmp = s_arr[max];
		s_arr[max] = s_arr[i];
		s_arr[i] = tmp;
	}
	
	return new String(s_arr);
}

마지막은 선택정렬 방식입니다.

배열의 앞에서부터 순서대로 탐색하며 정렬하는 알고리즘입니다.

데이터를 하나씩 모두 비교하기에 데이터 양이 매우 많으면 처리 속도가 늦어진다는 단점이 있습니다.

 

✔ 테스트 케이스 처리 속도: 평균 0.04ms / 최대 1.72ms

---

역시 Stream은 깔끔하지만 처리속도가 느렸어요.

Arrays를 활용해 정렬한 경우는 평균적으로 무난한 처리속도였고

선택정렬은 평균적으로는 매우 빠르지만 앞서 설명한 선택정렬의 단점처럼 특정 케이스의 경우엔 처리속도가 많이 느려지는 모습이 보였습니다.