가희와 자원 놀이 : 자원 카드를 어떻게 관리할지 생각해 봅시다.

 제가 개최한 1회 코딩테스트는 총 8문제가 있었습니다. 2, 3회에 비해 상대적으로 어렵지 않았는데요. 어디까지나 제가 개최한 코딩테스트 기준일 뿐이니 너무 자신감을 잃지 않으셔도 됩니다. 대회 당시에 맞은 분들 수를 보면, 4번부터 통곡의 벽처럼 다가오셨을 거 같습니다.

 

 이 삼형제 중에 두 문제는 이미 풀이를 마쳤고요. 나머지 한 녀석이 가희와 자원 놀이라는 문제입니다. 세팅하는 데 1달이 넘게 걸렸습니다. 이 문제를 출제하기 위해 턴제 게임의 시스템도 다른 분들이 이해하실 수 있게 서술하기 위해 공부해야 했습니다. 제너레이터 몇 번 다시 재작업 하면서 겨우 출제했던 기억이 나네요. 이 자리를 빌어 검수진 분들에게 다시 한 번 감사 말씀을 올립니다.

 

---

 이제, 이 문제를 풀기 위해서 어떻게 생각하셔야 하는지 생각을 해 봅시다. 먼저 카드 덱입니다. 그림에는 연산 카드 더미라고 되어 있는데요. 이 부분은 그리 어렵지 않습니다. 그냥 배열이던, deque를 쓰면 됩니다. 각 턴마다 어떤 카드를 들고 있는가와 자원 카드를 누군가 가지고 있는가를 어떻게 관리할 것이냐임을 알 수 있어요. 이 둘만 처리할 수 있으면, 나머지는 for문과 switch문을 적절하게 사용하면 되기 때문입니다.

 

 먼저 자원 카드가 20억개 있다고 했어요. 카드를 점유하고 있고 없고는 bit로 관리할 수 있습니다. 예를 들어 1번 카드를 누군가 점유하고 있고, 2번 카드를 점유하고 있지 않다면 1번 비트는 1, 2번 비트는 0 이렇게 관리할 수 있어요.

 

 이렇게요. 그러면 20억개의 비트는 대략 2억 5천개의 byte로 관리를 할 수 있고요. 이를 mb로 환산하면 250mb가 됩니다. 이는 메모리 제한 안에 있습니다. 그리고, bitset에서 random access하는 복잡도는 O(1)이므로, 제출을 해 보면 매우 빠르게 동작함을 알 수 있습니다.

 

 이 발상은 제가 생각하는 풀이 범위 내에 있었으나 뭔가 어색한 부분이 있습니다. 굳이 20억개의 카드에 대한 정보를 저장할 필요가 있을까요? bitwise로 표현될 수 있는 20억개의 정보에 메모리 제한 512면 그냥 고정 정보 20억개를 넣어도 무난하긴 합니다. 문제는 이런 경우입니다. 자원 카드가 1번부터 300억번까지 있다면? 1경번까지 있다면? 고정 정보를 300억개, 1경개를 넣기에는 bitset으로도 부족할 겁니다.

 

 

 그러면 이 정보를 어떻게 압축해야 할까요? next는 아무 일도 안 하니까 무시하면 되고, acquire n이 있어요. 이것은 n번 자원 카드를 획득하는 것인데요. 만약에 누군가 획득했다면, acquire n을 다음 차례에 재사용 한다고 되어 있어요. 그런데, 수많은 카드 중에서 많아봐야 50만번의 턴 동안 누군가 점유하고 있는 자원 카드는 많아 봐야 50만개밖에 안 됩니다. 왜냐하면 acquire n이 n번 자원 카드 하나만 물고 가는 것이기 때문입니다.

 

 고로, 위 정보를 아래와 같이 압축할 수 있습니다.

 

 

 1번 카드와 10억번 자원 카드는 현재 턴에 누군가 가지고 있다. 각 턴마다 x번 자원 카드가 누군가 가지고 있다는 정보를 빠르게 판단하기 위해서는 무엇이 필요한가요? x번 카드가 있고 없고의 문제 아닌가요? 결국 key를 빠르게 찾을 수 있는 자료 구조가 필요합니다. 그렇기 때문에, hash 계열이나 tree 계열의 구조가 적합합니다. 이 문제에서는 unordered_map 저격이 있어서 unordered_map 대신 set, map 등을 활용하면 됩니다.

 

 그런데 정말 이 정보만 저장해도 될까요? 자원 카드 n을 획득한 상태에서 n을 acquire하는 경우나, 자원카드 n을 획득하지 않은 상태에서 release n을 하는 명령이 주어지지 않는다고 했습니다. 즉, n을 누가 획득했는지에 대한 정보를 저장할 필요가 없습니다. 단지 자원 카드 n을 누군가 점유했는지에 대한 정보만 끌고 오면 됩니다. 누가 가지고 있는지 정보를 저장해야 한다면, 카드 id를 key, 누가 가지고 있는지를 value 형태로 관리해 주면 되고요.

 

---

 이제, 유저가 어떤 카드들을 들고 있는지를 관리해야 합니다. 이건 어떻게 할까요? 밑에 있는 게임 규칙을 읽어 보면, 내가 카드를 들고 있지 않은 경우, 더미의 맨 위에 있는 카드를 뽑아서 연산을 수행하고, 그렇지 않으면 현재 내가 가지고 있는 카드의 연산을 수행한다고 되어 있어요. 그 말은? 2개 이상의 카드를 동시에 들고 있을 수 없다는 의미입니다.

 

 그리고 턴을 수행하는 사람 번호나, 연산 카드 번호도 커 봐야 50만 이하입니다. 고로, 가지고 있는 카드의 번호는 배열로 관리해도 됩니다.

 

 

 1번 사람이 1번, 2번 사람이 10만, 3번 사람이 아무것도 가지고 있지 않다고 해 봅시다. 그러면 가지고 있는 카드를 아래와 같이 관리해 주면 됩니다.

 

 

 이 말은 1번은 1번 카드를 가지고 있고, 2번은 10만번 카드를, 3번은 아무 것도 가지고 있지 않음을 의미해요. 그러면 연산 카드 정보는 어떻게 관리하면 되나요? 그냥 연산 카드에 있는 연산을 통으로 배열에 넣어버리면 됩니다.

 

 

 만약에 연산 카드 번호라던지, 게임에 참가하는 사람 번호가 매우 커질 수 있다면 어떻게 해아 할까요? 배열이 아닌 map이나 set으로 관리해 주면 됩니다. 즉, index로 접근하는 대신에 key를 빠르게 찾는 구조로 접근하면 됩니다.

 

 

---

 이제 코드를 보겠습니다.

 

 먼저 카드에는 id와, op, resource 등이 있는데요. 이 resource는 release n이나 acquire n 등을 받을 때 쓰기 위한 용도입니다. 13번째 줄의 ss는 누군가 자원 카드를 점유하고 있는지를 나타내고요. player[i]는 i번 플레이어가 현재 들고 있는 카드에 대한 정보를 나타냅니다.

 

 이렇게 구현을 위한 자료구조를 설계했다면, 흐름대로 구현해 주시면 됩니다.

 

 

 먼저 카드를 뽑으라고 했죠? 그런데, 내가 들고 있는 카드가 없을 때 뽑으라 했어요. player[pn].id가 -1이면, 들고 있는 카드가 없는 것이므로, 더미의 맨 위에서 뽑아주면 됩니다.

 

 

 next는 카드를 그대로 버리라고 했죠? player[pn].id가 -1이 됩니다. 이는 내가 현재 들고 있는 카드가 없다는 의미입니다.

 

 

 다음에 acquire 부분입니다. 자원 카드 rr번을 누군가 점유하고 있지 않으면 rr을 점유하고 카드를 버립니다. 그렇지 않으면 계속 들고 있으면 됩니다. 이 부분을 55번째 줄 if문 1줄로 처리했어요.

 

 

다음에, 자원 카드 rr을 release 하는 연산은 rr을 점유하고 있지 않은 경우 주어지지 않는다고 했으므로, 편안하게 점유하고 있는 카드에서 제거해 버리고 카드를 버리면 됩니다. 해당 코드는 여기에서 볼 수 있고 bitset을 이용한 코드는 여기에서 볼 수 있습니다.