[99클럽 코테 스터디] 12일차 TIL - 문자열 내림차순으로 배치하기

Hoxy?·2024년 8월 2일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99클럽 코테 스터디

목록 보기

12/42

오늘의 학습 키워드

문자열 내림차순으로 배치하기

공부한 내용 본인의 언어로 정리하기

import java.util.*;

class Solution {
    public String solution(String s) {
        char[] charArray = s.toCharArray();
        
        // 소문자와 대문자를 분리
        ArrayList<Character> lowercase = new ArrayList<>();
        ArrayList<Character> uppercase = new ArrayList<>();
        
        for (char c : charArray) {
            if (Character.isLowerCase(c)) {
                lowercase.add(c);
            } else if (Character.isUpperCase(c)) {
                uppercase.add(c);
            }
        }
        
        // 소문자와 대문자를 각각 정렬
        Collections.sort(lowercase, Collections.reverseOrder());
        Collections.sort(uppercase, Collections.reverseOrder());
        
        // 정렬된 소문자와 대문자를 합침
        StringBuilder result = new StringBuilder();
        for (char c : lowercase) result.append(c);
        for (char c : uppercase) result.append(c);
        
        return result.toString();
    }
}

오늘의 회고

문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 반환하는 문제였다. 조건은 s는 영문 대소문자로만 구성되어 있고, 대문자는 소문자보다 작은 것으로 간주한다고 하였다

그래서 난 소문자와 대문자의 배열을 따로 만들어서 소문자 배열과 대문자 배열을 오름차순 정렬해서 소문자배열 + 대문자배열을 반환해주면 정답에 가까울 것이라 생각했다.

우선 소문자와 대문자 배열의 새 객체를 만들어주었다

ArrayList<Character> lowercase = new ArrayList<>();
ArrayList<Character> uppercase = new ArrayList<>();

forEach 반복문을 통해 Character가 소문자이면 lowercase에 대문자이면 uppercase에 넣어주었다.

 for (char c : charArray) {
	if (Character.isLowerCase(c)) {
    	lowercase.add(c);
	} else if (Character.isUpperCase(c)) {
    	uppercase.add(c);
	}
}

배열이 완성되었다면 정렬하는 순서가 필요했다.

Collections.sort(lowercase, Collections.reverseOrder());
Collections.sort(uppercase, Collections.reverseOrder());

마지막으로 정렬된 문자를 소문자 + 대문자 순으로 결합하여 반환이 필요했다.

StringBuilder result = new StringBuilder();
for (char c : lowercase) result.append(c);
for (char c : uppercase) result.append(c);
        
return result.toString();

AI 코드리뷰

현재 코드의 장점

알고리즘이 명확하고 이해하기 쉽습니다.
대소문자를 분리하여 처리하므로 요구사항을 정확히 충족합니다.
ArrayList를 사용하여 동적으로 문자를 저장하고 있어 메모리 관리가 효율적입니다.

현재 코드의 단점

여러 번의 반복문을 사용하여 시간 복잡도가 다소 높을 수 있습니다.
StringBuilder를 사용하여 문자열을 구성하는 과정이 있어 추가적인 메모리 사용이 있습니다.
문자열을 char 배열로 변환한 후 다시 ArrayList로 변환하는 과정이 있어 약간의 오버헤드가 발생합니다.

시간 복잡도

현재 코드의 시간 복잡도는 O(n log n)입니다. 여기서 n은 입력 문자열의 길이입니다.

문자 분리: O(n)
정렬: O(n log n) (Collections.sort()는 일반적으로 병합 정렬을 사용)
문자열 결합: O(n)

따라서 전체 시간 복잡도는 정렬이 가장 지배적이어서 O(n log n)입니다.

시간복잡도 개선된 코드 제안

import java.util.*;
import java.util.stream.*;

class Solution {
    public String solution(String s) {
        String lowers = s.chars()
                         .filter(Character::isLowerCase)
                         .mapToObj(ch -> String.valueOf((char) ch))
                         .sorted(Comparator.reverseOrder())
                         .collect(Collectors.joining());

        String uppers = s.chars()
                         .filter(Character::isUpperCase)
                         .mapToObj(ch -> String.valueOf((char) ch))
                         .sorted(Comparator.reverseOrder())
                         .collect(Collectors.joining());

        return lowers + uppers;
    }
}

개선된 버전의 장점: