[알고리즘] 이상한 문자 만들기 - 향상된 for문의 함정과 String 성능 이슈

문제 요구사항

문자열 s는 한 개 이상의 단어로 구성되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 리턴하는 함수, solution을 완성하세요.

제한 사항

• 문자열 전체의 짝/홀수 인덱스가 아니라, 단어(공백을 기준)별로 짝/홀수 인덱스를 판단해야합니다.
• 첫 번째 글자는 0번째 인덱스로 보아 짝수번째 알파벳으로 처리해야 합니다.

 

풀이(결과: 실패)

import java.util.*;

class Solution {
    public String solution(String s) {
        String answer = "";
        // 문자열을 공백을 기준으로 단어들로 분리
        String[] splitWords = s.split("\\s");
        // 단어들을 순회하면서
        for(int j = 0;j < splitWords.length;j++){
            // 인덱스 값에 접근할 수 있도록 char 배열로 변경
            char[] chars = splitWords[j].toCharArray();
            // 각 인덱스를 순회하면서
            for(int i = 0;i<chars.length;i++){
                // 짝수 인덱스를 대문자로 교체
                if(i%2 == 0) chars[i] = Character.toUpperCase(chars[i]);
            }
            // 기존 문자열을 대문자를 적용한 char 배열로 교체
            splitWords[j] = new String(chars);
        }
        // 배열을 공백으로 구분된 문자열로 리턴
        answer = String.join(" ", splitWords);
        return answer;
    }
}

/*
향상된 for문에서 순회자 변수는 배열의 복사본이다.
반면, index 기반 for문은 각 배열 요소의 주소값을 가리킨다.

*/

실패 요인

원본 문자열 내 단어들이 한 개 이상의 공백으로 구분되어 있는데,

다시 반환할 때는 일괄적으로 한 개의 공백으로만 구분된 문자열을 리턴했다.

 

단어 대소문자 처리에 집중하여, 원본 문자열 내 공백의 크기가 다를 수 있다는 점을 감안하지 않았다.

모범답안

import java.util.*;

class Solution {
    public String solution(String s) {
        StringBuilder answer = new StringBuilder();
        // 공백이 아닌 문자 발견 시 사용할 인덱스
        int index = 0;
        for(int i = 0; i < s.length(); i++){
            // 읽기 전용인 경우, String의 각 문자를 charAt(i)로 접근할 수 있다.
            char c = s.charAt(i);
            // c의 공백/문자 유무에 따라 처리 다르게
            if(c == ' '){
                answer.append(' ');
                // 이전 단어의 index가 끝났으므로 0으로 초기화
                index = 0;
            }
            // 문자인 경우 index 값에 따라 대/소문자 처리
            else{
                if(index % 2 == 0){
                    answer.append(Character.toUpperCase(c));
                } else {
                    // (주의) 조건에서 원본 단어가 전부 소문자라고 하지 않음
                    answer.append(Character.toLowerCase(c));
                }
                // 대/소문자 처리 후 단어 내 다음 문자로 넘어감
                index++;
            }
        }
        return answer.toString();
    }
}

 

다른 답안 분석

class Solution {
  public String solution(String s) {

        String answer = "";
        int cnt = 0;
        String[] array = s.split("");

        for(String ss : array) {
            cnt = ss.contains(" ") ? 0 : cnt + 1;
            answer += cnt%2 == 0 ? ss.toLowerCase() : ss.toUpperCase(); 
        }
      return answer;
  }
}

 

평가

1. 접근 방식

핵심 아이디어:

문자열을 한 글자씩 분리(split(""))카운터 cnt로 각 단어 내 인덱스 추적공백을 만나면 카운터를 0으로 리셋카운터의 홀짝에 따라 대소문자 반환

 

cnt = 1 -> 대문자(0번째 인덱스)cnt = 2 -> 소문자(1번째 인덱스)

 

2. 문제

심각한 성능 문제

 answer += cnt%2 == 0 ? ss.toLowerCase() : ss.toUpperCase();

 

String 연결 연산자(+=)의 문제점:

- String은 불변 객체이므로 += 적용할 때마다 String 객체가 생성됨

- n개의 문자를 처리할 때 길이가 n인 문자열을 생성하므로 시간 복잡도가 O(n^2)

 

총평

접근 방식	⭐⭐⭐⭐⭐	매우 영리하고 직관적
효율성	⭐⭐	O(n²) 성능, 작은 입력엔 괜찮지만 큰 입력엔 문제
가독성	⭐⭐⭐⭐	간결하지만 성능 이슈가 숨겨져 있음
실용성	⭐⭐⭐	코딩테스트에선 통과할 수 있지만 실무에선 비추천

 

인사이트

향상된 for문에서 순회자 변수는 배열의 복사본이다.
반면, index 기반 for문은 각 배열 요소의 주소값을 가리킨다.
String은 불변 객체이므로, += 연산자는 매번 새로운 문자열을 생성한다.

Github 링크

https://github.com/ginsengcandy/Coding-Test-Practice/commit/f1bdba4e98b62425a88732eaec652a74f13c05a5

[level 1] Title: 이상한 문자 만들기, Time: 0.10 ms, Memory: 85.3 MB -BaekjoonHub · ginsengcandy/Coding-Test-Practice@f1

 

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/12930

프로그래머스