하드 코딩을 이용해서 7 세그먼트 구현 응용 문제를 풀어봅시다.

 코딩 테스트에서 7 세그먼트는 꽤 자주 등장하는 주제 중 하나입니다. 백준 22251번 빌런 호석 문제도 이런 문제인데요. 처음에 볼 때 이 문제에서 말려서, 안타깝게도 매우 많은 시간을 소모하게 되었습니다. 그래도 호석배 1회보다는 나았지만요. 그 코테는 애초에, 앞에 3개 푸는 데 2시간 걸렸다는 게 함정. 구현을 빡세게 내기 위해서, 자주 보이는 패턴이긴 합니다. 당황할 법한 문제입니다만, 예전에 제가 쓴 글이 하나 있었습니다.

 

[관련글]

코딩테스트에서 답을 미리 하드코딩 해 두는 방법도 쓸만할까요?

 

 이 글에서는 주사위 윷놀이 문제에 대해서 다루고 있습니다. 7 세그먼트를 응용한 이 문제 역시, 하드 코딩을 잘 해두면 매우 간단하게 구현할 수 있습니다.

 

---

 그러면 어떻게 하면 될까요? 이 문제에서는 해당 세그먼트가 켜졌는지 꺼졌는지만 관리하면 됩니다. 그러면 각 세그먼트 별로 상태를 관리할 건데요. 꺼졌거나 켜졌거나. 그러면 생각나야 하는 것은 bit 연산자입니다.

 

 

 7 세그먼트를 요렇게 부분 요소들로 나눠 봅시다. 그러면 위와 같이 나눌 수 있을 텐데요. 여기서 각 숫자를 이루는 데 필요 없는 요소에 대해서 flag를 켜도록 하겠습니다. 예를 들어서, 숫자 0을 봅시다.

 

 

 2번 요소가 필요 없어요. 따라서, 이것만 키면 됩니다. 상태 값은 2^2 = 4가 됩니다. 1은 어떨까요?

 

 

 0, 1, 2, 4, 5가 필요없어요. 따라서 상태값은 2^0 + 2^1 + 2^2 + 2^4 + 2^5이므로, 7 + 16 + 32 = 55가 되겠네요. 이런 식으로 각 숫자에 대해서 상태값을 다 구해 보면 아래와 같이 나오게 됩니다.

 

 

 여기까지가 풀이의 90%입니다. 이제, 이 hc 배열을 가지고 숫자 a에서 숫자 b로 변했을 때, 몇 개의 세그먼트를 반전시켜야 하는지만 구하면 됩니다.

 

 

 0에서 1로 변할 때 몇 개를 반전시키면 될까요? 0에서 1로 변할 때, 0, 1, 4, 5번 요소만 끄면 됨을 알 수 있어요. 이건 어떻게 나왔을까요? 4와 55를 xor 해 보면 알 수 있어요. 두 비트의 상태값이 다른 경우에, xor 값이 1이 되는 성질을 이용합니다. 4와 55를 xor 하면, 51이 나오는데요.

 

 

 이 51은 0번째, 1번째, 4번째, 5번째 bit만 켜져 있어요. 즉, 숫자 a에서 숫자 b로 변할 때 몇 개의 요소를 뒤집어야 하는지에 대한 질문에 대한 답을 구하기 위해서, hc[a] ^ hc[b]값의 켜진 비트 갯수만 세면 됩니다.

 

 

---

 이제 풀이의 나머지 10%를 찾아 봅시다. X와 N이 최대 10^K - 1까지 나올 수 있어요. 그런데 K는 6 이하래요. 그러면, X와 N의 자릿수는 최대 6자리라는 의미입니다. 따라서 층 수가 1자리던, 2자리던, 5자리던, 6자리던 10진수로 변환할 때 돌리는 for loop를 6번 돌리면 됨을 알 수 있어요. 15를 예로 들어볼게요.

 

 

 15를 10으로 나눈 나머지인 5를 0번째 요소에 넣습니다. 다음에, 15를 10으로 나눈 몫을 취합니다. 1이네요.

 

 

 1을 10으로 나눈 나머지인 1을 1번째 요소에 넣어요. 다음에 1을 10으로 나눈 몫인 0을 취해요. 그러면, 2번째 요소부터 5번째 요소까지는 모두 0으로 채워질 겁니다.

 

 

 자릿수 최대가 5라면 어떨까요? N 최대가 88888이라면? 이래도 별 문제가 없습니다. N 최대 값이 88888도 저런 식으로 변환하면 5번째 요소가 0이 되는 건 동일하기 때문입니다. 이제, 각 요소마다 돌면서 숫자 a에서 숫자 b로 변할 때 bit를 몇 개 켜야 하는지만 검사해 주면 됩니다. 이제 코드를 봅시다.

 

 

 현재 층수 x에 대한 정보를 채우는 코드는 9번째 줄에 있습니다. i가 6까지 돌아갔다는 것을 보시면 됩니다.

 

 

 다음에 목적 층에 대해서, 정보를 채워 나가면서, __builtin_popcount로 다른 비트 수를 세는 것을 보시면 됩니다. 중간에 ^ 연산자가 보이는데요. xor 연산의 특징을 잡으면 이해하는 데 그리 어렵지 않습니다. 핵심은 딱 하나입니다. 각 숫자에 대해서 어떤 세그먼트가 켜지고 꺼지는지를 하드 코딩을 해서 문제를 쉽게 해결했다. 하드 코딩도 구현을 하는 데 꽤나 잘 써먹히니, 언제 써야 하는지만 잘 판단하면 신속하게 풀어내실 수 있을 듯 합니다.