Unreal 개발 본 캠프 49일차

HappyCircle·2026년 2월 6일

Unreal 개발

목록 보기

66/163

📘TIL - 코딩 테스트 : 이진 변환 반복하기

문제 핵심 요약

0과 1로 이루어진 문자열 s가 "1"이 될 때까지 다음 과정을 반복하며 [이진 변환 횟수, 제거된 0의 총합]을 구하는 문제입니다.

문자열에서 모든 0을 제거합니다.
남은 문자열의 길이 c를 2진수 문자열로 변환하여 s를 교체합니다.

🚩 알고리즘 개선 과정

1. 원본 코드 (초기 접근)

특징: 0을 만날 때마다 길이를 줄이고, to_string을 이용해 이진수 문자열을 새로 생성합니다.
분석: 직관적이지만 문자열을 매번 새로 할당하는 비용이 발생합니다.

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

using namespace std;

vector<int> solution(string s) {
    int count = 0;
    int zero_count = 0;
    
    while(s.length() != 1) {
        int temp = s.length();
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == '0') {
                temp -= 1;
                zero_count += 1;
            }
        }
        
        string binary = "";
        while (temp > 0) {
            binary += to_string(temp % 2);
            temp /= 2;
        }
        reverse(binary.begin(), binary.end());
        s = binary;
        count += 1;
    }
    return {count, zero_count};
}

2. 정석 코드 1 (불필요한 연산 줄이기)개선: ones 개수만 세어 제거된 0의 개수를 즉시 계산 (s.length() - ones).최적화: push_back을 사용하여 문자열 누적 비용을 줄였습니다.

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

using namespace std;

vector<int> solution(string s) {
    int transform = 0;
    int removedZero = 0;

    while (s != "1") {
        int ones = 0;
        for (char ch : s) {
            if (ch == '1') ones++;
            else removedZero++;
        }

        s.clear();
        while (ones > 0) {
            s.push_back(char('0' + (ones % 2)));
            ones /= 2;
        }
        reverse(s.begin(), s.end());
        transform++;
    }
    return {transform, removedZero};
}

3. 정석 코드 2 (문자열 생성 최소화)개선: 다음 루프에 필요한 정보인 문자열 길이(n)와 1의 개수(ones)만 숫자로 관리합니다.최적화: 문자열 복사 비용이 거의 없으며, 비트 연산을 활용해 속도가 가장 빠릅니다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(string s) {
    int transform = 0;
    int removedZero = 0;

    int n = (int)s.size();
    int ones = 0;
    for (char ch : s) if (ch == '1') ones++;

    while (n > 1) {
        removedZero += (n - ones);
        transform++;

        int nextN = 0;
        int nextOnes = 0;
        int x = ones;

        while (x > 0) {
            nextN++;
            if (x & 1) nextOnes++;
            x >>= 1;
        }
        n = nextN;
        ones = nextOnes;
    }
    return {transform, removedZero};
}

📊 알고리즘 전략 비교 분석

구분	원본 코드 (Initial)	정석 코드 1 (Standard)	정석 코드 2 (Optimized)
0 제거 방식	반복문을 돌며 `temp--`로 남은 길이 계산	`ones++`로 1의 개수를 직접 카운트	`n - ones` 수식을 통해 제거된 개수 즉시 산출
문자열 생성	매 루프마다 `to_string`으로 새 문자열 생성	`push_back`과 `reverse`를 활용해 기존 객체 재사용	문자열 생성을 완전히 배제하고 정수(int)로만 연산
메모리 효율	문자열 재할당으로 인해 메모리 사용량 높음	메모리 할당을 최소화하여 안정적임	최적. 스택 메모리 내 정수 연산만 수행
핵심 장점	로직이 직관적이라 구현이 빠름	가독성과 성능의 균형이 좋아 코테 정답의 정석	복사 비용을 극한으로 줄인 설계 (High Performance)
추천 상황	알고리즘 초안 작성 시	실전 코딩 테스트 제출용	대용량 데이터 처리 및 성능 최적화 어필 시