백준 BOJ 16439 치킨치킨치킨 문제의 파이썬 python 풀이입니다.

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

문제

N명의 고리 회원들은 치킨을 주문하고자 합니다.

치킨은 총 M가지 종류가 있고 회원마다 특정 치킨의 선호도가 있습니다. 한 사람의 만족도는 시킨 치킨 중에서 선호도가 가장 큰 값으로 결정됩니다. 진수는 회원들의 만족도의 합이 최대가 되도록 치킨을 주문하고자 합니다.

시키는 치킨의 종류가 많아질수록 치킨을 튀기는 데에 걸리는 시간도 길어지기 때문에 최대 세 가지 종류의 치킨만 시키고자 합니다.

진수를 도와 가능한 만족도의 합의 최댓값을 구해주세요.

입력

첫 번째 줄에 고리 회원의 수 N (1 ≤ N ≤ 30) 과 치킨 종류의 수 M (3 ≤ M ≤ 30) 이 주어집니다.

두 번째 줄부터 N개의 줄에 각 회원의 치킨 선호도가 주어집니다.

i+1번째 줄에는 i번째 회원의 선호도가 주어집니다.

출력

첫 번째 줄에 고리 회원들의 만족도의 합의 최댓값을 출력합니다.

접근 : itertools.combinations

정석적인 풀이 방법은 치킨의 종류 M개 중에서 3개를 고르는 조합을 브루트포스로 전부 시도해 보는 것일 겁니다.

• combinations를 활용하면 좋겠습니다.

  
  

itertools.combinations

itertools 모듈의 combinations(iterable, r) 함수는

• 주어진 iterable에서 r개를 뽑는 모든 조합을 만들어 줍니다.
• 순서 상관없이 중복 없이 조합을 만듭니다.
• 반환되는 것은 튜플들의 이터레이터

사용 예시

from itertools import combinations

for comb in combinations(\[1, 2, 3, 4\], 2):  
print(comb)

출력 결과

(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)

• 4개의 원소 중에서 2개씩 뽑는 모든 조합을 출력한 것!

풀이

# 16439 치킨치킨치킨

import sys
from itertools import combinations

input = sys.stdin.readline

n, m = map(int, input().split())

# 선호도 정보 저장
likes = [list(map(int, input().split())) for _ in range(n)]

max_total = 0

# 치킨 종류 중 3개 고르는 모든 조합
for comb in combinations(range(m), 3):
    total = 0
    for i in range(n):
        # 회원 i의 선호도 중 선택된 3개 치킨에 대한 점수 중 최고값
        max_like = max(likes[i][comb[0]], likes[i][comb[1]], likes[i][comb[2]])
        total += max_like
    max_total = max(max_total, total)

print(max_total)

• likes [1] [3]은 2번째 회원이 4번째 치킨에 대해 매긴 선호 점수에 해당할 것
• combinations(range(m), 3) → 치킨 종류 중 3개 고르기
• 회원별로 3개 치킨 중 최고 선호도만 선택해서 총합 계산
• 모든 조합을 시도해서 최대값을 찾음

백준 BOJ 23253 자료구조는 정말 최고야 문제의 파이썬 python 풀이입니다.

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

문제

찬우는 스택을 배운 뒤 자료구조 과목과 사랑에 빠지고 말았다.

자료구조 과목만을 바라보기로 다짐한 찬우는 나머지 과목의 교과서 $N$권을 방 구석에 $M$개의 더미로 아무렇게나 쌓아 두었다. 하지만 중간고사가 다가오자 더 이상 자료구조만 공부할 수는 없었고, 결국 찬우는 팽개쳤던 나머지 과목의 교과서를 정리하고 번호순으로 나열하려 한다.

 N$N$권의 교과서는 각각 $1$부터 $N$까지의 번호가 매겨져 있다. 찬우는 각 더미의 맨 위에 있는 교과서만 꺼낼 수 있으며, 반드시 교과서를 꺼낸 순서대로 나열해야 하기 때문에 번호순으로 나열하기 위해서는 $1$번, $2$번, … $N - 1$번, $N$번 교과서 순으로 꺼내야 한다. 교과서를 올바르게 나열할 수 없다면 중간고사 공부를 때려치겠다는 찬우를 위해 번호순으로 나열할 수 있는지 여부를 알려주는 프로그램을 작성해 주자.

입력

첫째 줄에 교과서의 수 $N$, 교과서 더미의 수 $M$이 주어진다.

둘째 줄부터 $2\times M$줄에 걸쳐 각 더미의 정보가 주어진다.

 $i$번째 더미를 나타내는 첫 번째 줄에는 더미에 쌓인 교과서의 수 $k_{i}$ 가 주어지며, 두 번째 줄에는 $k_{i}$ 개의 정수가 공백으로 구분되어 주어진다.

각 정수는 교과서의 번호를 나타내며, 아래에 있는 교과서의 번호부터 주어진다.

교과서의 번호는 $1$부터 $N$까지의 정수가 한 번씩만 등장한다.

출력

올바른 순서대로 교과서를 꺼낼 수 있다면 Yes를, 불가능하다면 No를 출력한다.

풀이

먼저 시도했던 방법은 교과서 번호를 다 확인하면서 모든 더미를 순회하는 방식이었습니다.

시간 초과

# 23253 자료구조는 정말 최고야

import sys

# 교과서의 수 n, 교과서 더미의 수 m
n, m = map(int, sys.stdin.readline().split())

books = []

for _ in range(m):
    # 더미에 쌓인 교과서 수 k
    k = int(sys.stdin.readline())
    books.append(list(map(int, sys.stdin.readline().split())))

i = 1
while i <= n:
    for book in books:
        if book and book[-1] == i:
            i += 1
            book.pop()
            break

    else:
        print("No")
        exit()

print("Yes")

• 교과서 번호 1 ~ N까지 순서대로 하나씩 확인하는 것을, 매번 M개의 더미 모두 순회하기 때문에 최악의 경우 O(N * M) 시간 복잡도가 발생합니다.

스택 특성, top 활용

모든 스택이 내림차순으로만 쌓여 있어야 전체적으로 순서대로 꺼낼 수 있습니다.
즉, 각 스택에서 book[i] > book[i+1] 이어야 합니다.

# 23253 자료구조는 정말 최고야

import sys

n, m = map(int, sys.stdin.readline().split())

for _ in range(m):
    k = int(sys.stdin.readline())
    stack = list(map(int, sys.stdin.readline().split()))
    # 위에서부터 아래로 검사 (책 쌓인 순서대로)
    for i in range(k - 1):
        if stack[i] < stack[i + 1]:
            print("No")
            exit()

print("Yes")

• 스택 특성상 위에서부터 꺼내기 때문에, 스택 내부는 반드시 내림차순이어야만 전체적으로 1 → N 순서대로 뺄 수 있습니다
• 이 조건만 만족하면 순서대로 뽑는 것이 항상 가능하므로, 모든 스택이 내림차순인지 확인만 하면 됨!
• 이렇게 하면 스택 하나당 O(k) 검사만 하면 되기 때문에 전체 시간 복잡도는 O(N) (k₁ + k₂ + ... + kₘ = N)

리트코드 LeetCode 46 Permutations 문제의 파이썬 python 풀이입니다.

https://leetcode.com/problems/permutations/

문제

2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라.

풀이

DFS를 활용한 정석적인 풀이 방법과, 파이썬 itertools 모듈을 사용한 편리한 풀이 방법 두 가지를 작성했습니다.

1. DFS를 활용한 순열 생성

# 순열 : DFS

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        result = [] # 최종 순열 결과를 저장하는 리스트
        prev_elements = [] # 지금까지 선택한 숫자들을 저장 (경로)

        def dfs(elements): # 현재 사용할 수 있는 숫자들(elements)를 입력으로 받음
            # 더 이상 선택할 수 없는 숫자가 없는 리프 노드일 때 -> 하나의 순열이 완성된 것
            if len(elements) == 0:
                result.append(prev_elements[:]) # 현재까지 선택된 숫자 경로(prev_elements)를 복사하여 결과에 추가

            # 순열 생성 재귀 호출
            for e in elements:
                next_elements = elements[:]
                next_elements.remove(e)

                prev_elements.append(e)

                dfs(next_elements)

                prev_elements.pop()

        dfs(nums)

        return result

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

• permute 함수는 nums라는 정수 리스트를 받아서, 가능한 모든 순열을 리스트 형태로 반환합니다.
• 예: nums = [1, 2, 3] → 결과는 [[1,2,3],[1,3,2],[2,1,3],...[3,2,1]]

DFS 재귀 호출

for e in elements:
    next_elements = elements[:]
    next_elements.remove(e)

    prev_elements.append(e)
    dfs(next_elements)
    prev_elements.pop()

• 현재 선택할 수 있는 숫자들 중 하나(e)를 고릅니다.
• e를 선택한 후엔 더 이상 해당 숫자를 선택할 수 없으므로 elements에서 제거한 새 리스트(next_elements)를 만듭니다.
• 그 숫자를 현재 경로(prev_elements)에 추가하고 나머지 숫자들을 대상으로 DFS를 재귀적으로 실행합니다.
• 재귀 호출 이후에는 prev_elements에서 마지막에 추가한 숫자를 제거하여 백트래킹합니다.

진행 과정

입력: nums = [1, 2, 3]

dfs([1, 2, 3])
 └─ 1 선택 → prev = [1], elements = [2, 3]
     └─ 2 선택 → prev = [1, 2], elements = [3]
         └─ 3 선택 → prev = [1, 2, 3], elements = []
             └─ 저장! [1, 2, 3]
         ← 3 제거 → prev = [1, 2]
     ← 2 제거 → prev = [1]
     └─ 3 선택 → prev = [1, 3], elements = [2]
         └─ 2 선택 → prev = [1, 3, 2], elements = []
             └─ 저장! [1, 3, 2]
         ← 2 제거 → prev = [1, 3]
     ← 3 제거 → prev = [1]
 ← 1 제거 → prev = []

 └─ 2 선택 → prev = [2], elements = [1, 3]
     └─ 1 선택 → prev = [2, 1], elements = [3]
         └─ 3 선택 → prev = [2, 1, 3], elements = []
             └─ 저장! [2, 1, 3]
         ← 3 제거
     ← 1 제거
     └─ 3 선택 → prev = [2, 3], elements = [1]
         └─ 1 선택 → prev = [2, 3, 1], elements = []
             └─ 저장! [2, 3, 1]
         ← 1 제거
     ← 3 제거
 ← 2 제거

 └─ 3 선택 → prev = [3], elements = [1, 2]
     └─ 1 선택 → prev = [3, 1], elements = [2]
         └─ 2 선택 → prev = [3, 1, 2], elements = []
             └─ 저장! [3, 1, 2]
         ← 2 제거
     ← 1 제거
     └─ 2 선택 → prev = [3, 2], elements = [1]
         └─ 1 선택 → prev = [3, 2, 1], elements = []
             └─ 저장! [3, 2, 1]
         ← 1 제거
     ← 2 제거
 ← 3 제거

• prev_elements: 지금까지의 선택 경로를 저장하는 리스트
• elements: 현재 선택 가능한 후보 숫자들
• dfs는 한 단계 깊이 들어가며 한 숫자를 고르고, 그 숫자를 후보에서 제거
• 숫자를 다 골라서 elements == []가 되면 → 하나의 완성된 순열이므로 저장
• 그런 다음 prev_elements.pop()을 통해 방금 선택한 숫자를 되돌리고, 다음 후보를 탐색

이 코드는 백트래킹 기법을 사용하여 nums의 모든 순열을 구합니다.

재귀 호출을 통해 하나씩 선택하고, 선택이 완료되면 결과에 저장하며, 선택을 되돌리며(백트래킹) 다른 경우의 수를 시도합니다.

시간복잡도는 O(n!)입니다. 가능한 모든 순열을 생성해야 하므로, n개의 숫자에 대해 n!개의 경우의 수가 생깁니다.

2. itertools 모듈 사용

파이썬에는 itertools라는 모듈이 있습니다. itertools 모듈은 반복자 생성에 최적화된 효율적인 기능들을 제공하므로, 실무에서는 알고리즘으로 직접 구현하기보다는 가능하다면 itertools 모듈을 사용하는 편이 낫겠습니다.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(map(list, itertools.permutations(nums)))

itertools.permutations() 함수의 결과물은 리스트 내 튜플입니다. 리트코드 문제에서는 리스트를 반환하도록 요구하기 떄문에, 리스트로 map 해주는 과정을 추가했습니다.

리트코드 LeetCode 17 Letter Combinations of a Phone Number 문제의 파이썬 python 풀이입니다.

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

문제

2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라.

풀이

# 폰 번호 문자 조합 : 모든 조합 탐색 (DFS)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:

        def dfs(index, path):
            # 끝까지 탐색하면 백트래킹
            if len(path) == len(digits):
                result.append(path)
                return

            # 입력값 자릿수 단위 반복
            for i in range(index, len(digits)):
                # 숫자에 해당하는 모든 문자열 반복
                for j in dic[digits[i]]:
                    dfs(i+1, path+j) #path에 digits[i]을 더해서 가져감

        # 예외 처리
        if not digits: # 아무것도 없을 때
            return []

        dic = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
               "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}

        result = []

        dfs(0, "")

        return result

def dfs(index, path):

• index: 현재 몇 번째 숫자를 처리 중인지 나타냄
• path: 지금까지 조합한 문자들을 저장하는 문자열
  예를 들어, '2' → abc, '3' → def이면
  • 첫 번째 단계에서 'a'를 선택 → path = 'a'
  • 두 번째 단계에서 'd'를 선택 → path = 'ad'
  • 끝까지 조합이 완료되면 → result.append('ad')

즉, path는 현재 만들고 있는 조합 중간 결과입니다.

예시

입력: digits = "23"
딕셔너리:

dic = {"2": "abc", "3": "def"}

DFS 흐름

dfs(0, ""):
  ├─ dfs(1, "a"):
  │   ├─ dfs(2, "ad") → 끝 → 저장
  │   ├─ dfs(2, "ae") → 끝 → 저장
  │   └─ dfs(2, "af") → 끝 → 저장
  ├─ dfs(1, "b"):
  │   ├─ dfs(2, "bd") → 끝 → 저장
  │   ├─ dfs(2, "be") → 끝 → 저장
  │   └─ dfs(2, "bf") → 끝 → 저장
  ├─ dfs(1, "c"):
      ├─ dfs(2, "cd") → 끝 → 저장
      ├─ dfs(2, "ce") → 끝 → 저장
      └─ dfs(2, "cf") → 끝 → 저장

재귀 호출을 하면서 이 문자열을 점점 길게 만들어 가다가, digits 길이와 같아지면 결과에 저장합니다.

백준 BOJ 16961 탭 vs 공백 문제의 파이썬 python 풀이입니다.

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

문제

큐브러버가 운영하는 호텔은 1년 스케줄을 전년도에 미리 정해놓는다. 또, 이 호텔에는 코딩을 할 줄 아는 사람만 투숙할 수 있다. 코딩을 할 때 들여쓰기는 필수이다. 호텔에는 두 종류의 사람이 투숙하는데, 들여쓰기로 탭을 사용하는 사람과 공백을 사용하는 사람이다. 편의를 위해 각각 "탭파"와 "공백파"로 부르도록 하자.

올해는 윤년이기 때문에, 총 366일로 이루어져 있다. 편의상 날짜는 1일-366일로 표시한다.

큐브러버의 호텔에 예약을 한 사람의 수는 N명이고, 각 사람이 투숙 시작일과 종료일을 모두 알고 있다. 모든 사람은 투숙 시작일의 오전 9시에 호텔에 투숙하고, 투숙 종료일의 오후 6시에 호텔에서 나간다. 이 호텔에는 모든 것이 있기 때문에, 호텔 투숙객은 호텔을 벗어나지 않는다.

탭파와 공백파가 만나면 싸운다. 하지만, 탭파와 공백파의 수가 일치하는 날에는 균형이 잡혀서 싸움이 일어나지 않는다. 탭파가 한 명도 없거나 공백파가 한 명도 없으면 호텔 관리자들끼리 왜 호텔 운영을 이런 식으로 하냐며 서로 책임을 돌리면서 싸운다.

호텔 예약 정보가 주어졌을 때, 여러가지 정보를 구해보려고 한다.

입력

첫째 줄에 예약을 한 사람의 수 N(1 ≤ N ≤ 5,000)이 주어진다. 둘째 줄부터 호텔 예약 정보가 한 줄에 하나씩 주어진다.

호텔 예약 정보는 문자 c와 정수 s, e로 이루어져 있다. c가 'T'인 경우는 탭파, 'S'인 경우는 공백파이다. s는 투숙 시작일, e는 투숙 종료일이다. (1 ≤ s ≤ e ≤ 366)

출력

다음 정보를 한 줄에 하나씩 출력한다.

1. 투숙객이 1명 이상인 날의 수
2. 가장 많은 투숙객이 있었던 날에 투숙한 사람의 수
3. 싸움이 없는 날의 수
4. 싸움이 없는 날 중 가장 많은 투숙객이 있었던 날에 투숙한 사람의 수. 싸움이 없는 날이 없으면 0을 출력한다.
5. 가장 오랜 기간 투숙한 사람이 투숙한 날의 수

풀이

# 16961 탭 vs 공백

import sys

n = int(sys.stdin.readline().strip()) # 예약한 사람의 수

# 각 날짜별 탭파와 공백파의 수를 기록할 배열 (1일부터 366일까지)
tab = [0] * 367
space = [0] * 367

# 투숙 기간 기록
max_stay = 0

# 모든 예약 정보 처리
for _ in range(n):
    c, s, e = input().split()
    s, e = int(s), int(e)

    # 가장 오랜 기간 투숙한 사람 업데이트
    max_stay = max(max_stay, e - s + 1)

    # 해당 손님의 투숙 날짜 기록
    if c == 'T':  # 탭파
        for day in range(s, e + 1):
            tab[day] += 1

    else:  # 공백파
        for day in range(s, e + 1):
            space[day] += 1

# 결과 계산
one_over = 0    # 투숙객이 1명 이상인 날의 수
max_guests = 0          # 가장 많은 투숙객이 있었던 날의 투숙객 수
no_fight = 0       # 싸움이 없는 날의 수
no_fight_max = 0 # 싸움이 없는 날 중 가장 많은 투숙객이 있었던 날의 투숙객 수

for day in range(1, 367):
    total_guests = tab[day] + space[day]

    # 투숙객이 있는 날 카운트
    if total_guests > 0:
        one_over += 1

    # 최대 투숙객 수 업데이트
    if total_guests > max_guests:
        max_guests = total_guests

    # 싸움이 없는 날 체크 (탭파 == 공백파 && 둘 다 0이 아닌 경우)
    if (tab[day] == space[day]) and (tab[day] > 0):
        no_fight += 1

        # 싸움이 없는 날 중 최대 투숙객 수 업데이트
        if total_guests > no_fight_max:
            no_fight_max = total_guests

# 결과 출력
print(one_over)
print(max_guests)
print(no_fight)
print(no_fight_max)
print(max_stay)

• 입력 처리
  • 예약한 사람의 수 N을 입력
  • 각 예약 정보(탭파/공백파, 투숙 시작일, 종료일)를 입력
• 날짜별 투숙객 추적
  • 1일부터 366일까지 각 날짜별로 탭파와 공백파의 수를 기록
  • 각 예약마다 투숙 시작일부터 종료일까지 해당 유형의 손님 수를 증가시킴
• 통계 계산
  • 투숙객이 1명 이상인 날의 수를 계산
  • 가장 많은 투숙객이 있었던 날의 투숙객 수를 찾음
  • 싸움이 없는 날(탭파와 공백파의 수가 동일하고 둘 다 0이 아닌 경우)의 수를 계산
  • 싸움이 없는 날 중 가장 많은 투숙객이 있었던 날의 투숙객 수를 찾음
  • 가장 오랜 기간 투숙한 사람의 투숙 일수를 계산

백준 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 모듈이나 다른 외부 의존성 없이도 복잡한 정렬 로직을 구현할 수 있습니다.