[99클럽 코테 스터디_ DAY 12] 문자열 내림차순으로 배치

yewon·2024년 8월 3일
0

스터디

목록 보기
12/22
post-thumbnail

문자열 내림차순으로 배치

✏️오늘의 문제



💡나의 풀이


   public String solution(String s) {
        String answer = "";
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        for(int i=arr.length-1; i>=0; i--){
            answer += arr[i];
        }
        return answer;
    }

장점

  1. 간단하고 직관적인 구현: 코드가 간단하며, 문제의 요구사항을 명확히 이해할 수 있습니다.
  2. 정렬을 이용한 해결: Arrays.sort()를 사용하여 내림차순 정렬을 수행하므로, 자바의 내장 함수를 효율적으로 활용하고 있습니다.

단점

  1. 문자열 연결 연산의 비효율성: 문자열 연결 연산 answer += arr[i];은 반복할 때마다 새로운 문자열을 생성하므로, 시간 복잡도가 O(n^2)에 가깝게 될 수 있습니다. 따라서 문자열 연결 대신 StringBuilder를 사용하는 것이 더 효율적입니다.
  2. 불필요한 문자열 정렬: 입력 문자열 s의 길이가 n일 때, 정렬 연산이 O(n log n)의 시간 복잡도를 가집니다. 문제에서 요구하는 것은 단순히 문자들을 내림차순으로 정렬하는 것이므로, 정렬 없이도 해결할 수 있는 방법이 있습니다.



💡더 효율적인 코드


정렬을 사용하지 않고도 내림차순으로 문자열을 구성할 수 있습니다. 아래는 StringBuilder를 사용하여 문자열을 효율적으로 구성하는 방법입니다

public String solution(String s) {
    int[] count = new int[256];
    for (char c : s.toCharArray()) {
        count[c]++;
    }
    
    StringBuilder sb = new StringBuilder();
    for (int i = 255; i >= 0; i--) {
        while (count[i] > 0) {
            sb.append((char)i);
            count[i]--;
        }
    }
    
    return sb.toString();
}

코드 설명

  1. 입력 문자열 처리

    • 함수는 문자열 s를 입력으로 받습니다. 문자열은 char 배열로 변환하여 처리됩니다.
  2. 문자 출현 횟수 카운트

    • count 배열을 사용하여 ASCII 문자셋을 기준으로 각 문자의 출현 횟수를 기록합니다. 예를 들어, count[97]은 'a'의 출현 횟수를 의미합니다.
  3. 문자열 구성을 위한 StringBuilder 사용

    • StringBuilder 객체 sb를 생성하여 내림차순으로 정렬된 문자열을 구성합니다. StringBuilder는 문자열을 효율적으로 추가하고 관리할 수 있는 클래스입니다.
  4. 내림차순 문자열 구성

    • count 배열을 역순으로 순회하면서 각 문자의 출현 횟수에 따라 문자를 sb에 추가합니다. 이 때, 출현 횟수가 0보다 클 경우에만 추가합니다. 이는 해당 문자가 문자열에 포함될 때마다 카운트를 감소시키는 방식입니다.
  5. 결과 반환:

    • sb.toString()을 호출하여 StringBuilder에 구성된 문자열을 최종적으로 반환합니다.

장점

  • 효율성: 정렬을 사용하지 않고 선형 시간복잡도 O(n)으로 문제를 해결합니다.
  • 간결함: 정렬보다 더 간단하게 문자열을 내림차순으로 정렬할 수 있습니다.
  • 메모리 사용: StringBuilder를 사용하여 문자열을 구성함으로써 메모리 사용을 최적화할 수 있습니다.

사용 사례 및 추가 설명

이 코드는 문자열을 정렬하는 과정에서 정렬 알고리즘이 아닌 문자 출현 횟수를 기반으로 문자열을 구성하는 방법을 보여줍니다. 이는 일반적인 문자열 문제에서 유용하게 적용될 수 있으며, 정렬을 사용하지 않아도 효율적으로 해결할 수 있는 경우를 보여줍니다.

이와 같은 설명을 블로그 포스팅에 추가하면, 코드를 이해하기 쉽게 도와주며, 이 코드를 사용하여 문제를 해결할 때의 장점과 성능을 설명할 수 있습니다.



0개의 댓글