[프로그래머스] - 이진 변환 반복하기(C++)

이진 변환 반복하기

 

문제 설명

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'이 최소 하나 이상 포함되어 있습니다.

 

입출력 예

s	result
"110010101001"	[3, 8]
"01110"	[3, 3]
"1111111"	[4, 1]

 

시작 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    return answer;
}

 

나의 풀이

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<int> solution(string s)
{
    vector<int> answer(2, 0);
    int len;
    
    while(s.size() != 1)
    {
        len = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] == '0') answer[1]++;
            else len++;
        }
        s = "";
        while(len)
        {
            s += to_string(len % 2);
            len /= 2;
        }
        reverse(s.begin(), s.end());
        answer[0]++;
    }
    return answer;
}

 

코드 분석

이진 변환의 횟수와 삭제된 0의 개수를 저장할 answer를 만듭니다. while문을 통해 s의 크기가 1이 아닐때까지 반복문을 돌리고 그 안에서 len을 0으로 초기화 후 for문을 돌립니다. for문에서는 if문으로 s의 요소가 0인지 체크하고 맞다면 0의 제거 횟수를 세는 answer[1]을 증가시킵니다. 그게 아니라면 len을 증가시킵니다.

 

for문 이후 s를 초기화하고 while문으로 len이 없을 때까지 돌아가도록 합니다. 안에서는 len 값을 2로 나눈 나머지 값을 string으로 변환하여 s에 추가합니다. 이후 len을 2로 나눈 결과를 저장합니다.

 

while문을 빠져나오면 reverse함수를 사용하여 s를 뒤집습니다. 이후 이진 변환의 횟수를 세는 answer[0]을 증가시킵니다. 모든 루프를 빠져나왔다면 answer값을 리턴합니다.

 

풀이 설명

이 문제가 요구하는 것은 주어지는 문자열 s에 대해서 s가 1이 될때까지 이진 변환을 수행하여 이진 변환의 수행횟수와 제거된 0의 갯수를 세는 것입니다. 이진 변환의 과정은 설명에 적힌 것처럼 0을 전부 지우고, 0을 지운 해당 문자열의 길이를 2진법으로 표현하는 것입니다. 그럼 입출력 예 1번을 통해 설명하겠습니다.

 

"110010101001"이 s로 주어지고 이진 변환을 수행합니다. 그럼 0이 전부 사라지고 "111111" 이 됩니다. 이때 사라진 0의 갯수는 6개입니다. 이후 0을 제거한 문자열의 길이 6을 2진법으로 만들면 "110"이 됩니다. 이러면 answer는 [1, 6]이 됩니다. 두번째 변환을 시도하면 "11" -> "10" 이 되고 [2, 7]이 됩니다. 마지막 세번째 변환을 수행하면 "1" -> "1" 그리고 [3, 8]이 나오게 됩니다.

 

소스코드로 과정을 보면, 가장 바깥쪽에 있는 while문은 모든 루프의 종료조건으로 s의 크기가 1이상이면 계속 돌아갑니다. 안에 for문에서는 s를 순회하여 0을 찾고 answer에 카운팅된 값을 증가시킵니다. len은 반대로 0이 아닌것을 만나면 길이를 증가시킵니다. s를 비우고 새롭게 만들어진 길이를 통해 2진법 변환을 수행합니다. 이후 변환된 문자열을 뒤집어 제대로 된 이진법 표현으로 만들어줍니다. 이후 answer에 이진 변환 횟수를 올려줍니다. 이 과정을 계속 반복하여 모든 루프를 빠져나오면 s의 길이는 1이되고 answer에는 이진 변환 횟수와 제거된 0의 개수가 저장되어 리턴됩니다.

 

<NEXT>

오늘은 월간 코드 챌린지 시즌1 문제인 "이진 변환 반복하기" 문제를 살펴봤습니다. 이 문제의 정답률은 77%입니다. 다음에는 "숫자의 표현" 문제를 살펴보도록 하겠습니다. 감사합니다.