[C++] [2025 프로그래머스 코드챌린지 1차 예선] 2번 / 비밀 코드 해독

 

 

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

프로그래머스

 

문제 3줄 요약

 

1. 비밀 코드는 1 ~ n까지의 서로 다른 정수 5개 (오름차순)이다.

2. 이 비밀 코드를 맞추기 위해 m 번의 시도를 하며, 몇 개 맞췄는지 알려준다.

3. 시도한 결과를 보고 비밀 코드로 가능한 정수 조합의 개수를 출력하자.

 

---

 

 

 

제한 사항을 보니

조합의 개수가 최대 30C5 (약 14만개)이다.

 

따라서 브루트포스 알고리즘을 이용해도

풀 수 있을 것이라 생각했고

 

그 결과..

무식하게 5중 포문을 작성했다.

 

하지만 값을

비교하는 과정에서 시간 초과가 나게 되었는데

단순히 값을 비교하는 것이 아닌 비트마스크를 통해 값을 비교해야

시간 초과를 피할 수 있는 문제였다.

---

 

비트마스킹을 이 문제에서 처음 접하게 되었는데

사실 그렇게 어려운 개념은 아니였다.

 

비트 연산자를 기반으로

빠르게 교집하는 부분을 찾는 알고리즘이다.

 

 

해당 문제에서는 각 자리의 암호를

Left Shift를 통해 체크를 해주어 전체 암호를 설정해 줄 것이다.

 

// (00011111) 
password = (1 << 4) | (1 << 3) | (1 << 2) | (1 << 1) | (1 << 0);

 

예를 들어 1, 2, 3, 4, 5가 암호였다면,

위의 코드처럼 작성하여

각 자리를 1로 체크하는 것이다.

 

int는 8바이트(=32비트)이므로 2^32까지 표현이 가능하고

가장 앞의 비트는 부호 비트이기 때문에

최대 31자리까지 0과 1로 체크할 수 있게 된다.

 

문제에서 n은 최대 30까지이니 int형이면 범위에 딱 맞게 되는 것이다.

 

---

 

그럼 우리가 설정한 암호와와

기존 비밀 코드는 어떻게 비교를 할 수 있을까?

 

 

비트 연산자의 '&'를 사용하면

두 비트가 1인 경우에는 1로

그 외에는 0으로 설정함으로서

'즉, 서로가 각 자리에 체크를 해둔 경우 → 암호가 같다.' 를 의미하게 된다.

 

따라서

'1의 개수'를 우리가 제공 받은 '포함된 비밀 코드 개수'와 비교하여

내가 설정한 암호가 조합의 가능성이 있는지 없는지를 판단할 것이다.

 

---

 

먼저

5중 포문을 이용하여

nC5 개의 경우의 수를 모두 만들어보자.

 

    int pwd = 0;
    
    for(int i=1; i<=n-4; i++)
    {
        for(int j=i+1; j<=n-3; j++)
        {
            for(int k=j+1; k<=n-2; k++)
            {
                for(int l=k+1; l<=n-1; l++)
                {
                    for(int m=l+1; m<=n; m++)
                    {
                        pwd = (1 << (i-1)) | (1 << (j-1)) | (1 << (k-1)) | (1 << (l-1)) | (1 << (m-1));
                        check(pwd, q, ans);
                    }
                }
            }
        }
    }

 

위에서 살펴보았던

비트 연산자를 '&' 와 '|' 를 이용하여 5자리의 수를 int형 pwd에 체크한다.

 

int answer;

void check(int pwd, vector<vector<int>> q, vector<int> ans){
    for(int i=0; i<q.size(); i++)
    {
        int compare = 0, cnt = 0;
        for(int bit : q[i]) compare += (1 << bit-1);
        cnt = __builtin_popcount(pwd & compare);
        if(cnt != ans[i]) return;
    }

    answer++;
}

 

check 함수에서는 주어진 q와 ans를 이용한다.

 

우리가 시도한 m번의 케이스를 하나씩 꺼내어

5개의 수를 pwd와 동일한 방식으로 compare에 체크를 한다.

 

두 암호를 '&' 연산을 통해 비교하는데,

여기서

__builtin_popcount라는 함수가 보인다.

 

이는

01001101 과 같이 이진수로 표현된 수에서 1의 개수를 세어주는 함수이다!

 

되게 유용한 기능인 것 같은데 이름이 좀 어렵,,,

내장 함수인데.. 튀어나온(=1) 곳을 세주는 함수? 라고 익혀야겠다.

내장함수인만큼 따로 헤더파일 호출은 필요가 없다.

 

여튼

1의 개수를 카운트하여 ans에서 해당 케이스에 대한 포함된 암호의 개수를 비교하고

만일 같다면, 다음 케이스도 비교해본다.

 

이렇게 모든 케이스에서 통과를 한다면

그 암호는 비밀 코드 후보 중 하나이기 때문에 answer를 +1 증가시킨다.

 

---

 

전체 코드는 아래와 같다.

 

#include <string>
#include <vector>

using namespace std;

int answer;

void check(int pwd, vector<vector<int>> q, vector<int> ans){
    for(int i=0; i<q.size(); i++)
    {
        int compare = 0, cnt = 0;
        for(int bit : q[i]) compare += (1 << bit-1);
        cnt = __builtin_popcount(pwd & compare);
        if(cnt != ans[i]) return;
    }

    answer++;
}

int solution(int n, vector<vector<int>> q, vector<int> ans) {
    int pwd = 0;
    
    for(int i=1; i<=n-4; i++)
    {
        for(int j=i+1; j<=n-3; j++)
        {
            for(int k=j+1; k<=n-2; k++)
            {
                for(int l=k+1; l<=n-1; l++)
                {
                    for(int m=l+1; m<=n; m++)
                    {
                        pwd = (1 << (i-1)) | (1 << (j-1)) | (1 << (k-1)) | (1 << (l-1)) | (1 << (m-1));
                        check(pwd, q, ans);
                    }
                }
            }
        }
    }

    return answer;
}

 

비트마스킹을 문제로 푼게 처음이었기에

당황스러웠지만, 개념을 알고나니 메모리 최적화에 매우 유용하다고 느꼈다.

 

끝!