[ 프로그래머스 [ 월간코드챌린지 ] 이진 변환 반복하기 ] (C++)

프로그래머스의 이진변환 반복하기(월간코드챌린지) 문제이다.

[ 문제풀이 ]

주어진 문자열을 조건에 맞게 변환했을 대, 변환 횟수와 제거된 0의 갯수를 모두 구해야 하는 문제이다.

각 과정별로 풀이법을 알아보고, 정답을 도출하는 과정까지 진행해보자.

#1. 현재 문자열에서 '0' 제거하기

먼저, 현재 문자열에서 0을 제거하는 과정을 진행해 주어야 한다.

그럼 현재 문자열에서 0을 제거했다고 가정해보자. 그 이후에 우리가 알아야 될 값은 무엇일까 ???

바로, 남은 '1'로만 이루어진 문자열의 길이를 알아야 한다. 왜냐하면 이 문자열의 길이를 통해서 그 다음 문자열을

만들어야 하기 때문이다.

따라서 본인은 0을 제거함과 동시에 남은 문자열의 길이를 return 하는 부분을 다음과 같이 구현하였다.

int DeleteZero(string S, vector<int> &answer)
{
    int Cnt = 0;
    for (int i = 0; i < S.length(); i++)
    {
        if (S[i] == '0')
        {
            Cnt++;
            answer[1]++;
        }
    }
    return S.length() - Cnt;
}

매개변수 'S'는 "현재 문자열"을 의미하는 문자열이다.

문자열을 탐색하면서 '0'의 갯수를 Count하고 최종적으로 return하는 것은 원래의 문자열의 길이에서 지운 0의 갯수만큼을 return 하게 된다. 그렇게 되면, 남은 '1'로만 이루어진 문자열의 길이를 알 수 있기 때문이다.

#2. 새로운 문자열 만들기

#1의 과정에서 우리는 '1'로만 이루어진 문자열의 길이를 파악했다.

이 길이가 N이라면, 우리는 N이라는 값을 2진수로 바꿔야 한다.

2진수로 만드는 과정은 간단하다. 주어진 숫자가 0이 아닐 때 까지 2로 나눈 나머지를 계속해서 붙여주면 된다.

즉, 코드로 나타내면 다음과 같다.

string Make_Binary_Num(int N)
{
    string S = "";
    while (N > 0)
    {
        S += ((N % 2) + '0');
        N /= 2;
    }
    S = Reverse(S);
    return S;
}

N이라는 값을 2진수로 만들고, 이 2진수를 string으로 return 하는 함수이다.

그럼 하나의 예로 N = 4를 생각해보자.

위의 코드에서 line4 ~ 8)에 있는 반복문을 N = 4로 진행해보면 'S'에는 "001" 이라는 문자열이 저장될 것이다.

실제로는 '4'를 2진수로 만들게 되면 "100"이 된다. 즉, 문자열이 뒤집힌 상태로 저장된다는 것을 알 수 있다.

따라서, line9)에서 진행했듯이, 문자열을 다시 뒤집어 주는 과정을 진행해 주어야 한다.

최종적으로는 뒤집은 문자열을 return 하게 된다.

#3. 종료 조건

#1과 #2의 과정을 계속해서 반복할 것이다. 그럼 언제까지 반복하게 될까 ??

문제에서도 나와있듯이, "현재 문자열이 "1"이 될 떄 까지" 반복해 주면 된다.

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
int DeleteZero(string S, vector<int> &answer)
{
    int Cnt = 0;
    for (int i = 0; i < S.length(); i++)
    {
        if (S[i] == '0')
        {
            Cnt++;
            answer[1]++;
        }
    }
    return S.length() - Cnt;
}
 
string Reverse(string S)
{
    string Temp = "";
    for (int i = S.length() - 1; i >= 0; i--) Temp += S[i];
    return Temp;
}
 
string Make_Binary_Num(int N)
{
    string S = "";
    while (N > 0)
    {
        S += ((N % 2) + '0');
        N /= 2;
    }
    S = Reverse(S);
    return S;
}
 
vector<int> solution(string s) 
{
    vector<int> answer(2, 0);
    string Str = s;
    while (Str != "1")
    {
        int Len = DeleteZero(Str, answer);
        Str = Make_Binary_Num(Len);
        answer[0]++;
    }
    return answer;
}