프로그래머스 - 타겟넘버 <알고리즘 비트연산 계산>

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

프로그래머스

 

프로그래머스에서 이 문제를 풀다 나는 깊이우선 탐색 방식을 사용하여 풀었지만 다른 분들의 코드를 보며 감명 받아서 이를 남기게 되었다

 

using System;

public class Solution {
     public int solution(int[] numbers, int target)
        {
            int answer = 0;

            for(int i = 0; i < Math.Pow(2,numbers.Length); i++)
            {
                int sum = 0;
                int temp = i;

                for (int j = 0; j < numbers.Length; j++)
                {
                    if(temp % 2 == 1)
                    {
                        sum -= numbers[j];
                    }
                    else
                    {
                        sum += numbers[j];
                    }
                    temp /= 2;
                }

                if(sum == target)
                {
                    answer++;
                }
            }

            return answer;
        }
}

 

전체 코드는 위에 인데 여기서 핵심은 아래 부분이다

 

for (int j = 0; j < numbers.Length; j++)
{
    if(temp % 2 == 1)
    {
        sum -= numbers[j];
    }
    else
    {
        sum += numbers[j];
    }
    temp /= 2;
}

 

이 문제 풀이의 방식의 핵심은 순서대로 + - 부호를 바꿔가며 계산을 완료한뒤 이 값이 target 값과 같은지 확인하는 것이다

여기에서 이 부호 변경을 비트 연산 방식으로 표현하였는데 첫번째 루프일때 temp = 0 이고 이는 0000 하위비트만 봤을때 이다 두번째는 temp = 1이고 이는 0001이다 위에서 temp의 첫번재 비트가 1 이면 -부호를 달아주고 1이아니면 +부호를 달아주며 temp /= 2를 통하여 다음 비트값을 확인하는 방식으로 즉 temp의 값에 따라 몇번째 numbers를 -로 할지를 결정하게 해주는 아름다운 코드였다.

 

나도 언젠가는 저런생각이 빠르게 나왔으면 좋겠다는 생각을 가지며 글을 마친다