[프로그래머스] 이진 변환 반복하기 for JAVA

문제설명

0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

1. x의 모든 0을 제거합니다.
2. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다.

예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

제한사항

s의 길이는 1 이상 150,000 이하입니다.

s에는 '1'이 최소 하나 이상 포함되어 있습니다.

 

문제풀이

1. 첫번째 풀이

StringBuffer의 deleteCharAt 함수 사용

0인 부분을 삭제하기 위해 String s 의 특정위치 char를 삭제할 수 있는 StringBuffer의 deleteCharAt를 사용하여 구현했습니다.

for문을 반복하면서 문자열 내의 문자가 삭제되므로 반복문은 String의 끝지점부터 0으로 이동하면서 실행합니다.

문제점 :  String에서 deleteCharAt 함수를 이용하여 삭제하는데 시간이 오래 걸림

private static int[] solution(String s) {
	int[] answer = new int [2];
	int cnt = 0;	// 변환 과정에서 제거된 모든 0의 개수
	int change = 0;	//이진 변환의 횟수
	while (!s.equals("1")) {	// s가 1이 될때까지 반복
		StringBuffer tmp = new StringBuffer(s);
		for (int i = s.length()-1; i >= 0; i--) {
			if (tmp.charAt(i) == '0') {
				tmp.deleteCharAt(i);
				cnt++;
			}
		}
		change++;
        	// 10진수값을 이진수로 변환한 String 값 반환
		s = Integer.toBinaryString(tmp.length());	
	}
	answer[0] = change;
	answer[1] = cnt;
	
	return answer;
}

 

2. 두번째 풀이

replaceAll 함수 사용

0을 삭제할 때 replaceAll("0", "")을 사용하여 0에 해당하는 부분은 모두 없어지도록 구현했다.

제거된 0의 갯수를 구하기 위해 replaceAll 함수 실행 전의 s.length()와 함수 실행 후의 s.length()의 차이를 더했다. (7번째 줄)

이로써 실행시간은 줄어들고 코드 또한 간결해졌다.

private static int[] solution1(String s) {
	int[] answer = new int [2];
	while (!s.equals("1")) {
		int size = s.length();
		s = s.replaceAll("0", "");
		answer[0]++;
		answer[1] += (size-s.length());
		s = Integer.toBinaryString(s.length());
	}
	return answer;
}

GitHub - dayaeLee777/Java_Algo: 1일 1알고리즘

 

문제 바로가기

코딩테스트 연습 - 이진 변환 반복하기