[프로그래머스 / 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]

• 문자열을 뒤집기 위해 reverse() 함수를 사용하므로 algorithm 헤더를 include
• 이진 변환의 횟수와 변환 과정에서 제거된 0의 개수를 저장할 정수형 벡터 answer을 2의 크기로 0으로 초기화. 문자열 중 1의 개수를 저장할 정수형 변수 len을 초기화. while loop의 조건문을 s.size() != 1로 설정하여 s의 크기가 1이 아닐동안 반복. len을 0으로 초기화 후, for loop를 통해 문자열 s의 첫번째부터 마지막 원소까지 순환하고, if문을 사용하여 0을 발견하면 0의 제거 횟수인 answer[1]을 1씩 늘림. else문을 사용하여 1을 발견하면 len을 1씩 늘림. loop 탈출 후, s를 초기화 하고 저장된 len은 0 제거후 길이 이므로 이진 변환을 해야 함. while loop()의 조건문을 len으로 설정하여 len이 자연수인 동안 반복. 문자열 s에 len을 2로 나눈 나머지를 저장하고, len은 2로 나눈 몫을 저장하는 과정을 반복하여 이진화 수행. loop 탈출 후,이진 변환이 거꾸로 저장되어 있으므로 reverse() 함수를 사용하여 문자열을 뒤집음. 이후, 이진 변환의 횟수를 의미하는 answer[0]을 1씩 늘리고, 이 과정을 반복. while loop 탈출 후, 최종적으로 저장된 answer을 return

algorithm 헤더의 reverse() 함수 사용법
1. 배열
reverse(a, a+5); => a 배열의 처음부터 다섯번째 요소까지 뒤집음
2. 문자열, 벡터
1) reverse(str.begin(), str.end()); => 문자열 str의 처음부터 끝까지 뒤집음
2) reverse(v.begin()+1, v.end()-1); => 벡터 v의 두번째부터 마지막 이전 요소까지 뒤집음

---

풀이

#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;
}