[프로그래머스 Lv.0] 이진수 더하기 C++

문제

https://school.programmers.co.kr/learn/courses/30/lessons/120885

프로그래머스

계획 세우기

두 문자의 뒷자리(bin1.length()-1)부터 비교하여, 각 자리수+올림수를 한다.

1.  더한 수가 3인 경우(두 문자열의 해당자리가 1이면서 올림수가 1인 경우) 벡터에 1을 넣고, 올림수를 1로 
2.  더한 수가 2인 경우 answer에 0을 넣고, 올림수를 1로
3.  더한 수가 1인 경우 answer에 1을 넣고, 올림수를 0으로
4. 더한 수가 0인 경우 answer에 0을 넣고 올림수를 0으로 만든다.

모든 작업이 끝났을 때(반복이 끝나고), 올림수가 1이면 answer에 1을 넣는다.

 

첫 번째 풀이(실패)

#include <string>
using namespace std;

string solution(string bin1, string bin2) {
    string answer = "";
    int carry = 0;
    for(int i=bin1.length()-1; i>=0; i--){
        int tmp = (bin1[i]-'0') + (bin2[i]-'0') + carry;
        switch (tmp){
            case 0:
                answer = "0" + answer;
                carry=0;
                break;
            case 1:
                answer = "1" + answer;
                carry=0;
                break;
            case 2:
                answer = "0" + answer;
                carry=1;
                break;
            case 3:
                answer = "1" + answer;
                carry=1;
                break;
            default:
                break;
        }
    }
    if(carry==1) answer = "1" + answer;
    
    return answer;
}

제한 사항의 1 ≤ bin1, bin2의 길이 ≤ 10 를 보고, bin1과 bin2의 길이가 같을 것이라고 생각했다. 길이가 같지 않을 경우 string 앞에 0을 추가해서 같게 만들어 주면 잘 작동할 것 같음.

 

두 번째 풀이(성공)

#include <string>
using namespace std;

string solution(string bin1, string bin2) {
    string answer = "";
    // 두 문자열의 길이가 다른 경우 짧은 쪽 앞에 0을 넣어 길이를 맞춰준다.
    if (bin1.length()!=bin2.length()){
        int len_1 = bin1.length();
        int len_2 = bin2.length();
        if(len_1>len_2){
            for (int i=0;i<len_1-len_2;i++){
                bin2 = "0" + bin2;
            }
        }
        else{
            for (int i=0;i<len_2-len_1;i++){
                bin1 = "0" + bin1;
            }
        }
        
    }
    
    // 계산하는 부분
    int carry = 0;
    for(int i=bin1.length()-1; i>=0; i--){
        int tmp = (bin1[i]-'0') + (bin2[i]-'0') + carry;
        switch (tmp){
            case 0:
                answer = "0" + answer;
                carry=0;
                break;
            case 1:
                answer = "1" + answer;
                carry=0;
                break;
            case 2:
                answer = "0" + answer;
                carry=1;
                break;
            case 3:
                answer = "1" + answer;
                carry=1;
                break;
            default:
                break;
        }
    }
    if(carry==1) answer = "1" + answer;
    
    return answer;
}

길이가 다를 경우 앞에 0을 추가하도록 제일 간단한 방법을 사용해서 만들었는데, 뭔가 많이 부족한 것처럼 느껴진다...ㅎㅎ...

 

 

다른 사람 풀이

#include <bits/stdc++.h>
using namespace std;

string solution(string bin1, string bin2) {
    int a = 0, b = 0;
    for (auto ch : bin1) a = a << 1 | ch - 48;
    for (auto ch : bin2) b = b << 1 | ch - 48;

    string ret;
    for (int n = a + b; n; n >>= 1) ret = char(n % 2 + 48) + ret;

    return ret.empty() ? "0" : ret;
}

 

가장 좋아요를 많이 받았고, 간결해보여서 해석하면 도움이 될 것 같았다. 비트 연산은 아직 어렵다고 생각하는 것 중 하나라서 좋을 것 같다. 코드가 간결한 만큼 아는 부분도 자세하게 적어보려고 한다.

 

for (auto ch : bin1)은 bin1의 문자들(bin1[0], bin1[1], ...)을 순회하겠다는 의미이다. 쉽게 말해, for(int i =0 ; i<bin1.length();i++)와 동일한 의미이며, ch는 bin1[i]를 의미한다. int a = 0으로 시작하고, a << 1 과 ch-48을 | 연산한 결과를 저장한다.

• '<<' 는 지정한 수만큼 비트들을 전부 왼쪽으로 이동시킨다는 의미이다(left shift 연산).
• '|' 는 대응되는 비트 중에서 하나라도 1이면 1을 반환하는 비트 OR 연산이다. 
• ch -48은 ch -'0'과 같은 의미로 char 타입의 숫자와 대응되는 숫자로 인식되도록 만들기 위한 조치! '0'의 아스키코드가 48이기 때문에 ch가 '0'일 경우 48-48 =0이므로 숫자 0처럼 다룰 수 있는 것.

쉽게 이해 할 수 있도록 해당 반복문이 어떻게 돌아가는지 그림으로 정리했다. 아래 그림을 참고할 것!

음... 근데 bin1과 같은 값이 나왔다. 물론 int a에 저장되어 있는 값은 10진수 9이긴 하지만 말이다... string에 저장된 비트를 int로 변환해주기 위해 해당 작업을 한 건가?

 

아무튼 이해했다면 바로 아랫줄의 for (auto ch : bin2) b = b << 1 | ch - 48; 또한 이해했을 것이다. b도 1111, 즉 10진수로 15가 저장되었을 것이다.

 

다음 줄이 조금 어려운데,

for (int n = a + b; n; n >>= 1) ret = char(n % 2 + 48) + ret;

우선, for문의 조건을 먼저 살펴본다! for문은 for (초기식; 조건식; 증감식) 으로 이루어져 있다. 조건식이 참일 때 반복한다.  조건식에 그냥 n만 들어가 있으므로 n이 0(거짓)이 아니면 반복한다는 의미이다. n>>=1은 처음 딱 봤을 때는 저게 뭐야???? 라고 생각했지만, n+=1을 떠올리고 다시 보자! n+=1이 n= n+1인 것처럼,  n= n>>1과 같은 의미이다.

쉽게 정리하면 "n=a+b부터 시작해서 n이 0이 아닐 동안 반복한다. 코드를 실행 후 n = n >> 1 연산을 해준다." 가 된다.

 

어려울 땐 그냥 대입을 해보자. a=9, b=15, 따라서 n=24가 된다. 24를 2진수로 표현하면 11000이다. 여기서 이 코드를 짠 사람의 생각을 읽을 수 있었다. 이 코드는 string에 저장된 2진수를 int로 바꿔서 더한 후(10진수로 저장됨), 다시 2진수로 바꾸어 string에 저장하는 코드였던 것(변환 → 덧셈 → 변환하는 코드).

for 문 순서도

이제 for문이 참일 동안 반복할 실행문을 살펴보자.

ret = char(n % 2 + 48) + ret;

char(n%2+48)을 원래의 문자열 앞에 삽입해준다. 그림으로 표현할까 하다가 생각보다 간단할 것 같아 글로 적겠다.

 

- 반복1: n=24(11000)

n%2+48 == 24%2+48 == 0+48 =48 → char(48)== '0'

증감식 n>>=1, n=12(1100)

 

- 반복2: n=12(1100)

n%2+48 == 12%2+48 == 0+48 =48 → char(48)== '0'

증감식 n>>=1, n=6(110)

 

- 반복3: n=6(110)

n%2+48 == 6%2+48 == 0+48 =48 → char(48)== '0'

증감식 n>>=1, n=3(11)

 

- 반복4: n=3(11)

n%2+48 == 3%2+48 == 1+48 =48 → char(49)== '1'

증감식 n>>=1, n=1(1)

 

- 반복5: n=1(1)

n%2+48 == 1%2+48 == 1+48 =48 → char(49)== '1'

증감식 n>>=1, n=0(0)

 

n=0이 되었으므로 반복 종료, ret에는 "11000"이 저장되어 정답이 된다!

 

 

참고 사이트

다른 사람 풀이 설명을 위해 참고한 사이트들입니다.

https://www.tcpschool.com/c/c_operator_bitwise

코딩교육 티씨피스쿨

https://www.dotnetkorea.com/docs/c-language/15-for/for-statement/

15 반복문(for 문)을 사용한 구간 반복