오늘의 학습 키워드
- 정수 내림차순으로 배치하기
공부한 내용 본인의 언어로 정리하기
import java.util.*;
class Solution {
public long solution(long n) {
// 문자열로 변환하고 각 자릿수를 분리하여 배열로 만듦
String[] arr = String.valueOf(n).split("");
// 배열을 내림차순으로 정렬
Arrays.sort(arr, Collections.reverseOrder());
// 내림차순 정렬한 문자들을 문자열로 결합
String str = "";
for(String s : arr){
str += s;
}
/* StringBuilder를 사용해도 됌
StringBuilder sb = new StringBuilder();
for(String s : arr){
sb.append(s);
}
*/
// Long으로 변환하기
//StringBuilder일때는 sb.toString()사용
return Long.parseLong(sb);
}
}오늘의 회고
오랜만에 배열이 나와서 수월하게 풀 수 있었던 날이었다.
정수를 내림차순으로 배치한다는 것을 보고 첫날에 풀었던 문제가 생각나 비슷하게 순서를 구성했다.
1. 문자열로 변환하고 배열로 만들기
2. 배열을 내림차순으로 정렬하기
3. 내림차순 정렬한 문자들을 문자열로 다시 결합하기
4. 문자열을 다시 정수로 변환하기
하지만 첫날과는 다르게 객체를 따로 생성해서 순회하며 int로 한 자리씩 잘라서 넣지않고 이번에는 바로 문자열로 변환한 후 한글자 씩 잘라서 배열로 만들었다.
String[] arr = String.valueOf(n).split("");그리고 몇일 전에 했던 Arrays.sort()를 이용해서 내림차순 정렬을 배열에 적용을 시켰다.
Arrays.sort(arr, Collections.reverseOrder());내림차순으로 정렬한 배열 arr을 다시 문자열로 만들어 주었다. 처음에는 StringBuilder를 사용했지만 알아보던 중 JDK1.5 이후 버전에서는 String 클래스를 활용해도 성능상으로 차이가 없어졌다는 것을 보았고 간단하게 수정했다.
String str = "";
for(String s : arr){
str += s;
}마지막으로 출력해주기 위해서 다시 정수로 변환이 필요했다. 전에 사용했던 ParseInt를 응용해서 ParseLong을 사용하였다.
return Long.ParseLong(sb);AI 코드리뷰
현재 코드 리뷰:
장점
- 코드는 주어진 숫자를 내림차순으로 정렬하는 기능을 올바르게 수행합니다.
- 주석이 잘 되어 있어 각 단계의 목적을 이해하기 쉽습니다.
String.valueOf()와split("")을 사용하여 숫자를 문자 배열로 변환하는 것은 효과적입니다.Arrays.sort()와Collections.reverseOrder()를 사용하여 내림차순 정렬을 구현한 것은 좋습니다.- 문자열 연결을 위해 += 연산자를 사용하는 것은 비효율적일 수 있습니다.
단점
- 시간 복잡도:
Arrays.sort()메소드를 사용하여 정렬하므로 시간 복잡도가 O(n log n)입니다. 여기서n은 입력 숫자의 자릿수입니다. 이는 더 효율적인 방법이 가능한 경우에 비해 비교적 느립니다.
- 메모리 사용:
String[] arr를 생성하여 각 자릿수를 저장합니다. 이는 입력 숫자의 크기에 비례하는 추가 메모리를 사용합니다.
- 비효율적인 문자열 연결:
for루프 내에서+=연산자를 사용하여 문자열을 연결합니다. 이는 매 반복마다 새로운String객체를 생성하므로 비효율적입니다.
- 불필요한 변환:
숫자를 문자열로 변환한 후 다시 배열로 분리하고, 정렬 후 다시 문자열로 합친 뒤 최종적으로Long으로 변환합니다. 이 과정에서 여러 번의 불필요한 변환이 일어납니다.
- 제한된 입력 범위:
long 타입을 사용하므로 매우 큰 숫자의 경우 오버플로우가 발생할 수 있습니다.
- 코드의 복잡성:
간단한 작업을 수행하는데 비해 코드가 다소 복잡합니다. 여러 단계의 변환과 정렬 과정이 포함되어 있어 코드의 의도를 한눈에 파악하기 어려울 수 있습니다.
- 확장성 부족:
이 방식은 숫자를 내림차순으로 정렬하는 특정 문제에만 적용 가능합니다. 다른 정렬 기준이나 데이터 형식에 대해서는 쉽게 수정하기 어려울 수 있습니다.
- 성능 최적화의 여지:
주어진 문제(숫자의 자릿수를 내림차순으로 정렬)의 특성을 고려하지 않고 일반적인 정렬 알고리즘을 사용하고 있어, 성능 최적화의 여지가 많이 남아있습니다.
시간복잡도:
현재 코드의 주요 시간복잡도는 정렬 단계에서 발생합니다. Arrays.sort()는 평균적으로 O(n log n)의 시간복잡도를 가집니다. 여기서 n은 입력 숫자의 자릿수입니다.
시간복잡도 개선된 코드 제안
import java.util.*;
class Solution {
public long solution(long n) {
// 숫자를 문자열로 변환
String numStr = String.valueOf(n);
// 각 자릿수의 빈도를 저장할 배열 (0-9)
int[] count = new int[10];
// 각 자릿수의 빈도 계산
for (char c : numStr.toCharArray()) {
count[c - '0']++;
}
// 결과를 저장할 StringBuilder
StringBuilder result = new StringBuilder();
// 9부터 0까지 내림차순으로 순회하며 결과 문자열 생성
for (int i = 9; i >= 0; i--) {
while (count[i] > 0) {
result.append(i);
count[i]--;
}
}
// 결과를 long으로 변환하여 반환
return Long.parseLong(result.toString());
}
}개선된 버전의 장점:
Counting sort알고리즘을 사용하여 정렬 과정을 최적화했습니다.StringBuilder를 사용하여 문자열 연결 작업을 효율적으로 만들었습니다.- 불필요한 배열 생성과 정렬 과정을 제거했습니다.
시간복잡도:
- 개선된 코드의 시간복잡도는 O(n)입니다. 여기서
n은 입력 숫자의 자릿수입니다. - 각 자릿수를 한 번씩 순회하고, 0 부터 9 까지의 고정된 범위를 다시 순회하므로 선형 시간이 소요됩니다.
공간복잡도:
- 개선된 코드의 공간복잡도는 O(1)입니다. 크기가 10 으로 고정된 배열만 사용하기 때문입니다.
이 개선된 버전은 원래 코드보다 더 효율적이며, 특히 입력 숫자의 자릿수가 많을 때 성능 차이가 두드러질 것입니다.
내일 공부할 것 :
셀프세션에서 클럽장님이 반복문을 사용하지 않고 문자열을 결합할 방법이 있다고 말씀해 주셔서 알아보고 새로 풀어보았다.
import java.util.*;
class Solution {
public long solution(long n) {
// 문자열로 변환하고 각 자릿수를 분리하여 배열로 만듦
List<String> arr = Arrays.asList(String.valueOf(n).split(""));
// 내림차순으로 정렬
Collections.sort(arr, Collections.reverseOrder());
// 내림차순 정렬한 문자들을 문자열로 결합
String str = String.join("", arr);
return Long.parseLong(str);
}
}join을 사용하기 위해서 문자열이 아닌 List로 만들어서 진행하였다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/12933
