문자열 내림차순으로 배치하기
문제
https://school.programmers.co.kr/learn/courses/30/lessons/12917
풀이
- 문자열의 문자를 배열로 나누어 넣는다.
- 해당 배열을 내림차순으로 정렬한다.
- 배열을 문자열로 다시 만든다.
import java.util.*;
class Solution {
public String solution(String s) {
String answer = "";
ArrayList<Character> str = new ArrayList<>();
for (int i=0; i<s.length(); i++) {
str.add(s.charAt(i));
}
str.sort(Collections.reverseOrder());
for (int i=0; i<str.size(); i++) {
answer += str.get(i).toString();
}
return answer;
}
}평균적으로 1ms ~ 2ms 사이의 시간이 걸린다.
테스트 1 〉 통과 (1.59ms, 84.9MB)
테스트 2 〉 통과 (1.70ms, 88.2MB)
테스트 3 〉 통과 (1.56ms, 73.4MB)
테스트 4 〉 통과 (1.55ms, 73.3MB)
테스트 5 〉 통과 (3.73ms, 73.7MB) //제일 오래 걸리는 해당 테스트로 확인하자
테스트 6 〉 통과 (2.87ms, 78.6MB)
테스트 7 〉 통과 (1.66ms, 75.4MB)
테스트 8 〉 통과 (1.77ms, 88.9MB)
테스트 9 〉 통과 (1.80ms, 75.7MB)
테스트 10 〉 통과 (2.11ms, 89.1MB)
테스트 11 〉 통과 (1.99ms, 68.9MB)
테스트 12 〉 통과 (2.26ms, 83.8MB)
테스트 13 〉 통과 (1.89ms, 76MB)
테스트 14 〉 통과 (1.38ms, 87.8MB)
테스트 15 〉 통과 (2.62ms, 77.8MB)
테스트 16 〉 통과 (1.32ms, 86.5MB)시간을 더 줄여보자
Split() vs CharAt()
class Solution {
public String solution(String s) {
String answer = "";
String [] str = s.split("");
Arrays.sort(str, Collections.reverseOrder());
for (int i=0; i<str.length; i++){
answer += str[i];
}
return answer;
}
}테스트 5 〉 통과 (4.26ms, 85.3MB)split() 함수를 사용하니 시간이 더 늘어났다.
GPT🗣️
charAt()방식은 O(N)의 시간복잡도와 최소한의 메모리 사용으로 동작합니다.
split("")방식은 O(N)의 시간복잡도에 더해, N개의 String 객체와 배열을 추가로 생성하므로 메모리와 실행시간 모두 더 소모됩니다.
라고 한다.
그러면 문자열을 리스트로 받는 건 반복문과 charAt()을 통해 해결해보자.
index vs Iterator
그 다음에 배열을 다시 문자열로 만드는 과정에서 고민이 생겼다.
class Solution {
public String solution(String s) {
String answer = "";
List<String> str = new ArrayList<>();
for (int i=0; i<s.length(); i++){
str.add(String.valueOf(s.charAt(i)));
}
str.sort(Collections.reverseOrder());
//어떤 것을 쓸 것인가?
/*
for (int i=0; i<str.size(); i++) {
answer += str.get(i);
}
for (String string : str) {
answer += string;
}
*/
return answer;
}
}
인덱스로 접근하는 방식과 Iterator를 사용하는 방식이다.
- 인덱스 방식
for (int i=0; i<str.size(); i++) {
answer += str.get(i);
}테스트 5 〉 통과 (2.99ms, 81.7MB)- Iterator 방식
for (String string : str) {
answer += string;
}테스트 5 〉 통과 (3.13ms, 88.5MB)미약하지만 Iterator 방식이 조금 더 시간이 걸린다.
아마 내부적으로 Iterator를 호출하여 사용하는 부분에서 오버헤드가 발생하는 것 같다.
GPT🗣️
성능이 아주 중요한 대용량 반복에서는 인덱스 기반for문이 더 유리합니다.
일반적이거나, 코드의 가독성이 더 중요한 경우에는for-each (Iterator)를 써도 무방합니다.
하지만 이것보다 더 효율이 좋은 String을 다루는 객체가 따로 있다.
바로 StringBuilder
StringBuilder
StringBuilder에 대한 얘기는 해당 링크 참고!
결론만 얘기하자면 String은 불변적인 문자열, StringBuilder는 가변적인 문자열로 쉽게 문자열을 변경할 수 있다.
따라서, StringBuilder를 사용하면 마지막 배열을 문자열로 바꾸는 과정에서 훨씬 빠르게 문자열을 만들 수 있다!
class Solution {
public String solution(String s) {
StringBuilder answer = new StringBuilder();
List<String> str = new ArrayList<>();
for (int i=0; i<s.length(); i++){
str.add(String.valueOf(s.charAt(i)));
}
str.sort(Collections.reverseOrder());
for (String string : str) {
answer.append(string);
}
return answer.toString();
}
}테스트 5 〉 통과 (1.60ms, 77.3MB)히익
1ms까지 나왔다. 👏👏👏👏
여기서 더 나아가
다른 분들의 풀이를 보던 중 넘사벽을 보았다.
나는 String 배열을 만들기 위해 String.valueOf()로 char을 String 객체로 생성하고 있었다.
for (int i=0; i<s.length(); i++){
str.add(String.valueOf(s.charAt(i)));
}하지만
public class Solution {
public String solution(String str){
char[] sol = str.toCharArray();
Arrays.sort(sol);
return new StringBuilder(new String(sol)).reverse().toString();
}
}이 코드는 toCharArray()를 통해 애초에 char 배열로 시작해서, StringBuilder로 마무리를 했다.
char은 기본형이므로 String보다 메모리 할당과 비교 연산이 훨씬 빠르다는 점과
StringBuilder에서 new String()으로 char 배열을 String 객체로 한 번만 생성한 점
이 부분에서 코드가 훨씬 빨라진 것이다.
속도를 줄일 수 있는 핵심은 역시 "
String객체 생성을 얼마나 줄일 수 있느냐" 인 것 같다.
그래서 나온 속도는요?
테스트 5 〉 통과 (0.80ms, 74.9MB)... 대단하다.
