<프로그래머스 C++> 이진 변환 반복하기 풀이

문제

0과 1로 이루어진 문자열 s에 이진 변환을 반복 적용하는 문제이다.

 

이진 변환 규칙

1. s의 모든 0을 제거한다.

2. 제거 후 길이를 2진수의 문자열로 변환.

 

s가 "1"이 될 때까지 반복하며, 변환 횟수와 제거된 0의 총 개수를 return한다.

---

풀이 아이디어

s가 "1"이 될 때까지 반복하므로 while(s != "1") 구조를 선택했다.

 

매 반복마다 세 가지를 처리해야한다.

 

1. '1'의 개수를 세서 s.size - 1의 개수를 해서 0의 개수와 1의 개수를 한 번에 체크한다.

2. 변환 횟수와 0을 제거한 개수를 변수에 누적한다.

3. '1'의 개수를 2진수 문자열로 변환해서 s를 갱신한다.

 

2진수 변환 방식으로는 2로 나눈 나머지를 앞에 붙이는 방식으로 구현했다.

---

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string toBinary(int n)
{
    string result = "";
    while(n > 0)
    {
        result = to_string(n % 2) + result;
        n /= 2;
    }
    return result;
}

vector<int> solution(string s) {
    vector<int> answer = {0, 0};

    while(s != "1")
    {
        int one = count(s.begin(), s.end(), '1');
        int zero = s.size() - one;

        answer[0]++;
        answer[1] += zero;
        s = toBinary(one);
    }

    return answer;
}

---

코드 흐름

1. toBinary함수

string toBinary(int n)
{
    string result = "";
    while(n > 0)
    {
        result = to_string(n % 2) + result;
        n /= 2;
    }
    return result;
}

정수를 2진수 문자열로 변환하는 함수를 추가했다.

2로 나눈 나머지를 앞에 붙이는 방식으로 구현했다.

n = 6
6 % 2 = 0  →  "0"
3 % 2 = 1  →  "10"
1 % 2 = 1  →  "110"

 

2. while 반복

while(s != "1")

s가 "1"만 남을 때까지 반복한다.

 

3. 1과 0의 개수 계산

int one = count(s.begin(), s.end(), '1');
int zero = s.size() - one;

<algorithm> 헤더에 정의되어 있는 count() 함수를 이용해서 '1'의 개수를 세고, 전체 길이에서 빼면 0의 개수를 한 번에 구할 수 있다.

 

4. 누적 및 갱신

answer[0]++;        // 변환 횟수
answer[1] += zero;  // 제거된 0의 총 개수
s = toBinary(one);  // 1의 개수를 2진수 문자열로 변환

변환 횟수와 0 제거 개수를 누적하고, s를 새로운 2진수의 문자열로 갱신한다.

---

핵심 포인트

 

• while(s != "1")로 종료 조건을 간단하게 표현한다
• '1'의 개수만 세면 s.size() - 1의개수로 0의 개수도 한 번에 구할 수 있다