[C++] 삼성 SDS KOITP 고장난시계

문제링크 : https://koitp.org/problem/SDS_TEST_CLOCK

[삼성 SDS 대학생 알고리즘 특강 사전 테스트 B Type 4번 문제]

FND의 7-segment를 보자마자 bit 연산으로 풀어야겠다고 생각이 든 문제이다.

0~9 까지의 모든 bit 순서를 저장한 배열을 만들고 각 숫자와 XOR 연산을 하게되면 어떤 부분이 다른지 여부가 체크된다.

이 다른 부분의 bit 갯수가 4개의 segment 모두 합쳐 2개 이하가 되는 최소 값을 구하면 된다.

4중 for문을 사용하여 코드가 매우 지저분하지만 for문이 각각 상수 횟수 만큼 실행되기 때문에 O(1)이다.

탐색 조건은 반드시 00:00 ~ 23:59 범위 내로 한정해야 한다. 최소로 나올 수 있는 값이 32:00 이런식으로 되버리면 곤란하기 때문이다.

(2번째 세그먼트의 경우 1번째 세그먼트가 2가 오게 되면 0~3까지 밖에 표현 못하기 때문에 별도의 조건을 두어야 하는 것이 마땅하나 딱히 23시를 초과한 값에 대하여 고려할 필요는 없기 때문에 생략했다.)

또한 goto를 통하여 4중 for문을 깔끔하게 한번에 빠져나갈 수 있다는 점이 정말 매력적인듯 하다. (동아리 LCH 회원님 ㄳ)

// KOITP_SDS_Btype_04
#include <bits/stdc++.h>
 
using namespace std;
 
int countBits(int n) {
    int result = 0;
    for (int i = 0; i < 7; i++) {
        if (n & 1)
            result++;
        n = n >> 1;
    }
    return result;
}
 
int main() {
    // freopen("../input.txt", "r", stdin);
    // 0 ~ 9
    int nums[10] = {0b1111110, 0b0000110, 0b1011011, 0b1001111, 0b0100111,
                0b1101101, 0b1111101, 0b1000110, 0b1111111, 0b1101111};
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        int time[4] = {0,};
        bool tmp;
        int resultHour = 0;
        int resultMin = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 7; j++) {
                time[i] = time[i] << 1;
                cin >> tmp;
                if (tmp)
                    time[i] += 1;
            }
        }
        int n1, n2, n3, n4;
        bool exitFlag = false;
        for (int a = 0; a <= 2; a++) {
            if (exitFlag) break;
            n1 = countBits(nums[a] ^ time[0]);
            if (n1 > 2)
                continue;
            for (int b = 0; b <= 9; b++) {
                if (exitFlag) break;
                n2 = countBits(nums[b] ^ time[1]);
                if (n1 + n2 > 2)
                    continue;
                for (int c = 0; c <= 5; c++) {
                    if (exitFlag) break;
                    n3 = countBits(nums[c] ^ time[2]);
                    if (n1 + n2 + n3 > 2)
                        continue;
                    for (int d = 0; d <= 9; d++) {
                        if (exitFlag) break;
                        n4 = countBits(nums[d] ^ time[3]);
                        if (n1 + n2 + n3 + n4 > 2)
                            continue;
                        else {
                            resultHour = a * 10 + b;
                            resultMin = c * 10 + d;
                            exitFlag = true;
                            goto END;
                        }
                    }
                }
            }
        }
        END:
        cout << "#" << t + 1 << " " << resultHour << " " << resultMin << "\n";
    }
    return 0;
}