예전에 삼성 상시 SW 역량평가 B형을 준비하면서 추천받은 문제 중 하나가 Iceberg Orders였습니다. 실제 시험이야 이것보다 어렵게 나오지는 않으니 굳이 목숨 걸고 풀지는 않았지만, 언젠가는 해결해야겠다는 생각은 하고 있었습니다. 이번 포스팅에선 문제에 접근하는 두 가지 관점을 살펴보고 어떻게 구현하면 될지 생각해보도록 하겠습니다.

문제의 이해

PS 문제 치고는 뭔가 설명이 긴데, 무려 주식 거래 시뮬레이터를 만들어야 합니다. 거래 방식은 다음과 같습니다.

  • 모든 주문에는 우선순위가 부여됩니다.

  • 주문 목록에 있는 주문에는 자동으로 부여되는 우선순위를 제외하고 6개의 변수가 있습니다.

    • ID: 주문 ID
    • T: 주문 타입. 매수(BUY)=1, 매도(SELL)=2
    • P: 주문 가격입니다.
    • V: 총 주문량입니다. 거래가 이루어지면 감소합니다.
    • TV: 팁 주문량. 목록에서 꺼낸 주문에 대해, 한 번의 체결에서 거래 가능한 양입니다.
    • CV: 현재 거래 가능한 양입니다. 거래가 이루어진 후에는 주문 상대의 V가 더 크다면 0이 된 후 TV만큼 다시 채워집니다.만약 V가 부족하다면 V만큼만 채워지고, 남은 주문량이 없으면 목록에서 사라집니다.
    • PR: 우선순위. 같은 가격에 대해, 우선순위가 높은 주문이 우선 체결됩니다. 체결 후 CV가 다시 채워진 주문은 최후순위가 됩니다.
  • 매도 주문이 들어오면 매수 주문들 중에서 조건에 부합하는 것들을 찾아 거래를 체결합니다.
    • 이 때, 매도 주문 가격보다 높은 가격을 부르는 매수 주문을 찾습니다.
    • 그러한 것들이 여러 개라면 가장 비싸게 사려는 주문을 찾고,
    • 그러한 것들이 여러 개라면 우선 순위가 가장 높은 주문을 찾습니다.
    • 거래 가격은 비싸게 사는 쪽이 기준이 됩니다.
  • 매수 주문이 들어오면 매도 주문들 중에서 조건에 부합하는 것들을 찾아 거래를 체결합니다.
    • 이 때, 매수 주문 가격보다 낮은 가격을 부르는 매도 주문을 찾습니다.
    • 그러한 것들이 여러 개라면 가장 싸게 팔려는 주문을 찾고,
    • 그러한 것들이 여러 개라면 우선 순위가 가장 높은 주문을 찾습니다.
    • 거래 가격은 싸게 파는 쪽이 기준이 됩니다.

  • 주문 목록에서 조건에 부합하는 주문을 찾을 수 있을 때까지, 또는 주문의 V가 0이 될 때까지 거래를 반복합니다.

  • 해당 주문에서 발생한 거래는 거래 상대의 ID가 같은 것들을 병합하여 하나로 만든 후, 거래 목록에 저장합니다.

  • 거래 목록에 저장되는 변수는 다음과 같습니다.

    • BUY_ID: 매수 주문의 ID
    • SELL_ID: 매도 주문의 ID
    • P: 거래 가격
    • V: 두 ID 간 체결된 거래량

전형적인 B형 문제입니다. 복잡다단한 조건이 거의 A4용지로 3페이지 이상 되고, 시뮬레이션 과정을 실제로 보기 전엔 제대로 이해하기도 힘든 게 딱 이런 스타일입니다. 어쨌든 문제를 풀어봅시다.

단순 구현

만약 데이터가 작다면 구현에는 아무 어려움이 없을 겁니다. 주문 목록에서 조건에 맞는 걸 다 꺼내고 정렬해준 후, 하나씩 거래를 체결해가면서 V가 0이 되거나 목록이 모두 소진될 때까지 시뮬레이션해주면 됩니다.

하지만 위 방식은 큰 문제가 있습니다. 데이터가 큰 경우 위 방식은 너무 느립니다.

  • 주문 목록에서 조건에 맞는 걸 다 꺼내고 (\(O(N)\))

  • 정렬해준 후 (\(O(N \log N)\))

  • 하나씩 거래를 체결해가면서 (\(O(V)\))

시뮬레이션 하는 건 택도 없습니다.

관찰

이 문제를 해결하기 위해서는 몇 가지를 관찰해야 합니다.

  • 거래 가격 P는 정수이며, 그 범위가 꽤 작은 편이다.

  • 항상 최대 혹은 최소 가격인 상대하고만 거래가 이루어진다.

가격대에 따라 주문을 분류하여 따로 관리할 수 있다면 주문 목록에서 조건에 맞는 걸 다 꺼내는 과정을 \(O(1)\)로 줄일 수 있습니다. 최대, 최소 가격을 찾는 과정은 균형이진트리, 힙 등의 자료구조를 써서 \(O(\log P)\)로 줄일 수 있습니다.

  • 거래가 체결된 주문은 같은 가격대에 대해서만 뒤로 밀려난다.

또한 가격이 다르면 우선순위끼리는 비교가 일어나지 않으므로 같은 가격대에서 비교할 때만 의미가 있습니다. 그렇다면 우선순위를 실제 변수로 갖고 있는 것이 아니라 원형 연결 리스트 등의 자료구조를 써서 정렬하는 과정을 없앨 수 있습니다.

주문을 항상 정렬된 상태로 갖고 있기 위한 준비는 끝났습니다. 하지만 실제 시뮬레이션 과정이 오래 걸리면 아무 의미가 없습니다.

  • 거래 상대의 TV가 매우 작다면, 단순한 시뮬레이션의 시간복잡도는 \(O(V)\)에 가까워진다.

문제에서 발생하는 모든 거래 목록의 크기는 십만을 넘지 않는다는 조건이 주어지므로, 이를 이용할 수 있으면 좋겠습니다.

  • 한 가격대의 모든 주문량의 합 SV가 V보다 작다면…?

어떤 가격대 P에 대해, 거래 상대의 주문 목록을 모두 소진시킬 수 있다면, 시뮬레이션 과정을 크게 생략할 수 있습니다. 거래량은 거래 상대의 남은 V만큼 이루어집니다. 이 때 시간복잡도는 \(O(N)\)이지만, 이를 모두 합쳐도 십만이 되지 않으므로 상관 없습니다.

만약 어떤 주문이 모든 거래가 체결된 후에 목록에 들어간다면, 해당 주문은 거래 상대를 모두 소진시킨 후가 됩니다. 여기까진 간단한 관찰만으로도 쉽게 구현이 가능합니다.

이 문제에서 병목이 되는 부분은 거래 상대를 소진시킬 수 없을 때의 처리입니다. 어떤 가격대에서 주문을 더이상 소진시킬 수 없으면 그 때는 각 주문에 대한 체결량을 계산해주어야 합니다.

그런데 각 주문들의 V, CV, TV가 제각각인데다 우선순위에 따라 돌아가며 체결해야 하므로 한번에 계산하기는 불가능합니다.

최적화

아마 이 부분을 해결할 수 있는가에 따라 B형 합불이 갈라진다고 봐도 무방할 겁니다. 거래 상대를 소진시킬 수 없을 때에 대해서도 몇 가지를 관찰할 수 있습니다.

일단 같은 가격대인 주문 상대의 모든 CV를 처리해줍시다. CV를 모두 0으로 만들어주면서 V를 감소시킵니다. V가 0이 된다면 정말 운이 좋습니다! 더 이상의 거래가 만들어지지 않으므로 시뮬레이션을 종료하면 됩니다.

하지만 대부분의 경우엔 모든 CV만큼 체결한 후에도 V가 남아있을 겁니다. 다음 사실들을 관찰할 수 있습니다.

  • 임의의 주문 상대 \(i\)와 체결이 이루어진 후 다시 상대 \(i\)와 만나기 전까지 거래량은 TV의 합과 같다.

  • 만일 TV의 합과 같지 않다면 이는 어떤 주문이 모두 소진되었음을 의미한다.

해당 성질을 잘 활용해야 하는 비슷한 유형의 문제로 무지의 먹방 라이브가 있습니다. 몇 번 루프를 돌다가 어느 지점에서 끝날 것인가를 찾는다는 점에서 거의 같은데, 다만 다른 점이 있다면 먹방 라이브 쪽은 모든 TV가 1로 고정되어 있습니다.

최적화 방안은 2가지 정도를 생각해냈습니다.

현재 우선순위가 가장 높은 거래 상대에서 시작하여 다시 돌아올 때까지의 거래를 루프라 합시다. 그렇다면 완전한 루프를 몇 번 돌 수 있는지만 알 수 있으면 시뮬레이션 과정을 크게 줄일 수 있습니다. 서로 다른 최적화 방법은 결국 완전한 루프의 수를 찾는 과정에 불과합니다.

이분 탐색

\(k\)번 강제로 루프를 돌리게 해봅니다. 만약 모든 거래 상대에 대해 \(k\)번 거래가 이루어진 후 V가 0 이상이라면 실제 완전한 루프의 수는 \(k\) 이상입니다. V가 0 미만이라면 완전한 루프의 수는 \(k\) 미만입니다. 시뮬레이션 과정을 결정 문제로 치환할 수 있으므로 이분탐색이 가능해집니다. 최대 루프의 수는 알 수 없으나 \(V\)에 비례하고, 이 때 시간복잡도는 \(O(N \log V)\)입니다.

정렬

거래 상대를 \(V / TV\) 기준 오름차순으로 정렬해줍니다. \(V / TV\) 값이 변하기 전까진 매 루프의 거래량이 같습니다. 그럼 같은 거래량의 루프는 일괄로 처리할 수 있으므로 그만큼을 처리해줍니다. 소진된 주문만큼 한 루프의 거래량은 줄어듭니다. 루프의 거래량이 달라지는 횟수는 \(N\) 이하이므로 일괄 처리 또한 \(N\)번 이루어집니다. 이 때 시간복잡도는 \(O(N \log N)\)입니다. 이분탐색 방식보다 계산식은 작지만 상수가 큰 방식이므로 실질적으로는 더 오래 걸릴 수 있습니다.

예전에 먹방 라이브 문제를 정렬 후 시뮬레이션 하는 방식으로 풀었는데, 그걸 무의식 중에 떠올린 건지 이번 문제도 정렬 방식으로 풀었습니다. 나중에 이분탐색 방식으로도 풀어봐야겠습니다.