https://school.programmers.co.kr/learn/courses/30/lessons/70129
문제 자체는 간단했지만,
문자열을 어떻게 다루느냐에 따라서 실행 시간 초과가 발생하는 구조라
문제 접근 방식을 정리해두고자 한다.
이번 문제는 크게 다음 두 가지 포인트가 핵심이었다.
- 문자열 변경 (0 제거, 길이 계산, 2진 변환)
- 문자열 처리 최적화 (replace 사용 시 시간 초과 발생)
문제 접근
ㅅ
1. 문자열에서 0을 제거한다
2. 제거한 0의 개수를 누적한다
3. 0을 제거한 후의 문자열 길이를 구한다
4. 그 길이를 2진수로 변환해서 다시 s로 저장한다
5. 변환 횟수를 +1 증가한다
6. s가 "1"이 될 때까지 반복한다
7. 마지막에 [변환 횟수, 제거된 0의 개수]를 반환한다
1. replace("0", "") 사용 시의 문제점
처음에는 replace("0", "")로 문자를 직접 제거하는 방식으로 접근했다.
s = s.replace("0", "");실행 시간 초과가 발생했다.
replace가 느린 이유
replace는 내부적으로 다음 작업을 수행한다.
- 문자열 전체를 순회한다
- 새로운 문자열 객체를 생성한다
- 기존 문자열은 GC(Garbage Collector) 대상이 된다
- 반복될수록 메모리 할당 비용 + GC 부담이 증가한다
즉, 문자열의 길이가 커질수록
매번 새 문자열을 생성하는 비용 때문에 속도가 느려진다.
2. 문자열을 직접 변경하지 않는 방향으로 최적화
문제를 다시 보면,
반드시 문자열에서 0을 “제거할 필요”가 없다는 점을 떠올리게 된다.
실제로 필요한 정보는 다음 두 가지 뿐이다.
- 현재 문자열에서 1의 개수
- 제거한 0의 개수 = 전체 길이 - 1의 개수
즉, 문자열을 매번 새로 만들 필요 없이
문자 배열을 순회하며 1의 개수만 세면 된다.
최적화된 방식
int oneCount = 0;
for (char c : s.toCharArray()) {
if (c == '1') oneCount++;
}최종 코드
class Solution {
public int[] solution(String s) {
int[] answer = new int[2];
int changeCount = 0;
int removeCount = 0;
while (!s.equals("1")) {
int oldLength = s.length();
int oneCount = 0;
// 문자열에서 1의 개수만 세기
for (char c : s.toCharArray()) {
if (c == '1') oneCount++;
}
// 기존 길이 - 1의 개수 = 제거된 0의 수
removeCount += oldLength - oneCount;
// 1의 개수를 2진 문자열로 변환
s = Integer.toBinaryString(oneCount);
changeCount++;
}
answer[0] = changeCount;
answer[1] = removeCount;
return answer;
}
}