오일러 프로젝트 54

오일러 프로젝트 54 번 문제는 포커게임의 승패를 판정하는 문제이다. 각 플레이어가 받은 카드의 무늬와 숫자를 이용하여 승패를 판정한다. 각 플레이어가 받은 카드를 이용하여 달성한 계급을 판정하는 것 외에 같은 계급에서의 하이카드 혹은 동점일 때 남은 카드에서의 하이카드까지 판별해야하는 부분이 의외로 성가신 문제이다.

포커라는 카드게임은 다섯 장으로 된 패의 높고 낮음에 따라 승부를 냅니다. (포커 규칙을 이미 아는 분이라면 규칙 설명 부분은 건너 뛰셔도 좋습니다.)
카드 한장은 아래와 같은 순서대로 값이 높아집니다.
2,3,4,5,6,7,8,9,10,J,Q,K,A
다섯장으로 이루어진 패의 계급은 낮은 것부터 높은 순서로 다음과 같습니다.

• High Card : 가장 높은 카드의 값 비교
• One Pair : 한 쌍이 같은 카드
• Two Pair : 서로 다른 두 쌍이 같은 카드
• Three of a Kind : 세 장이 같은 카드
• Straight : 모든 카드가 연속된 숫자
• Flush : 모든 카드의 무늬가 같음
• Full House : 세장이 같고, 또 한쌍이 같음 (Three of a Kind + One Pair)
• Four of a Kind : 네 장이 같은 카드
• Straight Flush :  모든 카드가 연속된 숫자이면서 무늬도 같음
• Royal Flush : 10, J, Q, K, A 가 무늬도 같음

두 사람의 패가 같은 종류의 계급이라면, 계급을 구성하는 카드 중 높은 쪽을 쥔 사람이 이깁니다. 예를 들면 8원페어는 5원페어를 이깁니다. 계급을 이루는 카드 숫자까지 같으면, (둘 다 Q원페어 등) 다른 카드를 높은 순서대로 비교해서 승부를 정합니다.
텍스트 파일 poker.txt에는 두 선수가 벌인 1,000회의 승부가 저장되어 있습니다. 한 줄에는 10장의 카드가 공백으로 분리되어 있는데, 앞의 다섯장은 1번 선수의 것이고 뒤의 다섯장은 2번 선수의 패입니다. 잘못되거나 중복된 데이터는 없으며, 무승부도 없습니다.
카드 숫자는 2, 3, …, 9, T, J, Q, K, A 로(숫자 10을 T로 표시), 무늬는 C, D, H, S로 표시되어 있습니다.
예를 들면 3C 3D 3S 9S 9D의 경우 3 풀하우스가 됩니다.
이 데이터를 분석하고 1번 선수가 이긴 횟수를 구하세요.

접근

일단 다음과 같이 생각해볼 수 있다. 규칙에서 설명하는 그대로 쓰자면…

1. 두 선수의 계급을 우선 비교한다. 계급이 높은 쪽이 승리
2. 계급이 같다면 계급을 구성하는 카드의 값을 비교한다. 스트레이트의 경우 가장 높은 카드를 가진 선수가 승리
3. 2까지 동일하다면 나머지 카드의 가장 높은 카드를 비교한다.

하지만 포커를 통해서 구성한 계급에 대해서 점수를 매겨서 점수로만 비교를 한다면 어떨까

1. 스트레이트 플러시는 스트레이트와 플러시를 동시에 달성했다. 따라서 스트레이트 판정 후 플러시 판정을 거쳐서 점수를 합산한 것으로 별도 판정 절차를 없앨 수 있다.
2. 같은 방식으로 풀하우스는 스리카인드와 원페어의 점수를 각각 합산한 것과 같은 점수로 맞춘다.
3. 투페어는 원페어의 점수의 2배이다.

하이카드는 2가지로 나뉘는데, 우선 상위 계급을 달성했을 때의 가장 높은 카드와, 나머지 카드의 가장 높은 카드를 각각 찾는다. 그리고 그 점수를 비교하도록 한다.
예를 들어 다음과 같은 점수 판을 작성할 수 있다.

• Straight Flush : 95,000 (Straight + Flush)
• Four Kind : 80,000
• Full House : 55,000 ( Three Kind + One Pair)
• Flush : 50,000
• Straight : 45,000
• Three of a Kind: 40,000
• Two Pair : 30,000 (One Pair + One Pair)
• One Pair : 15,000

이를 이용하면 Four Kind, Flush, Straight, Three of a Kind, One Pair 가 있는지만 판정해서, 점수를 합산해나가면 계급을 찾을 수 있다. (참고로 Pair는 2개 이상 나올 수 있다.) 로열 플러시의 경우에는 스트레이트 플러시 중에서 하이카드(에이스)가 가장 높기 때문에 별도의 계급으로 정하지 않아도 된다.

판정 로직

점수는 같은 무늬의 카드가 몇 장 있는가, (플러시), 같은 숫자의 카드가 몇 장씩 있는가 (페어, 3카인드, 4카인드), 연속된 숫자가 있는가로 판정한다. 참고로 가끔 동네 포커에서는 스트레이트 판정을 순환식으로 (Q K A 2 3) 하는 경우가 있는데 이는 현재 문제의 규칙에서는 스트레이트로 인정하지 않는다.
점수 계산시에는 각 무늬별 카드 수를 기록하는 맵과  카드 번호별 카드 수를 기록하는 맵을 둔다. 각각의 카드에 대해서 무늬와 점수를 통해 각 맵에 해당하는 카드 값을 올려준다. 그러면 무늬중에 4개를 만족하는지 여부로 플러시를 판정하고, 개수가 4,3,2인 숫자가 있는지를 보고 페어 여부를 가릴 수 있다.

하이카드

높은 계급의 달성 여부를 우선 검사하여, 제 1 하이카드를 결정한다. 조합되는 계급의 경우에는 높은 카드점수 순으로 판정하고, 이미 제 1 하이카드값이 있는 경우 제 2 하이카드에 넣는다.
최종적으로 계급점수 > 제1하이카드 > 제2하이카드 순으로 비교하여 승패를 판정할 수 있다.

Swift 구현

왠지 각 카드를 표현하는 클래스와, 카드 묶음을 표현하는 클래스를 만들고 어쩌고…해야 할 것 같은 기분이지만, 함수 하나에서 모두 처리할 수 있다. evaluate 라는 함수를 만들어서 카드 덱을 받아 포커 점수를 구하는 함수이다.

1.  입력 받는 인자의 타입은 문자열이다. 이는 공백 4자와 카드 10자를 포함해야 한다.
2. 리턴값의 타입은 (Int, Int, Int) 이다. 첫번째 값은 계급에 의한 값, 두 번째 값은 첫 번째 하이카드, 세 번째 값은 두 번째 하이카드이다. (하이카드의 순서는 계급순)

무늬별로 몇 장, 숫자별로 몇 장이 모였는지를 세는 것을 아이디어의 근간으로 하기 때문에 사전(Dictionary) 타입을 정말 빡세게 쓰는 문제이다. 참고로 테스트 케이스가 1000개나 되기 때문에 오답이 나는 경우 어디서 틀렸는지를 체크하기가 정말 쉽지 않다.

Evaluate 함수

점수 계산에 필요한 내부 값들을 준비한다.

func evaluate(_ s: String) -> (Int, Int, Int) = {
  let priorities = "23456789TJQKA"
  var numberMap: [Int: Int] = [:] // 1
  var faceMap: [Character: Int] = [:] // 2
  var value = 0 // 3
  var h1: Int? = nil
  var h2: Int? = nil
  ...
} 

1.  numberMap : 카드의 숫자값에 따라 몇 장이 들어왔는지를 카운트하는 맵
2. faceMap :  카드의 모양 종류에 따라 몇 장이 들어왔는지를 카운트한다. 플러시 여부를 판정하기 위함
3. priority : 카드에 쓰인 숫자값에 따라서 점수를 정하기 위해 있는 문자열. 이를 이용해서 스트레이트도 판정할 것이다.
4. value : 등급에 따른 점수
5. h1, h2 : 하이카드 점수. 상위 계급에서 하이카드가 결정되었다면, 하위 계급에서는 다음 하이카드를 기록해야 한다.

입력값 파싱

입력값이 들어오면 공백으로 분해하여 각 카드를 만들고, 앞글자를 통해서 카드 숫자를 판정하고, 뒷글자를 통해서 문양 종류를 판정한다.

let cards = s.split(separator: " ")
for card in cards {
  let face = card[card.index(before: card.endIndex)] // card.last! 로 대체할 수 있다. 
  faceMap[face] = (faceMap[face] ?? 0) + 1
  let number = card[card.startIndex]
  let point = priorities.distance(from: priorities.startIndex, 
                                  to:(priorities.index(of: number))!) + 2
                                  // "2"가 0이나오기 때문에 +2
  numberMap[point] = (numberMap[point] ?? 0) + 1
}

 

계급 판정

이제 정리한 데이터를 바탕으로 계급을 판정해보자. 단일 점수로 가장 높은 것부터 판정한다.

Four of a Kind

같은 숫자 네장이 있는 경우이다. numberMap 중에서 값이 4 인 것이 있다면, 이 계급에 해당된다. 이 때 첫번째 하이카드는 4장을 이루는 카드의 번호이고, 나머지 한 장이 두 번째 하이카드가 된다.

// Four of a Kind
numberMap.filter{ $0.1 == 4 }.forEach {
  value += 80_000
  if h1 == nil { h1 = $0.0 }
}

사전(Dictionary<Key, Value>)에 대해 filter를 거는 것은 매 아이템이 (key: Key, value: Value) 인 튜플의 시퀀스처럼 동작한다.¹ 따라서 이 중에서 값이 4 인 것을 찾고 그 때마다 8만점을 더해준다. 최초 시행 시에 해당 키가 카드숫자이므로 이 값을 하이카드1에 할당해준다. 물론, 5장을 받기 때문에 2회 시행이라는 건 없지만, 다른 판정 코드와 비슷한 모양으로 통일해주기 위해서 이렇게 했다.
참고로 이 로직은 4장인지 검사하는 것을 3장으로 하면 Three of a Kind 를 검사하는 로직과 동일하다.

Flush

플러시는 다섯장이 모두 같은 문양인 경우이다. faceMap에서 같은 식으로 처리한다.  이 때 하이카드는 가장 높은 숫자의 번호를 이용하면 된다.

// Flush
faceMap.filter{ $0.1 == 5 }.forEach { _ in // 클로저 내부에서 인자를 쓰지 않는다.
  value += 50_000
  if h1 == nil { h1 = numberMap.sorted{ $0.0 > $1.0 }.first?.0 }
}

가지고 있는 카드 숫자는 numberMap의 키들이라 이를 기준으로 역순으로 정렬한 첫 값의 키를 이용한다.

Straight

스트레이트는 연속된 숫자값일 때를 가정한다. 흔히 카드의 숫자값만 모은 다음, 이를 정렬하여 연속된 값인지 확인한다. 이를 검사하는 방법에는 몇 가지가 있는데,

1. 먼저 숫자에 해당하는 문자를 찾아서 이를 정렬한 다음, 우선순위 지표의 서브스트링인지 검사한다.
2. 숫자맵의 키가 5개이며, 연속된 값인지 검사한다.

참고로 숫자에 해당하는 문자는 2…9의 숫자와 T, J, Q, K, A 이니, 그냥 sorted() 로 정렬하면 안된다. (여기서 실수하면 보통 2, 3개 정도 많은 오답이 나온다.)

// Straight
let isLeftCard: (Character, Character) -> Bool = { x, y in
  let i = priorities.index(of: x) ?? priorities.startIndex
  let j = priorities.index(of: y) ?? priorities.startIndex
  return x < y
}
let keys = String(cards.flatMap{ $0.first }.sorted(by: isLeftCard))
if let _ = priorities.range(of: keys) { // 정렬한 숫자기호가 연속된 값내에 있다.
  value += 45_000
  if h1 == nil { h1 = numberMap.sorted{ $0.0 > $0.1 }.first?.0 }
}

Pair

One Pair, Two Pair 는 각각의 페어가 몇 번 나오냐에 의해 결정된다. 따라서 2 장인 카드에 대해서 루프를 돈다. 하이카드의 결정에 대해서는 쓰리 카인드 후에 원 페어가 나올 수 있고, 두 번째 원페어의 경우에는 해당 카드 값이 두 번째 하이카드 값이 되어야 한다. 이점에 유의해서 다음과 같이 정리한다.

// Pairs
let n = (numberMap.filter{ $0.value == 2})
n.sorted{ $0.0 > $1.0 }.forEach {
  value += 15_000
  if h1 == nil { h1 = $0.0 }
  else if h2 == nil { h2 = $0.0 }
}

하이카드

포카인드 이하의 구성을 갖는 경우 계급 구성에서 제외되는 카드에 대해서 두 번째 하이카드를 결정해준다. 만약 점수가 0이라면 (원페어도 못했다면) 첫 번째 하이카드만 결정한다.

let m = numberMap.filter{ $0.value == 1}
m.sorted{ $0.0 > $1.0}.forEach {
  if h1 == nil { h1 = $0.0 }
  else if value == 0, h2 == nil { h2 = $0.0 }
}

이제 모든 판정이 끝났고, 결과를 내보낸다. 하이카드가 없으면 0 으로 대체해서 보낸다.

return (value, h1 ?? 0, h2 ?? 0)

정리

남은 작업은 해당 URL에서 파일을 읽어들이고,  자르고 각각 판정과 비교하는 부분이다.  이를 포함하는 전체 코드는 아래와 같으며, 파이썬 해답은 다음 페이지에 게재한다.