백준 BOJ 27162 Yacht Dice 문제의 파이썬 python 풀이입니다.

https://www.acmicpc.net/problem/25204

문제

《Yacht Dice》는 여러 명이 플레이하는 주사위 게임입니다. 플레이어는 우선 주사위를 $5$개 굴립니다. 이후 원하는 주사위를 고정시킨 뒤, 남은 주사위를 다시 굴리는 일을 두 번 이하로 할 수 있습니다. 그렇게 주사위를 굴려 나온 값들의 조합으로 아래 족보에서 이전까지 선택하지 않은 하나를 선택해 점수를 기록합니다.

• Ones: $1$이 나온 주사위의 눈 수의 총합.
• Twos: $2$가 나온 주사위의 눈 수의 총합.
• Threes: $3$이 나온 주사위의 눈 수의 총합.
• Fours: $4$가 나온 주사위의 눈 수의 총합.
• Fives: $5$가 나온 주사위의 눈 수의 총합.
• Sixes: $6$이 나온 주사위의 눈 수의 총합.
• Four of a Kind: 동일한 주사위 눈이 $4$개 이상**이라면, 동일한 주사위 눈 $4$개의 총합. 아니라면 $0$점.
• Full House: 주사위 눈이 정확히 두 종류로 이루어져 있고 한 종류는 $3$개, 다른 종류는 $2$개일 때, 주사위 눈 $5$개의 총합. 아니라면 $0$점.
• Little Straight: 주사위 눈이 $1$, $2$, $3$, $4$, $5$의 조합이라면, 즉 $1$에서 $5$까지의 눈이 한 번씩 등장했다면 $30$점, 아니라면 $0$점.
• Big Straight: 주사위 눈이 $2$, $3$, $4$, $5$, $6$의 조합이라면, 즉 $2$에서 $6$까지의 눈이 한 번씩 등장했다면 $30$점, 아니라면 $0$점.
• Yacht: 동일한 주사위 눈이 $5$개라면 $50$점, 아니라면 $0$점.
• Choice: 모든 주사위 눈의 총합.

모든 플레이어의 모든 족보가 사용되면 게임이 끝납니다.

지금은 한별이 차례입니다. 한별이는 첫 번째로 굴린 주사위의 조합에서 세 개의 주사위를 고정하고 나머지 두 개의 주사위를 다시 굴려야 하는 상황입니다. 이 상황에서 나올 수 있는 점수의 최댓값은 얼마일까요?

입력

첫 번째 줄에는 이미 선택한 족보를 의미하는 $12$글자의 문자열이 주어집니다. 문자열의 모든 글자는 Y 또는 N이며, 글자들 중 적어도 하나는 Y입니다.

•  $1$번째 글자가 Y라면 Ones를 선택할 수 있습니다. 마찬가지로 $6$번째 글자까지 같은 규칙이 적용되어, $6$번째 글자가 Y라면 Sixes를 선택할 수 있습니다.
•  $7$번째 글자가 Y라면 Four of a Kind를 선택할 수 있습니다.
•  $8$번째 글자가 Y라면 Full House를 선택할 수 있습니다.
•  $9$번째 글자가 Y라면 Little Straight를 선택할 수 있습니다.
•  $10$번째 글자가 Y라면 Big Straight를 선택할 수 있습니다.
•  $11$번째 글자가 Y라면 Yacht를 선택할 수 있습니다.
•  $12$번째 글자가 Y라면 Choice를 선택할 수 있습니다.

각각의 경우에서 글자가 N이라면 해당하는 족보를 이미 선택하여 다시 선택할 수 없음을 의미합니다.

두 번째 줄에는 한별이가 첫 번째로 굴린 조합에서 고정한 주사위들의 눈의 수를 나타내는 $1$과 $6$ 사이의 정수 $3$개가 공백으로 구분되어 주어집니다.

출력

한별이가 얻을 수 있는 점수의 최댓값을 출력합니다.

풀이

compute_score 함수

이 함수는 주사위 조합과 선택한 족보에 따라 점수를 계산합니다.

def compute_score(dice, category_idx):

• dice: 5개의 주사위 눈을 담은 리스트
• category_idx: 0-11 사이의 정수로, 선택한 족보를 나타냄

함수는 각 족보 유형에 따라 다른 로직을 적용합니다.

1. Ones부터 Sixes까지 (인덱스 0-5)

   if 0 <= category_idx <= 5:  # Ones to Sixes
    target = category_idx + 1
    return sum(d for d in dice if d == target)

• category_idx + 1이 찾고자 하는 주사위 눈 값
• 해당 값과 일치하는 주사위 눈들의 합을 반환
  

2. Four of a Kind (인덱스 6)

   elif category_idx == 6:  # Four of a Kind
    for value in range(1, 7):
        if dice.count(value) >= 4:
            return value * 4
    return 0

• 같은 눈이 4개 이상인 경우, 그 눈 × 4를 반환
• 없으면 0점을 반환
  

3. Full House (인덱스 7)

   elif category_idx == 7:  # Full House
    counts = {}
    for d in dice:
        counts[d] = counts.get(d, 0) + 1
   
    values = list(counts.values())
    if len(counts) == 2 and (3 in values and 2 in values):
        return sum(dice)
    return 0

• 주사위 눈의 등장 횟수를 딕셔너리에 저장
• 딕셔너리의 길이가 2(두 종류의 눈만 있음)이고, 한 종류는 3번, 다른 종류는 2번 등장한다면 모든 주사위의 합을 반환
• 조건을 만족하지 않으면, 0점을 반환

4. Little Straight (인덱스 8)

   elif category_idx == 8:  # Little Straight
    if sorted(dice) == [1, 2, 3, 4, 5]:
        return 30
    return 0

• 주사위 눈이 1부터 5까지 모두 있으면 30점을 반환
• 아니면 0점을 반환

5. Big Straight (인덱스 9)

   elif category_idx == 9:  # Big Straight
    if sorted(dice) == [2, 3, 4, 5, 6]:
        return 30
    return 0

• 주사위 눈이 2부터 6까지 모두 있으면 30점을 반환
• 아니면 0점을 반환

6. Yacht (인덱스 10)

   elif category_idx == 10:  # Yacht
    if len(set(dice)) == 1:
        return 50
    return 0
   

- 모든 주사위 눈이 같으면(집합의 크기가 1이면) 50점을 반환
- 아니면 0점을 반환

<br>

**Choice (인덱스 11)**:
```python
elif category_idx == 11:  # Choice
    return sum(dice)

• 모든 주사위 눈의 합을 반환

시간 복잡도 분석

• 남은 두 주사위를 굴리는 경우의 수: 6 × 6 = 36
• 각 경우마다 최대 12개의 족보를 확인: 36 × 12 = 432
• 각 족보마다 점수 계산은 O(1) 또는 O(n) 시간이 소요됨 (여기서 n은 주사위 개수 5, 상수 취급 가능)
• 따라서 전체 시간 복잡도는 O(36 × 12 × 5) = O(2160) = O(1)

예제 검증

def test_examples():
    # 예제 1
    example1_available = "YYYYYYYYYYYN"
    example1_fixed = [1, 5, 6]

    available_categories1 = [i for i in range(12) if example1_available[i] == 'Y']
    max_score1 = 0
    best_dice1 = []
    best_category1 = -1

    for d1 in range(1, 7):
        for d2 in range(1, 7):
            current_dice = example1_fixed.copy() + [d1, d2]
            for category in available_categories1:
                score = compute_score(current_dice, category)
                if score > max_score1:
                    max_score1 = score
                    best_dice1 = current_dice
                    best_category1 = category

    print(f"예제 1 최대 점수: {max_score1}")
    print(f"최적 주사위: {best_dice1}, 사용 족보: {best_category1}")

# 예제 테스트
test_examples()

전체 코드

# 25204 문자열 정렬

def compute_score(dice, category_idx):
    if 0 <= category_idx <= 5:  # Ones to Sixes
        target = category_idx + 1
        return sum(d for d in dice if d == target)

    elif category_idx == 6:  # Four of a Kind
        for value in range(1, 7):
            if dice.count(value) >= 4:
                return value * 4
        return 0

    elif category_idx == 7:  # Full House
        counts = {}
        for d in dice:
            counts[d] = counts.get(d, 0) + 1

        values = list(counts.values())
        if len(counts) == 2 and (3 in values and 2 in values):
            return sum(dice)
        return 0

    elif category_idx == 8:  # Little Straight
        if sorted(dice) == [1, 2, 3, 4, 5]:
            return 30
        return 0

    elif category_idx == 9:  # Big Straight
        if sorted(dice) == [2, 3, 4, 5, 6]:
            return 30
        return 0

    elif category_idx == 10:  # Yacht
        if len(set(dice)) == 1:
            return 50
        return 0

    elif category_idx == 11:  # Choice
        return sum(dice)

    return 0

def solve():
    # 선택 가능한 족보 읽기
    available = input().strip()
    available_categories = [i for i in range(12) if available[i] == 'Y']
    # Y가 있는 위치의 인덱스를 리스트에 저장

    # 고정된 주사위 읽기
    fixed_dice = list(map(int, input().strip().split()))

    max_score = 0

    # 남은 두 주사위의 모든 경우의 수 시뮬레이션 (1-6, 1-6) => 36가지 모두 확인
    for d1 in range(1, 7):
        for d2 in range(1, 7):
            current_dice = fixed_dice.copy() + [d1, d2]

            # 각 선택 가능한 족보에 대한 점수 계산
            for category in available_categories:
                score = compute_score(current_dice, category)
                max_score = max(max_score, score)

    return max_score




print(solve())

백준 BOJ 25204 문자열 정렬 파이썬 python 문제 풀이입니다.

https://www.acmicpc.net/problem/25204

두 가지 풀이 방법을 작성했습니다.

1. functools 모듈을 활용한 풀이
2. __lt__ (less than) 연산자를 오버라이드한 래퍼 클래스를 이용한 풀이

문제

Bob은 문자열 정렬기를 만들어야한다.

문자열은 영문 알파벳 이외에도 붙임표 ('-')가 들어가는 경우가 있기 때문에 처리가 까다롭다. 이 문제에 한해, 서로 다른 두 문자열 $X$, $Y$의 "사전식" 순서는 아래 규칙에 따라 정한다:

1.  $X$가 $Y$의 접두사인 (prefix) 경우 $X$가 $Y$보다 앞선다. 반대로, $Y$가 $X$의 접두사인 경우 $Y$가 $X$보다 앞선다.
2. 위 경우에 해당하지 않을 경우: 첫번째 문자부터 시작하여 $X$, $Y$가 처음으로 달라지는 부분이 i$i$번째 문자라 하자. $X$의 $i$번째 문자를 $X_i$, $Y$의 $i$번째 문자를 $Y_i$라 했을 때:
   1. 둘 중 하나만 붙임표 ('-')인 경우, 붙임표가 들어간 문자열이 사전순에서 뒤진다. 예를 들어, Xi$X_i$가 붙임표이고 $Y_i$가 붙임표가 아닌 경우, $Y$가 앞선다.
   2. 둘 다 알파벳인 경우, 대소문자를 무시했을 때 서로 다른 알파벳이라면, 알파벳 순서를 따른다. 만약 같은 알파벳이지만 하나만 대문자인 경우 대문자가 들어간 문자열이 사전순에서 앞선다.

예를 들어, 아래와 같은 문자열 쌍을 비교해보자:

•  $X$ =Santa-Mar과 $Y$ = Santa-Maria이 경우 규칙 1에 따라 $X$가 앞선다. $X$가 $Y$의 접두사이기 때문이다.
•  $X$ = San-Francisco 와 $Y$ = Santa-Clara: 이 경우 처음 3$3$개의 문자는 같지만 4$4$번째 문자가 '-'와 't'로 다르다. 규칙 2-1에 따라 $X$가 $Y$에 뒤진다.
•  $X$ = Seoul과 $Y$ = seoul: 이 경우 규칙 2-2에 따라 Seoul이 앞선다.

입력으로 $n$개의 문자열이 주어졌을 때, 위 규칙에 따라 사전식 정렬 후 출력하는 문자열 정렬기를 만들어보자.

입력

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $n$이 주어진다. 다음 $n$줄에 걸쳐 각 줄에 문자열이 하나씩 주어진다.

출력

각 테스트 케이스의 정답을 $n$줄에 걸쳐 출력한다. 각 줄에는 사전순으로 정렬된 문자열 하나씩을 순서대로 출력한다.

풀이

1. functools 모듈을 활용한 풀이

• functools 모듈과 cmp_to_key 함수
  • functools는 파이썬의 내장 모듈로, 함수를 다루는 데 유용한 도구들을 제공합니다. 그 중 cmp_to_key 함수는 Python 2에서 사용되던 비교 함수를 Python 3의 키 함수로 변환해주는 역할을 합니다.
    • Python 2에서는 sort() 함수에 cmp 매개변수를 제공하여 두 요소를 직접 비교하는 함수를 사용할 수 있었습니다.
    • Python 3에서는 이러한 방식이 제거되고 key 매개변수만 남았습니다.
    • cmp_to_key는 두 요소를 비교하는 함수를 받아서, 각 요소에 대해 정렬 키를 생성하는 함수로 변환해줍니다.

# 25204 문자열 정렬

import sys
import functools

def compare(s1, s2):
    # 두 문자열을 한 글자씩 비교
    i = 0
    min_len = min(len(s1), len(s2)) # 두 문자열 중 더 짧은 문자열의 길이

    while i < min_len:
        # 두 문자열의 현재 위치 문자가 같으면 다음 문자로 넘어감
        if s1[i] == s2[i]:
            i += 1
            continue

        # 다른 문자를 발견했을 때
        # 붙임표(-)) 우선순위 처리 => 두 문자가 다르고 그 중 하나가 붙임표(-)라면, 붙임표가 아닌 문자열이 앞에 온다
        if s1[i] == '-':
            return 1  # s2가 앞선다
        if s2[i] == '-':
            return -1  # s1이 앞선다

        # 알파벳 비교
        if s1[i].lower() != s2[i].lower():
            # 대소문자 무시했을 때 다른 알파벳이면 알파벳 순서
            return -1 if s1[i].lower() < s2[i].lower() else 1
        else:
            # 같은 알파벳이지만 대소문자가 다른 경우 대문자가 앞선다
            return -1 if s1[i].isupper() and s2[i].islower() else 1 if s1[i].islower() and s2[i].isupper() else 0

    # 여기까지 왔다면 접두사 관계 확인
    if len(s1) == len(s2):
        return 0
    # 짧은 문자열이 긴 문자열의 접두사면 짧은 것이 앞선다
    return -1 if len(s1) < len(s2) else 1

# 입력 처리
input = sys.stdin.readline
T = int(input())

for _ in range(T):
    N = int(input())
    strings = [input().strip() for _ in range(N)]

    # functools.cmp_to_key를 사용하여 정렬
    sorted_strings = sorted(strings, key=functools.cmp_to_key(compare))

    # 순차적으로 출력
    for s in sorted_strings:
        print(s)

각 테스트 케이스마다

1. 문자열 개수 N을 입력받습니다.
2. N개의 문자열을 입력받아 리스트에 저장합니다.
3. sorted() 함수와 functools.cmp_to_key(compare)를 사용하여 문자열을 정렬합니다.
4. 정렬된 문자열을 한 줄에 하나씩 출력합니다.

2. __lt__ (less than) 연산자를 오버라이드한 래퍼 클래스를 이용한 풀이

모듈 없이도 구현이 가능한 방식입니다.

• 파이썬 클래스와 비교 연산자 오버라이딩

파이썬에서 객체를 비교할 때 (<, >, == 등), 파이썬은 특정 메서드를 찾아 호출합니다. 이것을 magic method 또는 double underscore method 라고 부릅니다.

• __lt__ (less than): < 연산자에 대응
• __gt__ (greater than): > 연산자에 대응
• __eq__ (equal): == 연산자에 대응

파이썬의 sort() 함수는 객체들을 정렬할 때 기본적으로 < 연산자를 사용합니다.
__lt__ 메서드를 구현하면, 파이썬은 정렬 과정에서 이 메서드를 호출하여 객체들의 순서를 결정합니다.

# 25204 문자열 정렬

import sys

# 입력 처리
input = sys.stdin.readline
T = int(input())

for _ in range(T):
    N = int(input())
    strings = [input().strip() for _ in range(N)]

    # 직접 비교 정렬 구현 (파이썬 내장 정렬 알고리즘 활용)
    # 두 문자열 비교를 위한 클래스 정의
    # 문자열을 받아서 객체 내부에 저장
    class StringComparer:
        def __init__(self, string):
            self.string = string

        def __lt__(self, other):
            # '<' 연산자 구현
            # self는 왼쪽 객체(a), other은 오른쪽 객체(b)를 가리킴
            s1, s2 = self.string, other.string

            # 문자별 비교
            # i는 현재 비교하는 문자의 위치(인덱스)
            # min_len은 두 문자열 중 더 짧은 것의 길이
            i = 0
            min_len = min(len(s1), len(s2))

            while i < min_len:
                # 같은 위치의 문자가 같으면 다음 문자로
                if s1[i] == s2[i]:
                    i += 1
                    continue

                # 다른 문자 발견 시
                #  붙임표 처리
                # s1[i]가 붙임표면, s1은 s2보다 뒤에 와야 함 => s1 < s2는 거짓이므로 False 반환
                # s2[i]가 붙임표면, s1은 s2보다 앞에 와야 함 => s1 < s2는 참이므로 True 반환
                if s1[i] == '-':
                    return False  # s2가 앞선다
                if s2[i] == '-':
                    return True   # s1이 앞선다

                # 알파벳 비교
                if s1[i].lower() != s2[i].lower():
                    # 대소문자 무시했을 때 다른 알파벳이면 알파벳 순서
                    return s1[i].lower() < s2[i].lower()
                else:
                    # 같은 알파벳이지만 대소문자가 다른 경우 대문자가 앞선다
                    if s1[i].isupper() and s2[i].islower():
                        return True
                    if s1[i].islower() and s2[i].isupper():
                        return False
                    # 둘 다 같은 대소문자면 계속 비교
                    i += 1
                    continue

            # 접두사 관계 확인
            return len(s1) < len(s2)

    # 래퍼 클래스를 사용하여 정렬
    sorted_strings = [s.string for s in sorted([StringComparer(s) for s in strings])]

    # 순차적으로 출력
    for s in sorted_strings:
        print(s)

• 두 문자가 다를 때, 먼저 붙임표(-)를 처리
  • s1[i]가 붙임표면, s1은 s2보다 뒤에 와야 함 ( s1 < s2는 거짓이므로 False 반환 )
  • s2[i]가 붙임표면, s1은 s2보다 앞에 와야 함 (s1 < s2는 참이므로 True 반환 )
• 붙임표가 아닌 경우 알파벳 비교
  • 두 문자를 소문자로 변환했을 때 다르면, 알파벳 순서로 비교
  • 두 문자가 같은 알파벳의 다른 대소문자인 경우, 대문자가 앞에 온다
    • s1[i]가 대문자이고 s2[i]가 소문자면 s1이 앞에 와야 함 (True 반환)
    • s1[i]가 소문자이고 s2[i]가 대문자면 s2가 앞에 와야 함 (False 반환)
  • 같은 대소문자라면 다음 문자로 넘어감
• 한 문자열이 다른 문자열의 접두사인 경우
  • 더 짧은 문자열이 앞에 와야 하므로, s1의 길이가 s2보다 짧으면 True, 아니면 False를 반환

# 래퍼 클래스를 사용하여 정렬
sorted_strings = [s.string for s in sorted([StringComparer(s) for s in strings])]

1. [StringComparer(s) for s in strings]: 모든 문자열을 StringComparer 객체로 변환
2. sorted([...]): 변환된 객체들을 정렬 => __lt__ 메서드를 사용하여 객체들을 비교
3. [s.string for s in ...]: 정렬된 객체에서 원래 문자열을 추출

문자열 비교를 위한 클래스를 정의하고, 파이썬의 내장 비교 연산자(<)를 오버라이드하여 문제에서 요구하는 특별한 정렬 규칙을 구현했습니다. 이렇게 하면 functools 모듈이나 다른 외부 의존성 없이도 복잡한 정렬 로직을 구현할 수 있습니다.