공부블로그

TODAY TIL

🔍 문제 소개

이번 포스팅에서는 배열에서 K번째 수를 찾는 문제를 다룹니다. 이 문제는 정렬 알고리즘의 기초를 연습하기에 적합하며, 간단한 구현으로도 해결할 수 있는 문제입니다. 문제를 이해하고, 순서대로 해결 방법과 코드를 공유하겠습니다!

📝 문제 설명

문제

• 크기가 N인 배열 A가 주어집니다.
• 배열 A를 오름차순으로 정렬했을 때, 앞에서부터 K번째 수를 출력하세요.

입력 조건

1. 첫 번째 줄: 정수 N과 K
   • 1 ≤ N ≤ 5,000,000, 1 ≤ K ≤ N
2. 두 번째 줄: 배열 A의 원소들
   • -10⁹ ≤ Aᵢ ≤ 10⁹

출력 조건

• 배열을 정렬했을 때 앞에서부터 K번째 수를 출력합니다.

💡 풀이 방법

이 문제는 크게 3단계로 해결할 수 있습니다:

1. 배열 입력받기
2. 오름차순 정렬하기
3. K번째 수 추출하기

🛠️ 코드 구현

Python을 사용하여 문제를 해결하는 코드는 다음과 같습니다:

# 입력 받기
import sys
input = sys.stdin.read
data = input().split()

# N: 배열의 길이, K: 찾고자 하는 위치
N, K = int(data[0]), int(data[1])
A = list(map(int, data[2:]))

# 배열을 정렬
A.sort()

# K번째 수 출력 (1-based index이므로 K-1 사용)
print(A[K - 1])

🔎 코드 설명

1️⃣ 입력 받기

• Python의 sys.stdin.read를 사용해 입력 데이터를 한 번에 받습니다.
• 첫 번째 줄에서 N(배열 길이)과 K(찾고자 하는 위치)를 가져옵니다.
• 두 번째 줄에서 배열 A를 리스트로 변환합니다.

2️⃣ 배열 정렬

• 배열 A를 sort() 메서드를 사용해 오름차순 정렬합니다.
  Python의 sort()는 Timsort 알고리즘을 기반으로 작동하며, 시간 복잡도는 **O(N log N)**입니다.

3️⃣ K번째 수 추출

• 배열은 0부터 시작하는 0-based index입니다. 따라서 K번째 수를 찾으려면 A[K-1]을 사용합니다.

🧩 예제 풀이

예제 입력

5 2
4 1 3 2 5

풀이 과정

1. 배열의 길이 N = 5, K번째 위치 K = 2
   배열 A = [4, 1, 3, 2, 5]
2. 배열 정렬:

A.sort() → [1, 2, 3, 4, 5]

3. K번째 수 추출:

A[K-1] = A[1] = 2

4. 출력 결과:

2

⏱️ 시간 복잡도 분석

1. 배열 정렬: 정렬의 시간 복잡도는 O(N log N)
2. K번째 수 추출: 상수 시간 O(1)

따라서 전체 시간 복잡도는 **O(N log N)**입니다.

📌 추가 팁: 더 효율적인 방법은 없을까?

만약 배열이 매우 커서 메모리나 시간 효율이 중요하다면, Quickselect 알고리즘을 사용해 K번째 수를 찾을 수 있습니다. Quickselect는 평균적으로 **O(N)**의 시간 복잡도로 실행됩니다. 그러나 이 문제에서는 Python의 내장 정렬을 사용하는 것이 가장 간단하고 안정적인 방법입니다.

✅ 마무리

배열에서 K번째 수를 찾는 문제는 정렬 알고리즘과 리스트 활용법을 연습할 수 있는 좋은 문제입니다. 이번 포스팅에서는 Python의 기본 정렬 메서드인 sort()를 사용하여 문제를 간단히 해결했지만, 다른 알고리즘을 적용해보는 것도 추천합니다!

TODAY TIL

다솜이는 사람의 마음을 읽는 기계를 이용해 국회의원 선거에서 자신을 찍지 않을 사람들을 매수하려고 합니다. 목표는 다른 후보들의 득표수를 초과하는 것입니다. 이 글에서는 다솜이가 최소 몇 명을 매수해야 당선될 수 있는지를 계산하는 방법을 설명합니다.

문제 설명

1. 입력 조건:
   • 후보 수 NNN이 주어집니다.
   • 각 후보의 득표수가 순서대로 입력됩니다.
   • 기호 1번 후보가 다솜이입니다.
2. 출력 조건:
   • 다솜이가 매수해야 하는 사람의 최소 수를 출력합니다.
3. 제약 조건:
   • 후보 수 NNN: 최대 50
   • 각 후보의 득표수: 최대 100
4. 예제 입력/출력

입력:

3
5
7
7

출력:

2

해결 방법

문제를 해결하기 위해 다음과 같은 단계로 접근합니다:

1. 입력 데이터를 읽기:
   • 후보 수와 각 후보의 득표수를 리스트로 저장합니다.
   • 다솜이의 득표수는 따로 저장하고, 나머지 후보들의 득표수를 관리합니다.
2. 매수 작업 반복:
   • 다른 후보들의 득표수를 내림차순으로 정렬합니다.
   • 가장 많은 득표수를 가진 후보를 매수하여 다솜이의 득표수를 증가시킵니다.
   • 다솜이의 득표수가 다른 모든 후보보다 많아질 때까지 이 작업을 반복합니다.
3. 매수 횟수 계산:
   • 매수 횟수를 카운트하면서, 다솜이의 득표수가 다른 후보들보다 많아질 때 결과를 출력합니다.

Python 코드

# 입력받기
N = int(input())  # 후보 수
votes = [int(input()) for _ in range(N)]  # 각 후보의 득표수

# 초기 설정
dasom_votes = votes[0]  # 다솜이의 득표수
other_votes = votes[1:]  # 다른 후보들의 득표수
bribes = 0  # 매수한 사람 수

# 매수 작업
while other_votes and max(other_votes) >= dasom_votes:
    # 가장 많은 득표수를 가진 후보의 표를 매수
    max_index = other_votes.index(max(other_votes))  # 최대값의 인덱스 찾기
    other_votes[max_index] -= 1  # 표 매수 (1 감소)
    dasom_votes += 1  # 다솜이의 표 증가
    bribes += 1  # 매수 횟수 증가

# 결과 출력
print(bribes)

코드 설명

1. 입력 처리:
   • 후보 수 NNN과 각 후보의 득표수를 입력받아 리스트로 저장합니다.
   • 다솜이의 득표수는 dasom_votes에, 나머지 후보들의 득표수는 other_votes 리스트로 관리합니다.
2. 매수 작업:
   • while 루프를 통해 다솜이의 득표수가 다른 후보들의 최대 득표수를 초과할 때까지 반복합니다.
   • 가장 많은 득표수를 가진 후보의 표를 하나 매수하고, 다솜이의 득표수를 증가시킵니다.
3. 결과 출력:
   • 매수 횟수는 bribes 변수에 저장되며, 반복이 끝나면 최솟값이 출력됩니다.

예제 실행

입력

3
5
7
7

출력

2

추가 설명

이 코드의 핵심은 다솜이의 득표수가 다른 후보들보다 많아질 때까지 반복적으로 매수하는 것입니다. 가장 득표수가 많은 후보를 우선 매수하는 전략을 사용하여 최솟값을 계산합니다.

최적화 고려사항

• 후보 수 NNN이 최대 50이므로, 매수 작업의 복잡도는 적절한 수준입니다.
• max\text{max}max 연산을 사용하는 만큼, 리스트 길이에 따라 작업 시간이 영향을 받을 수 있습니다.

마무리

이 문제는 그리디 알고리즘을 활용하여 반복적으로 최대값을 줄이는 전략을 사용합니다. 매수 전략을 효율적으로 구현하여 다솜이가 국회의원에 당선되도록 만드는 과정을 함께 배웠습니다.

코드와 예제 실행 결과를 참고하여 자신만의 해결 방법을 구현해 보세요! 😊

TODAY TIL

안녕하세요! 이번 블로그 포스팅에서는 학교 식당 줄 서기 문제를 해결하는 파이썬 코드와 문제 해결 과정을 공유해보려고 합니다. 이 문제는 많은 학생들이 식당에서 줄을 서고, 식사가 준비되는 과정을 처리하면서 최대 대기 인원을 기록하는 문제입니다. 특히, 입력의 개수가 많기 때문에 효율적인 구현이 필요합니다. 함께 문제를 이해하고 해결해봅시다!

문제 설명

학생들이 학교 식당에 도착하고, 식사가 준비되는 총 n개의 정보가 주어집니다. 이 정보는 두 가지 유형으로 이루어져 있습니다:

1. 학생 도착 (유형 1 a): 학생 번호 a가 식당에 도착하여 줄을 섭니다.
2. 식사 준비 (유형 2): 줄의 맨 앞 학생이 식사를 시작합니다.

식당에 도착한 학생은 줄의 맨 뒤에 서게 되며, 식사가 준비되면 줄의 맨 앞에 있는 학생이 식사를 하러 들어갑니다. 우리는 이 과정에서 줄에 서 있는 학생 수가 최대가 되었을 때, 그 순간 줄의 맨 뒤에 있는 학생 번호를 출력해야 합니다.

문제 해결 접근법

이 문제를 해결하기 위해 다음과 같은 접근 방식을 사용했습니다:

• 큐(Queue) 자료구조를 활용해 학생들이 줄을 서고, 식사를 하러 들어가는 과정을 구현합니다. deque 모듈을 사용하면 큐의 양쪽에서 삽입과 삭제가 빠르게 이루어지므로 적합합니다.
• 최대 대기 인원과 그 순간의 줄 맨 뒤 학생 번호를 추적하여 결과를 계산합니다.

코드 구현

아래는 문제를 해결하기 위한 파이썬 코드입니다:

from collections import deque
import sys

n = int(input())
queue = deque()
max_wait = 0
last_student = 100001

for _ in range(n):
    action = sys.stdin.readline().strip()
    if action[0] == '1':  # 학생 도착 (유형 1)
        _, student_number = action.split()
        student_number = int(student_number)
        queue.append(student_number)

        if len(queue) > max_wait:
            max_wait = len(queue)
            last_student = queue[-1]
        elif len(queue) == max_wait:
            if queue[-1] < last_student:
                last_student = queue[-1]

    elif action[0] == '2' and queue:  # 식사 준비 (유형 2)
        queue.popleft()

if max_wait == 0:
    last_student = -1

코드 설명

1. 입력 처리 및 초기화
   • n은 총 명령어의 개수를 의미합니다.
   • queue는 학생들이 줄을 서는 대기열을 나타내며, deque()로 초기화됩니다.
   • max_wait는 대기 중인 최대 학생 수를 저장하며, last_student는 그때 줄의 맨 뒤에 있는 학생 번호를 기록합니다.
2. 학생 도착 처리 (유형 1)
   • 학생 번호가 주어지면 해당 번호를 큐의 맨 뒤에 추가합니다.
   • 대기열 길이가 max_wait보다 크다면 이를 갱신하고, last_student를 현재 줄의 맨 뒤 학생 번호로 업데이트합니다.
   • 만약 대기열 길이가 max_wait와 같다면, 줄의 맨 뒤 학생 번호가 더 작은 경우로 갱신합니다.
3. 식사 준비 처리 (유형 2)
   • 식사가 준비되면 큐의 맨 앞에 있는 학생을 제거합니다.
4. 결과 계산
   • 만약 최대 대기 인원이 0이라면, 대기 중인 학생이 없다는 의미로 last_student를 -1로 설정합니다.

문제 해결의 어려움과 해결 방법

이 문제는 주어진 입력의 개수가 최대 100,000개일 수 있기 때문에 효율적인 입력 처리와 큐의 사용이 필수적입니다. sys.stdin.readline()을 사용하여 입력을 빠르게 처리하고, deque를 활용하여 큐 연산을 효율적으로 구현함으로써 런타임 에러를 피할 수 있었습니다.

마무리

이번 포스팅에서는 학생들이 식당에서 줄을 서는 문제를 해결하는 파이썬 코드를 다뤄보았습니다. 큐 자료구조를 사용해 효율적으로 줄 서기와 식사 과정을 처리하고, 최대 대기 인원과 그때의 학생 번호를 찾는 과정에서 발생할 수 있는 여러 가지 상황들을 고려했습니다. 이 코드가 여러분의 이해에 도움이 되었기를 바랍니다!

TODAY TIL

안녕하세요! 오늘은 게임 내에서 연계 기술의 발동 조건을 다루는 흥미로운 문제를 풀어볼 거예요. 임스가 플레이 중인 게임에서는 몇 가지 규칙에 따라 기술이 발동됩니다:

• 연계 기술은 사전 기술과 본 기술의 조합입니다.
• 사전 기술 없이 본 기술을 사용하면 기술이 비정상적으로 발동됩니다.
• 사전 기술은 L, S, 본 기술은 R, K입니다.
• 숫자 1부터 9까지의 기술은 언제나 단독으로 발동할 수 있습니다.

예를 들어, L을 사용한 후에 R을 사용하면 정상 발동되지만, R만 있으면 발동되지 않아요.

문제 해결 아이디어

이 문제를 해결하려면, 사전 기술이 사용되었는지 확인하면서 본 기술이 발동될 수 있는지를 검토하면 됩니다.

주요 아이디어

• 사전 기술(L, S)이 나오면 리스트에 저장해두고, 본 기술(R, K)이 나올 때 이 리스트를 확인해 발동 여부를 결정합니다.
• 숫자 기술(1~9)은 특별한 조건 없이 바로 발동할 수 있습니다.

코드 설명

# 기술의 개수 입력받기 (사용하지 않지만 문제의 형식에 맞추어 필요)
N = int(input())  

# 기술 순서를 문자열로 입력받고 리스트로 변환
skill = list(str(input()))

# 정상적으로 발동된 기술의 개수를 세는 변수
num = 0

# 사용된 사전 기술을 추적하는 리스트
used_list = []

# 기술을 하나씩 확인하며 발동 여부 판단
for i in skill:
    # 사전 기술 'L' 또는 'S'가 나오면 used_list에 추가
    if i == 'L' or i == 'S':
        used_list.append(i)
    
    # 본 기술 'K'가 나왔을 때
    elif i == 'K':
        # 사전 기술 'S'가 있다면 발동 가능
        if 'S' in used_list:
            used_list.remove('S')  # 사용한 'S'는 리스트에서 제거
            num += 1  # 발동된 기술 수 증가
        else:
            break  # 사전 기술 없으면 반복 종료 (스크립트 꼬임)
    
    # 본 기술 'R'이 나왔을 때
    elif i == 'R':
        # 사전 기술 'L'이 있다면 발동 가능
        if 'L' in used_list:
            used_list.remove('L')  # 사용한 'L'은 리스트에서 제거
            num += 1  # 발동된 기술 수 증가
        else:
            break  # 사전 기술 없으면 반복 종료 (스크립트 꼬임)
    
    # 숫자 기술 '1'~'9'는 조건 없이 발동 가능
    else:
        num += 1

# 최종 발동된 기술의 개수 출력
print(num)

설명

• L이 나오면 사전 기술로 저장됩니다.
• 1은 사전 기술이 필요 없는 숫자 기술이므로 바로 발동됩니다.
• S가 나오면 사전 기술로 저장됩니다.
• 2도 숫자 기술이라 바로 발동됩니다.
• R이 나오면 L이 사전 기술로 사용되었으므로 발동됩니다.
• K도 S가 사용된 상태이므로 발동됩니다.

발동된 기술은 총 4개입니다.

결론

이 문제는 리스트를 사용해 사전 기술의 사용 상태를 관리하면서 본 기술 발동 여부를 체크하는 방식으로 해결할 수 있었습니다. 코드의 각 부분을 이해하고, 예제를 실행해보며 학습하면 확실히 이해할 수 있을 거예요!

TODAY TIL

안녕하세요! 오늘은 n개의 숫자가 적힌 카드를 이용해 특정 규칙에 따라 카드를 처리하는 Python 코드에 대해 설명해드리겠습니다. 이 코드는 카드 게임의 시뮬레이션으로, 주어진 카드가 한 장 남을 때까지의 과정을 출력합니다.

문제 설명

사용자는 n개의 카드(숫자 1부터 n까지)를 갖고 있으며, 다음의 규칙을 반복해서 카드가 한 장 남을 때까지 진행합니다:

1. 제일 위에 있는 카드를 버립니다.
2. 그다음 제일 위에 있는 카드를 제일 아래로 옮깁니다.

코드 설명

n = int(input())
card = [i for i in range(1, n + 1)]
discard = []

while len(card) != 1:
    discard.append(card.pop(0)) # 제일 위에 있는 카드를 버린다.
    card.append(card.pop(0))    # 제일 위에 있는 카드를 제일 아래로 옮긴다.

for c in discard:
    print(c, end=' ')
print(card[0])

코드 단계별 분석

1. 입력받기: n은 카드의 개수를 나타내며, 사용자가 입력합니다.
2. 카드 리스트 생성: card는 1부터 n까지의 숫자가 순서대로 저장된 리스트입니다. 예를 들어, n=7일 경우 card = [1, 2, 3, 4, 5, 6, 7]입니다.
3. 버려진 카드 리스트 초기화: discard는 게임 중 버려진 카드를 저장하기 위한 빈 리스트입니다.
4. 메인 로직:
   • while len(card) != 1: 조건을 만족할 때까지 반복합니다.
   • discard.append(card.pop(0)): 카드의 맨 위에 있는 카드를 discard에 추가합니다.
   • card.append(card.pop(0)): 카드의 맨 위에 있는 카드를 제거하고, 이를 카드 리스트의 맨 아래로 보냅니다.
5. 출력:
   • discard 리스트의 내용을 순서대로 출력합니다.
   • 마지막으로 남은 한 장의 카드를 출력합니다.

동작 예시

입력: n = 7

초기 상태:

• card = [1, 2, 3, 4, 5, 6, 7]
• discard = []

게임 과정:

1. discard = [1], card = [3, 4, 5, 6, 7, 2]
2. discard = [1, 3], card = [5, 6, 7, 2, 4]
3. discard = [1, 3, 5], card = [7, 2, 4, 6]
4. discard = [1, 3, 5, 7], card = [4, 6, 2]
5. discard = [1, 3, 5, 7, 4], card = [2, 6]
6. discard = [1, 3, 5, 7, 4, 2], card = [6]

출력:

1 3 5 7 4 2
6

결과 해석: 버려진 카드의 순서를 출력한 후, 마지막으로 남은 카드를 출력합니다.

이 코드의 핵심은 리스트의 pop(0) 메서드와 append() 메서드를 사용하여 카드의 순서를 처리하는 것입니다. 이를 통해 카드 게임의 규칙을 간단하게 구현할 수 있습니다.

결론

이 코드 예제는 Python의 리스트 메서드를 활용하여 간단한 카드 게임을 시뮬레이션하는 방법을 잘 보여줍니다. 다양한 카드 처리 문제에 응용할 수 있는 좋은 연습이 될 것입니다.

다음에도 재미있는 코드 설명으로 찾아오겠습니다. 읽어주셔서 감사합니다!

TODAY TIL

안녕하세요! 이번 포스팅에서는 폰켓몬 선택과 관련된 흥미로운 코딩 문제를 다뤄보겠습니다. 단계적으로 설명하고 코드 구현을 공유합니다.

문제 설명

여러분은 오랜 여행 끝에 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 여러분에게 연구실에 있는 N마리의 폰켓몬 중 N/2마리를 선택해도 좋다고 했습니다. 같은 종류의 폰켓몬은 같은 번호를 가지며, 여러분은 최대한 다양한 종류의 폰켓몬을 선택하고 싶습니다.

문제의 목표: N마리의 폰켓몬 중 최대 N/2마리를 선택할 때, 가장 다양한 종류의 폰켓몬을 선택하는 경우를 찾고, 그때의 폰켓몬 종류의 수를 반환하는 것입니다.

제한사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• N은 항상 짝수이며, 1 이상 10,000 이하의 자연수입니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수입니다.

단계별 해결 방법

1. 입력 분석:
   • nums 배열에는 각 폰켓몬의 종류 번호가 포함되어 있습니다.
   • 배열의 길이 N은 항상 짝수입니다. 따라서 N/2마리의 폰켓몬을 선택할 수 있습니다.
2. 중복 제거:
   • set 자료형을 사용하여 배열에서 중복을 제거하고 고유한 폰켓몬 종류의 수를 구합니다.
3. 최대 선택 가능한 폰켓몬 수 계산:
   • 선택할 수 있는 최대 종류의 개수는 min(len(unique_pokemon), N // 2)입니다.
     • len(unique_pokemon)은 중복 제거 후 고유한 종류의 개수입니다.
     • N // 2는 선택할 수 있는 폰켓몬의 총 수입니다.
4. 코드 구현

def solution(nums):
    # 중복 제거 후 고유한 폰켓몬 종류의 수 계산
    unique_pokemon = set(nums)
    
    # 선택할 수 있는 폰켓몬 종류의 최댓값 계산
    return min(len(unique_pokemon), len(nums) // 2)

코드 설명

• set(nums)를 사용하여 nums 배열에서 중복된 종류 번호를 제거합니다.
• min(len(unique_pokemon), len(nums) // 2)를 사용해 선택할 수 있는 폰켓몬 종류의 최대 개수를 계산합니다.
  • 고유한 폰켓몬 종류의 수(len(unique_pokemon))가 선택 가능한 수(N/2)보다 작으면 모든 고유 종류를 선택할 수 있습니다.
  • 고유한 폰켓몬 종류의 수가 N/2보다 크다면 N/2만큼의 고유 종류만 선택할 수 있습니다.

예제

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

1. set(nums) 결과: {1, 2, 3} (고유한 폰켓몬 종류: 3개)
2. 선택할 수 있는 최대 개수: len(nums) // 2 = 2
3. 반환값: min(3, 2) = 2

결과: 최대 2종류의 폰켓몬을 선택할 수 있습니다.

결론

이 문제는 배열에서 중복된 항목을 제거하고 선택할 수 있는 폰켓몬의 종류를 비교하는 간단한 문제였습니다. 중복 제거를 위한 set 사용과 최소값 계산을 통해 다양한 경우를 쉽게 처리할 수 있었습니다.

이제 여러분도 다양한 알고리즘 문제를 해결할 때 중복 제거와 최소값 계산을 활용해 보세요!

TODAY TIL

안녕하세요! 이번 포스팅에서는 전주 듣고 노래 맞히기」 프로그램 와 관련된 흥미로운 코딩 문제를 다뤄보겠습니다. 첫 세 음만으로 노래 제목을 맞히는 프로그램을 단계적으로 설명하고 코드 구현을 공유합니다.

문제 설명

정환이 알고 있는 노래는 총 NNN개이고, 각각의 노래는 제목과 일곱 개의 음으로 이루어진 전주를 가지고 있습니다. 정환은 이 전주의 첫 세 음을 듣고 제목을 맞히려고 합니다.

요구사항

1. 주어진 첫 세 음에 맞는 노래가 딱 하나 있다면 해당 제목을 출력합니다.
2. 같은 첫 세 음으로 시작하는 노래가 여러 개면 ?를 출력합니다.
3. 해당하는 노래가 전혀 없다면 !를 출력합니다.

입력 및 출력 형식

• 첫 줄에는 정환이 알고 있는 노래의 개수 NNN과 맞히기를 시도할 노래의 개수 MMM이 주어집니다.
• 다음으로, NNN개의 노래 정보가 각각 제목과 전주의 일곱 개 음으로 주어집니다.
• 그 뒤에 맞히기를 시도할 첫 세 음이 MMM개 주어집니다.

출력 형식: 각 시도에 대해 노래 제목, ?, 또는 ! 중 하나를 한 줄에 출력합니다.

해결 방법

이 문제는 특정 패턴(첫 세 음)을 기준으로 노래 제목을 빠르게 찾는 문제입니다. 노래 정보를 사전에 딕셔너리에 저장해 두고, 맞히기 시도마다 해당 패턴이 있는지 빠르게 탐색하도록 합니다.

1. 아이디어 정리
   • 딕셔너리 자료 구조를 사용하여 각 노래의 첫 세 음을 키로 설정하고, 제목을 값으로 저장합니다.
   • 맞히기 시도 시, 입력된 첫 세 음으로 시작하는 노래를 딕셔너리에서 조회해 결과를 도출합니다.
   • 만약 해당 첫 세 음으로 시작하는 제목이 여러 개라면 ?, 하나라면 제목, 없으면 !를 출력합니다.
2. 코드 구현 단계
   • 노래 데이터 저장: 노래 정보를 입력받아 딕셔너리에 첫 세 음을 키로 하고, 제목을 리스트로 저장합니다. 리스트에 저장함으로써 다중 매칭이 가능하도록 합니다.
   • 맞히기 시도 처리: 맞히기 시도 시 딕셔너리를 조회하여 조건에 맞는 결과를 출력합니다.

# 1. 입력 받기
N, M = map(int, input().split())

# 2. 노래 정보를 저장할 딕셔너리 생성
song_dict = {}

# 3. 각 노래 정보를 입력 받아 첫 세 음을 키로 노래 제목을 딕셔너리에 저장
for _ in range(N):
    data = input().split()
    title = data[1]
    melody = ''.join(data[2:5])  # 첫 세 음만 추출
    
    if melody in song_dict:
        song_dict[melody].append(title)
    else:
        song_dict[melody] = [title]

# 4. 맞히기 시도 처리
for _ in range(M):
    guess_melody = ''.join(input().split())
    
    if guess_melody in song_dict:
        titles = song_dict[guess_melody]
        if len(titles) == 1:
            print(titles[0])  # 유일하게 일치하는 제목
        else:
            print('?')  # 여러 개의 제목이 일치
    else:
        print('!')  # 일치하는 제목이 없음

코드 설명

• 노래 정보 입력: 입력받은 각 노래 정보에서 첫 세 음만 추출해 딕셔너리에 저장합니다. 딕셔너리의 키는 첫 세 음, 값은 해당 제목의 리스트입니다.
• 맞히기 시도 처리: 첫 세 음을 기반으로 딕셔너리를 조회하여 조건에 맞는 출력을 도출합니다.

이 코드와 설명을 통해 전주 듣고 노래 맞히기 프로그램을 성공적으로 구현할 수 있습니다.

TODAY TIL

안녕하세요! 이번 포스팅에서는 보드게임 할리갈리와 관련된 흥미로운 코딩 문제를 다뤄보겠습니다. 게임에서 한별이가 종을 쳐야 할 시점을 자동으로 판단하는 코드를 작성하는 방법을 단계별로 설명하겠습니다.

📋 문제 설명

할리갈리 게임은 과일이 그려진 카드들과 종으로 이루어져 있습니다. 카드를 차례로 펼쳐서 한 종류의 과일이 정확히 5개가 될 때 가장 먼저 종을 쳐야 하는 게임입니다. 만약 한 종류의 과일이 5개가 되는 순간을 놓치지 않고 종을 칠 수 있도록 도와주는 프로그램을 만들어봅시다!

입력 조건

• 첫 번째 줄: 펼쳐진 카드의 개수 NNN
• 이후 각 줄에는 과일 종류 SSS와 과일 개수 XXX가 주어집니다.
• 과일 종류는 STRAWBERRY, BANANA, LIME, PLUM 중 하나입니다.

출력 조건

• 종을 쳐야 하면 "YES"를, 그렇지 않으면 "NO"를 출력합니다.

📝 문제 접근 방법

문제를 풀기 위해 각 과일의 개수를 누적한 후, 어떤 과일이 정확히 5개인지 확인하는 과정을 거칩니다.

1. 입력 데이터 처리: 카드의 개수 NNN과 카드별 과일 정보를 입력받습니다.
2. 과일 개수 누적: 각 과일에 대한 개수를 누적하여 관리합니다.
3. 종을 칠 조건 확인: 모든 카드의 정보를 누적한 후, 과일의 총 개수가 정확히 5인 과일이 있는지 확인합니다.

이제 코드로 문제를 해결해 보겠습니다.

# 입력 받기
N = int(input())  # 펼쳐진 카드 개수
fruit_counts = {"STRAWBERRY": 0, "BANANA": 0, "LIME": 0, "PLUM": 0}

# 카드 정보를 받아서 과일 수 누적
for _ in range(N):
    S, X = input().split()
    X = int(X)
    fruit_counts[S] += X

# 종을 칠 조건 확인
should_ring_bell = any(count == 5 for count in fruit_counts.values())

# 결과 출력
if should_ring_bell:
    print("YES")
else:
    print("NO")

코드 설명

1. fruit_counts 딕셔너리를 통해 각 과일의 개수를 0으로 초기화합니다.
2. 각 카드를 처리하면서 S와 X의 값을 읽고, fruit_counts의 해당 과일에 X를 더합니다.
3. any(count == 5 for count in fruit_counts.values())로 과일이 정확히 5개가 된 경우를 확인합니다.
4. 조건에 따라 "YES" 또는 "NO"를 출력합니다.

입력 예시

3
STRAWBERRY 2
BANANA 3
STRAWBERRY 3

출력 예시

YES

위 입력에서는 딸기가 총 5개(2 + 3)가 되므로, 한별이는 종을 쳐야 합니다.

🧩 마무리

이번 포스팅에서는 할리갈리 게임에서 종을 쳐야 하는 시점을 자동으로 판별하는 코드를 구현해 보았습니다. 과일 개수를 누적하면서 조건을 확인하는 문제를 통해 딕셔너리와 반복문의 활용을 연습할 수 있었습니다. 앞으로도 다양한 게임과 관련된 문제로 알고리즘을 즐겁게 풀어보아요!

TODAY TIL

오늘은 모스 부호를 원래의 문자로 해독하는 프로그램을 만들어 보겠습니다. 모스 부호는 짧은 신호와 긴 신호(‘.’, ‘-’)로 이루어져 있으며, 각 문자와 숫자를 모스 부호로 나타낼 수 있습니다. 예를 들어, ‘A’는 .-로, 숫자 ‘1’은 .----로 표기됩니다.

이 문제를 해결하기 위해 단계별로 접근해 보겠습니다.

문제 이해하기

• 입력: 모스 부호로 변환한 메시지와 원래 문자열의 길이 NNN이 주어집니다. 예를 들어, 모스 부호 .... . .-.. .-.. ---가 입력으로 주어지면 우리는 이것을 HELLO로 해독해야 합니다.
• 출력: 주어진 모스 부호 메시지를 원래의 문자로 해독하여, 공백 없이 출력해야 합니다.

해결 순서

1단계: 모스 부호와 문자의 매핑 사전 만들기

모스 부호를 해독하기 위해서는 모스 부호와 알파벳(또는 숫자) 간의 변환이 필요합니다. 이를 위해 morse_code_dict라는 사전을 만들어 각 모스 부호와 해당되는 문자를 연결합니다.

morse_code_dict = {
    ".-": "A", "-...": "B", "-.-.": "C", "-..": "D", ".": "E",
    "..-.": "F", "--.": "G", "....": "H", "..": "I", ".---": "J",
    "-.-": "K", ".-..": "L", "--": "M", "-.": "N", "---": "O",
    ".--.": "P", "--.-": "Q", ".-.": "R", "...": "S", "-": "T",
    "..-": "U", "...-": "V", ".--": "W", "-..-": "X", "-.--": "Y",
    "--..": "Z", ".----": "1", "..---": "2", "...--": "3", "....-": "4",
    ".....": "5", "-....": "6", "--...": "7", "---..": "8", "----.": "9",
    "-----": "0", "--..--": ",", ".-.-.-": ".", "..--..": "?", "---...": ":",
    "-....-": "-", ".--.-.": "@"
}

2단계: 입력 받기

문제에서는 두 가지 입력이 주어집니다.

• 첫 번째 줄은 변환할 원래 문자열의 길이인 NNN (사용하지 않으므로 무시 가능)
• 두 번째 줄은 모스 부호 메시지입니다.

N = int(input())  # 문자열의 길이 (사용하지 않음)
morse_code_message = input().split()  # 공백으로 구분된 모스 부호 메시지

split() 함수를 사용하여 모스 부호 메시지를 공백 기준으로 나누어 각 모스 부호가 리스트에 저장되도록 합니다.

3단계: 모스 부호 해독하기

모스 부호 메시지에 있는 각 모스 부호를 순서대로 morse_code_dict 사전을 통해 해독하여 원래의 문자로 변환합니다.

decoded_message = ""
for code in morse_code_message:
    decoded_message += morse_code_dict[code]  # 사전에서 해당 문자 찾기

이 과정에서는 for 반복문을 사용하여 각 모스 부호를 사전에서 찾아 decoded_message에 추가합니다.

4단계: 결과 출력

해독된 문자열 decoded_message를 출력합니다.

print(decoded_message)

전체 코드

아래는 위의 단계를 모두 포함한 전체 코드입니다

# 모스 부호와 문자 매핑 사전 만들기
morse_code_dict = {
    ".-": "A", "-...": "B", "-.-.": "C", "-..": "D", ".": "E",
    "..-.": "F", "--.": "G", "....": "H", "..": "I", ".---": "J",
    "-.-": "K", ".-..": "L", "--": "M", "-.": "N", "---": "O",
    ".--.": "P", "--.-": "Q", ".-.": "R", "...": "S", "-": "T",
    "..-": "U", "...-": "V", ".--": "W", "-..-": "X", "-.--": "Y",
    "--..": "Z", ".----": "1", "..---": "2", "...--": "3", "....-": "4",
    ".....": "5", "-....": "6", "--...": "7", "---..": "8", "----.": "9",
    "-----": "0", "--..--": ",", ".-.-.-": ".", "..--..": "?", "---...": ":",
    "-....-": "-", ".--.-.": "@"
}

# 입력 받기
N = int(input())  # 문자열의 길이 (사용하지 않음)
morse_code_message = input().split()  # 공백으로 구분된 모스 부호 메시지

# 모스 부호 해독
decoded_message = ""
for code in morse_code_message:
    decoded_message += morse_code_dict[code]  # 사전에서 변환

# 결과 출력
print(decoded_message)

마무리

이제 모스 부호 메시지를 해독하는 프로그램이 완성되었습니다! 각 단계를 순서대로 따라가며 코드를 작성하니 더 쉽게 이해할 수 있었을 거라 생각합니다. 앞으로도 다양한 문제를 해결하며 코딩 실력을 키워 나가길 응원합니다!

TODAY TIL

오늘은 문자열을 특정 규칙에 따라 여러 덩어리로 나누는 문제를 해결해 보았습니다. 이 문제에서는 주어진 문자열을 기준에 따라 잘라내어, 분리된 덩어리 개수를 구해야 했습니다.

문제 설명

문자열 s가 주어졌을 때, 다음 규칙을 따라 문자열을 여러 문자열로 분해합니다.

1. 첫 글자를 읽고, 이 글자를 x로 설정합니다.
2. 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다.
3. 두 횟수가 처음으로 같아지는 순간, 지금까지 읽은 문자열을 하나의 덩어리로 분리합니다.
4. 분리한 문자열을 제외하고 남은 문자열에 대해서 같은 과정을 반복합니다.
5. 문자열이 모두 처리될 때까지 반복하며, 분리된 문자열의 개수를 반환합니다.

예시:

• 입력: "banana"
• 출력: 3 (분리된 문자열: ["ba", "na", "na"])

해결 과정

문제를 해결하기 위해 다음 단계로 접근했습니다.

1. 첫 글자 선택하기: 문자열에서 첫 글자를 x로 설정합니다.
2. 글자 수 세기: 첫 글자 x의 개수와 x가 아닌 글자의 개수를 세면서 진행합니다.
3. 덩어리 분리: 두 개의 개수가 같아지는 순간을 기준으로 덩어리를 분리합니다.
4. 남은 문자열 반복: 문자열의 끝까지 위 과정을 반복하여 남은 모든 문자열을 분리합니다.

코드 구현

아래는 이 문제를 해결하는 Python 코드입니다.

def solution(s):
    answer = 0  # 분리된 덩어리 개수
    i = 0  # 현재 위치를 나타내는 인덱스

    while i < len(s):  # 문자열의 끝까지 읽을 때까지 반복
        x = s[i]  # 첫 글자를 x로 설정
        count_x = 0  # x의 개수를 세는 변수
        count_other = 0  # x가 아닌 글자의 개수를 세는 변수

        # x와 다른 글자들을 세어가며 두 개가 같아질 때까지 진행
        while i < len(s):
            if s[i] == x:
                count_x += 1  # x 글자가 나오면 count_x 증가
            else:
                count_other += 1  # 다른 글자가 나오면 count_other 증가

            i += 1  # 다음 글자로 이동

            # x와 다른 글자의 개수가 같아지면 덩어리 분리
            if count_x == count_other:
                answer += 1  # 덩어리 하나 추가
                break  # 분리 후 다시 반복
    
        # 남은 문자열이 있으면 마지막 덩어리로 추가
        if i == len(s) and count_x != count_other:
            answer += 1
    
    return answer

코드 설명

• 첫 글자 설정: 처음 x를 설정해주고, count_x와 count_other를 초기화합니다.
• 문자 개수 세기: count_x는 x 글자, count_other는 x가 아닌 글자의 개수를 나타내며, 둘이 같아질 때마다 덩어리를 하나 추가합니다.
• 남은 문자열 처리: 문자열 끝까지 다 읽었는데도 두 개수가 다르다면 남은 문자열을 마지막 덩어리로 간주합니다.

예제 테스트

# 예제 입력
print(solution("banana"))  # 출력: 3
print(solution("abracadabra"))  # 출력: 6
print(solution("aaabbaccccabba"))  # 출력: 3

배운 점

• 문자열의 특정 규칙을 기준으로 구분해야 할 때, 문자를 카운팅하는 방법이 유용하다는 것을 알게 되었습니다.
• 분리 조건에 따라 반복문을 중간에 빠져나오거나 특정 조건을 설정하는 것이 중요함을 깨달았습니다.
• 알고리즘의 기초를 배우는게 중요하다는걸 느꼈습니다.

이 포스팅을 통해 문자열 분리 문제를 규칙적으로 해결하는 방법을 익힐 걸 공유할수 있어서 좋았습니다.