[프로그래머스] 이진 변환 반복하기(Java, 문자열, 구현)

문제 링크 

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

프로그래머스

 

문제 풀이

문자열 + 구현 문제로 주어진 요구사항 그대로 구현하면 되었다.

0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다
① x의 모든 0을 제거 합니다
② x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다
문자열 s가 주어질 때 "1"이 될 때까지 변환 횟수와 제거된 0의 개수를 반환하시오

 

1. replaceAll()과 StringBuilder 성능 차이

이진수로 표현되는 문자열 s 에서 "0"을 제거할 때 아래 두 가지 방식을 시도했다

// 방법1.
private String erase(String s) {
    StringBuilder result = new StringBuilder();
    for(char c : s.toCharArray()) {
        if(c == '1') result.append(c);
    }

    return result.toString();
}

// 방법2.
s = s.replaceAll("0", "");

 

테스트는 둘 다 통과했으나, 두번째 방법 replaceAll()을 적용했을 때 속도 차이가 보였다.

(왼쪽: 방법1 StringBuilder() 사용, 오른쪽: 방법2 replaceAll() 사용)

 

왜 속도 차이가 나는지 replaceAll() 메서드를 살펴보았다

 

우선 메서드 체인 통해서 Pattern과 Matcher 객체를 매 번 신규 생성하면서 비용 발생하는 것으로 보였다. 

 

Matcher 생성하기 전 compiled 플래그에 synchorized 키워드가 눈에 보여서 좀 더 살펴보았다.

 

확인해보니 Pattern 생성자 초기화시 주입한 regex(정규 표현식)을 문자열 형태로 저장하는 것만으로 사용할 수 없고, 내부적으로 정규식 패턴을 분석하여 실행 가능한 형태(컴파일된 상태)로 변환해야 했다. 변환이 완료되면 compiled = true로 설정되며, 이후 Matcher를 생성할 수 있게 된다.

 

또한, synchronized 키워드가 적용된 것을 보아하니, 지연(Lazy) 컴파일 전략을 사용해 정규식이 실제로 필요할 때만 컴파일되도록 하여 초기 로딩 비용을 줄인 것으로 보였다.

 

예전부터 "Pattern 객체는 생성 비용이 크니, 재사용해야 성능이 향상된다." 라는 말을 들었는데, 오늘에서야 그 이유를 이해할 수 있었다.

 

2. 이진수 변환

decimal to binary (10진수 -> 2진수)

String binary = Integer.toBinaryString(10); // "1010"

String binary = Long.toBinaryString(10); // "1010";

- 참고. 10진수를 2진수로 변환 로직 구현 (geeksforgeeks)

- 참고. [Java] toBinaryString(), toHexString(), toOctalString(), parseInt() 알아보기

 

binary to decimal (2진수 -> 10진수)

int decimal=Integer.parseInt("1010", 2);  // 10

BigInteger decimal = new BigInteger("1010", 2);  // 10

- 두번째 인자가 redix로 i진법 표기

 

제출 코드

import java.util.*;

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[2]; // 0: 이진 변환 횟수, 1: 변환 과정    
        while(!s.equals("1")) {
            int len = s.length();
            
            answer[0] += 1;
            answer[1] += len;
            
            s = erase(s);
            answer[1] -= s.length();
            
            s = Integer.toBinaryString(s.length());
        }
        
        return answer;
    }
    
    private String erase(String s) {
        StringBuilder result = new StringBuilder();
        for(char c : s.toCharArray()) {
            if(c == '1') result.append(c);
        }
        
        return result.toString();
    }
}