공부블로그

TODAY TIL

📌 문제 설명

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 숫자들을 사용해 만들 수 있는 가장 큰 정수를 두 수의 "짝꿍"이라고 합니다.
짝꿍을 구하는 규칙은 다음과 같습니다:

1. X와 Y에 공통으로 나타나는 숫자만 사용합니다.
2. 공통 숫자 중 가능한 최대 빈도수만큼 사용합니다.
3. 공통 숫자가 없다면 -1을 반환합니다.
4. 짝꿍이 0으로만 구성되어 있다면 0을 반환합니다.

예시

• X = 3403, Y = 13203
  → 짝꿍: 330
• X = 5525, Y = 1255
  → 짝꿍: 552
• X = 12345, Y = 67890
  → 짝꿍: -1

💡 문제 해결 방법

이 문제를 해결하기 위한 단계별 접근법은 다음과 같습니다:

Step 1: 숫자의 빈도수 계산

• X와 Y의 각 숫자가 몇 번 나타나는지를 계산합니다.
• collections.Counter를 사용하면 간단하게 자릿수의 빈도를 구할 수 있습니다.

Step 2: 공통 숫자와 빈도수 찾기

• X와 Y의 공통 숫자를 찾고, 각 숫자의 최소 빈도를 기준으로 사용할 수 있는 최대 빈도를 계산합니다.

Step 3: 결과 문자열 생성

• 공통 숫자를 내림차순으로 정렬하여 가장 큰 숫자를 만듭니다.
• 예외 처리:
  • 공통 숫자가 없다면 -1 반환.
  • 결과가 0으로만 구성되어 있다면 0 반환.

🖥 코드 구현

from collections import Counter

def solution(X, Y):
    # Step 1: 숫자의 빈도수를 계산
    count_X = Counter(X)
    count_Y = Counter(Y)
    
    # Step 2: 공통 숫자와 최소 빈도 계산
    common_numbers = []
    for num in count_X.keys():
        if num in count_Y:
            # 공통으로 등장하는 숫자 중 가능한 최대 갯수를 추가
            common_numbers.extend([num] * min(count_X[num], count_Y[num]))
    
    # Step 3: 결과 문자열 생성
    if not common_numbers:  # 공통 숫자가 없으면
        return "-1"
    
    # 숫자를 내림차순으로 정렬
    common_numbers.sort(reverse=True)
    result = ''.join(common_numbers)
    
    # 숫자가 모두 0으로만 구성된 경우
    if result[0] == "0":
        return "0"
    
    return result

🛠 동작 원리 설명

1. Counter를 활용한 숫자 빈도수 계산

count_X = Counter("3403")  # {'3': 2, '4': 1, '0': 1}
count_Y = Counter("13203") # {'1': 1, '3': 2, '2': 1, '0': 1}

Counter는 각 숫자의 빈도를 딕셔너리 형태로 반환합니다.

2. 공통 숫자와 최소 빈도 찾기

count_X와 count_Y의 키를 비교하여 공통 숫자를 찾고, 가능한 최대 빈도를 리스트에 추가합니다.

common_numbers = ['3', '3', '0']  # 최소 빈도를 기준으로 계산

3. 결과 생성

common_numbers를 내림차순으로 정렬하여 가장 큰 숫자를 생성합니다.

common_numbers.sort(reverse=True)  # ['3', '3', '0']
result = ''.join(common_numbers)   # "330"

⚙️ 테스트 케이스

# 테스트 케이스
print(solution("3403", "13203"))  # 330
print(solution("5525", "1255"))   # 552
print(solution("12345", "67890")) # -1
print(solution("100", "203045"))  # 0
print(solution("0", "0"))         # 0

결과

XY결과

💡 문제 풀이 요약

1. 숫자의 빈도를 계산하여 X와 Y의 공통 숫자를 찾습니다.
2. 공통 숫자를 기준으로 가능한 최대 빈도를 계산하여 숫자를 조합합니다.
3. 숫자를 내림차순 정렬하여 가장 큰 짝꿍을 반환합니다.
4. 특별 케이스 (공통 숫자가 없거나, 결과가 0)를 처리합니다.

⏳ 시간 복잡도

• 빈도 계산: O(N + M) (X와 Y의 길이)
• 공통 숫자 탐색 및 정렬: O(10 + K log K) (K는 공통 숫자의 수, 최대 10)

최종 시간 복잡도는 **O(N + M)**입니다.

✏️ 블로그 마무리

이 문제는 문자열 조작과 빈도 계산을 효율적으로 다루는 연습에 적합합니다.
collections.Counter와 같은 내장 모듈을 활용하면 복잡한 문제도 간단히 해결할 수 있습니다.

여러분도 자신만의 풀이법으로 문제를 해결하고 Python을 더욱 깊게 이해해 보세요! 🚀
궁금한 점이나 추가적인 개선 아이디어가 있다면 댓글로 공유해 주세요! 😊

TODAY TIL

환규와 태욱이는 문자열을 가지고 재미있는 "탕수육 게임"을 하고 있습니다. 게임의 규칙은 다음과 같습니다:

1. 누가 먼저 시작할지 순서를 정합니다.
2. 먼저 시작하는 사람이 단어의 첫 글자를 말합니다.
3. 이후 두 사람은 번갈아 가며 다음 글자를 순서대로 말합니다.
4. 단어의 마지막 글자에 도달하면, 다시 단어의 첫 글자로 돌아가서 반복합니다.
5. 잘못된 글자를 말하면 게임에서 지게 됩니다.

예를 들어, 단어가 탕수육이라면:

• 첫 번째 사람: "탕", "육", "수", "탕", "육", "수" ...
• 두 번째 사람: "수", "탕", "육", "수", "탕", "육" ...

코드 소개

탕수육 게임의 규칙을 바탕으로, 두 사람이 번갈아 문자열을 나누어 가져가는 방식을 Python 코드로 구현했습니다. 이번 포스팅에서는 이 코드를 분석하며 어떻게 동작하는지 알아보겠습니다.

코드

def solution(case):
    answer = 0

    for v in case:
        player1 = []
        player2 = []
        for i, c in enumerate(v if (len(v) % 2) == 0 else v * 2):
            if i % 2 == 0:
                player1.append(c)
            else:
                player2.append(c)
        print("".join(player1))
        print("".join(player2))
    return answer


n = int(input())
games = [input() for _ in range(n)]
solution(games)

코드 분석

1. 함수 정의

def solution(case):
    answer = 0

• 함수 solution은 문자열의 리스트 case를 입력으로 받습니다.
• answer는 반환 값으로 초기화되지만, 현재는 출력 외에 사용되지 않습니다.

2. 게임 데이터 처리

for v in case:
    player1 = []
    player2 = []

• 각 문자열 v를 순회하며, 두 사람의 문자 선택을 저장할 리스트 player1과 player2를 초기화합니다.

3. 문자열 순회 및 나누기

for i, c in enumerate(v if (len(v) % 2) == 0 else v * 2):
    if i % 2 == 0:
        player1.append(c)
    else:
        player2.append(c)

• 문자열의 길이에 따라 처리 방식이 달라집니다:
  1. 짝수 길이: 문자열 v 그대로 사용.
  2. 홀수 길이: 문자열 v를 두 번 반복한 문자열 v * 2 사용.
     • 이렇게 하면 홀수 길이에서도 두 사람이 계속 번갈아 가며 문자를 가져갈 수 있습니다.
• enumerate를 사용해 문자열의 각 문자와 해당 인덱스 i를 가져옵니다:
  • i % 2 == 0: 첫 번째 사람이 선택(player1에 추가).
  • i % 2 == 1: 두 번째 사람이 선택(player2에 추가).

4.결과 출력

print("".join(player1))
print("".join(player2))

• 두 사람의 선택 결과를 각각 출력합니다.
• player1과 player2 리스트의 문자를 합쳐 문자열로 변환한 뒤 출력합니다.

5.입력 및 함수 호출

n = int(input())
games = [input() for _ in range(n)]
solution(games)

• 입력 데이터:
  • 첫 번째 줄: 게임의 수 n.
  • 이후 n개의 문자열이 게임의 데이터로 입력됩니다.
• solution 함수에 입력 데이터를 전달하여 결과를 처리합니다.

동작 예시

입력

2
탕수육
ABC

처리 과정

1. 첫 번째 게임: "탕수육"
   • player1: "탕육수" → 첫 번째 사람이 가져간 문자.
   • player2: "수탕육" → 두 번째 사람이 가져간 문자.
   • 출력:
      

탕육수
수탕육

2 .두 번째 게임: "ABC"

• 문자열 길이가 홀수이므로 "ABCABC"로 확장.
• player1: "ACB" → 첫 번째 사람이 가져간 문자.
• player2: "BCA" → 두 번째 사람이 가져간 문자.
• 출력:
   

ACB
BCA

최종 출력

탕육수
수탕육
ACB
BCA

코드의 한계와 개선 가능성

1. 반복 확장 방식의 비효율성
   • 홀수 길이 문자열에서 v * 2로 확장하면 메모리를 낭비할 수 있습니다.
   • 이를 대신해 인덱스를 순환적으로 접근하면 더 효율적입니다.
2. 리턴 값 사용
   • 현재 코드는 결과를 출력만 하고 반환하지 않습니다. 결과를 리스트로 반환하면 더 유연하게 활용할 수 있습니다.

개선된 코드

def solution(case):
    results = []
    for v in case:
        player1 = []
        player2 = []
        n = len(v)
        for i in range(n):
            if i % 2 == 0:
                player1.append(v[i % n])
            else:
                player2.append(v[i % n])
        results.append(("".join(player1), "".join(player2)))
    return results

# 입력 처리
n = int(input())
games = [input() for _ in range(n)]
result = solution(games)

# 결과 출력
for r in result:
    print(r[0])
    print(r[1])

결론

이 코드는 두 사람이 번갈아 문자열을 나누는 방식으로 게임을 진행하도록 구현되었습니다. 이를 통해 문자열의 반복적인 패턴을 쉽게 처리할 수 있습니다. 개선된 코드는 더 효율적으로 처리하며, 결과를 반환해 다양한 방식으로 활용할 수 있습니다.

탕수육 게임처럼 단순하지만 재미있는 문제를 통해 문자열 처리와 반복 구조에 대한 이해를 높여보세요! 😊

TODAY TIL

안녕하세요! 오늘은 선물 더미에서 가장 많은 선물을 가져가고 남은 선물을 계산하는 문제를 풀어보겠습니다. 이 문제는 선물 더미 중 가장 큰 값을 선택하고, 해당 더미에서 ⌊제곱근⌋만 남기고 나머지를 가져가는 과정을 k초 동안 반복한 후 남은 선물의 총합을 구하는 문제입니다.

문제 설명

문제

주어진 정수 배열 gifts는 다양한 더미에 있는 선물의 개수를 나타냅니다. 매초마다 가장 많은 선물이 있는 더미를 선택하여 ⌊제곱근⌋만 남겨두고 나머지를 가져갑니다. k초 동안 이 작업을 반복하고 최종적으로 남은 모든 선물의 총합을 반환합니다.

예시

입력

gifts = [25, 64, 9, 4, 100]
k = 4

출력

29

설명

• 첫 번째 초: 100을 선택하여 ⌊√100⌋ = 10을 남김 → [25, 64, 9, 4, 10]
• 두 번째 초: 64를 선택하여 ⌊√64⌋ = 8을 남김 → [25, 8, 9, 4, 10]
• 세 번째 초: 25를 선택하여 ⌊√25⌋ = 5를 남김 → [5, 8, 9, 4, 10]
• 네 번째 초: 10을 선택하여 ⌊√10⌋ = 3을 남김 → [5, 8, 9, 4, 3]
• 최종 남은 선물의 총합: 29

문제 풀이

접근 방법

• gifts 배열을 최대 힙(max heap)으로 변환하여 가장 큰 값을 효율적으로 가져옵니다.
• k번 동안 가장 큰 값의 선물을 가져가고 남은 ⌊제곱근⌋ 값을 다시 힙에 넣습니다.
• heapq 모듈을 활용해 효율적으로 최대값을 찾고, ⌊제곱근⌋을 계산하여 힙을 업데이트합니다.

코드 구현

다음은 문제를 해결하기 위한 Python 코드입니다.

import heapq
import math

def remaining_gifts(gifts, k):
    # 최대 힙으로 변환하기 위해 음수로 저장
    max_heap = [-gift for gift in gifts]
    heapq.heapify(max_heap)
    
    for _ in range(k):
        # 가장 큰 값 꺼내기
        max_gift = -heapq.heappop(max_heap)
        # 제곱근을 구해 남은 선물 수 계산
        remaining_gift = math.floor(math.sqrt(max_gift))
        # 남은 선물 다시 힙에 삽입
        heapq.heappush(max_heap, -remaining_gift)
    
    # 남은 선물의 총합 구하기
    return -sum(max_heap)

# 예시 실행
print(remaining_gifts([25, 64, 9, 4, 100], 4))  # 출력: 29
print(remaining_gifts([1, 1, 1, 1], 4))  # 출력: 4

코드 설명

1. gifts 배열을 최대 힙으로 변환합니다. Python의 heapq는 최소 힙만 지원하므로 음수로 값을 넣어 최대 힙처럼 사용합니다.
2. k번 반복하며, 가장 큰 값을 꺼내 ⌊제곱근⌋을 계산한 후 다시 힙에 넣습니다.
3. 모든 작업이 끝난 후 힙에 남은 값들을 합산하여 반환합니다.

시간 복잡도

• 힙을 사용하는 삽입 및 삭제의 시간 복잡도는 O(log n)이며, 이를 k번 반복하므로 전체 시간 복잡도는 O(k log n)입니다.

결론

이 코드는 주어진 문제 조건을 충족하면서 효율적으로 풀 수 있는 방법을 제시합니다. heapq와 math 모듈을 적절히 사용하여 최대값을 찾고 갱신하는 과정을 손쉽게 구현할 수 있습니다.

이 글이 여러분의 문제 해결에 도움이 되었기를 바랍니다. 질문이나 추가적인 설명이 필요하면 댓글로 남겨주세요!

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

안녕하세요! 오늘은 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

 안녕하세요!  오늘은 이 큐를 이용해서 여러 가지 명령어를 처리하는 프로그램을 파이썬으로 구현해볼 거예요!

큐(Queue)란?

큐(Queue)는 FIFO(First In, First Out) 구조를 가진 자료 구조에요. 줄을 서서 차례로 서비스를 받는 것처럼, 먼저 들어온 데이터가 먼저 나가는 구조를 가지고 있어요. 반대로 **스택(Stack)**은 LIFO(Last In, First Out) 구조를 가지는데, 나중에 들어온 것이 먼저 나가는 구조를 가지고 있어요.

오늘 우리가 구현할 프로그램은 정수를 저장하는 큐에 여러 가지 명령어를 처리하는 프로그램이에요. 여기서 사용될 명령어는 다음과 같아요:

1. push X: 정수 X를 큐에 넣습니다. 즉, 줄의 끝에 새로운 사람이 들어오는 것과 같아요.
2. pop: 큐의 가장 앞에 있는 값을 꺼내서 출력해요. 줄의 맨 앞에 있는 사람이 나가는 것과 같은 일이에요. 만약 줄에 아무도 없으면 -1을 출력해요.
3. size: 현재 큐에 몇 명이 있는지를 출력해요.
4. empty: 큐가 비어 있으면 1을, 비어 있지 않으면 0을 출력해요.
5. front: 큐의 가장 앞에 있는 값을 출력해요. 아무도 없으면 -1을 출력해요.
6. back: 큐의 가장 뒤에 있는 값을 출력해요. 아무도 없으면 -1을 출력해요.

파이썬 코드로 큐 구현하기

아래 코드는 deque를 사용해서 큐를 쉽게 구현한 거예요. deque는 양쪽 끝에서 데이터를 넣고 빼는 데 최적화된 자료구조로, 파이썬의 collections 모듈에서 제공해요.

from collections import deque
import sys

input = sys.stdin.read

def queue_operations(commands):
    queue = deque()
    result = []
    for command in commands:
        if "push" in command:
            value = command.split()[1]
            queue.append(value)
        elif command == "pop":
            result.append(queue.popleft() if queue else -1)
        elif command == "size":
            result.append(len(queue))
        elif command == "empty":
            result.append(0 if queue else 1)
        elif command == "front":
            result.append(queue[0] if queue else -1)
        elif command == "back":
            result.append(queue[-1] if queue else -1)
    return result

def main():
    data = input().splitlines()
    commands = data[1:]
    results = queue_operations(commands)
    sys.stdout.write("\n".join(map(str, results)) + "\n")

if __name__ == "__main__":
    main()

코드 설명

1. deque를 사용해 큐 만들기: queue = deque()로 큐를 만들었어요. 이제 queue.append()로 값을 추가하고, queue.popleft()로 값을 꺼낼 수 있어요.
2. 명령어 처리하기:
   • push X: 큐의 끝에 값을 추가해요.
   • pop: 큐의 앞에 있는 값을 꺼내고, 큐가 비어있다면 -1을 저장해요.
   • size: 현재 큐의 크기를 저장해요.
   • empty: 큐가 비어 있으면 1, 비어 있지 않으면 0을 저장해요.
   • front: 큐의 가장 앞에 있는 값을 저장하고, 큐가 비어있다면 -1을 저장해요.
   • back: 큐의 가장 뒤에 있는 값을 저장하고, 큐가 비어있다면 -1을 저장해요.
3. 결과 출력하기: 각 명령어의 결과를 리스트에 모아서 마지막에 한 번에 출력해요.

큐의 활용

큐는 여러 가지 상황에서 활용될 수 있어요. 예를 들어, 프린터의 출력 작업을 처리할 때, 먼저 요청된 작업부터 처리하는 데 큐가 사용돼요. 또 너비 우선 탐색(BFS) 같은 알고리즘에서도 큐가 중요한 역할을 해요.

이제 여러분도 큐의 개념과 구현 방법을 잘 이해할 수 있겠죠? 줄을 서는 것처럼 먼저 들어간 것이 먼저 나오는 이 간단한 개념을 파이썬으로 구현해보세요!

마무리

이 글에서는 큐라는 자료구조를 이해하고, 파이썬으로 직접 구현해 보았어요. 큐의 간단한 개념을 다양한 상황에 적용할 수 있으니, 여러 문제를 풀어보면서 직접 사용해 보세요. 이해하기 어려운 부분이나 더 궁금한 점이 있다면 언제든지 댓글로 남겨주세요!

TODAY TIL

 안녕하세요! 오늘은 주어진 여러 개의 테스트 케이스에서 단어들을 반대 순서로 출력하는 Python 코드를 다루어 보겠습니다. 이 문제는 간단한 문자열 처리 문제로, 입출력 포맷에 유의하며 해결하는 방법을 배워보겠습니다.

문제 설명

주어진 입력은 N개의 케이스로 구성되어 있습니다. 각 케이스에는 스페이스로 구분된 여러 단어가 있으며, 이를 반대 순서로 출력하는 것이 목표입니다. 각 케이스의 결과는 특정 출력 형식에 맞춰야 합니다.

• 입력 조건:
  • 첫 줄에는 케이스의 개수 NNN이 주어집니다.
  • 각 케이스는 한 줄에 하나씩 입력되며, 단어들은 공백으로 구분됩니다. 라인의 처음과 끝에는 공백이 없습니다.
  • NNN과 각 문장의 길이 LLL은 1 ≤ LLL ≤ 25를 만족합니다.
• 출력 조건:
  • 각 케이스에 대해 "Case #x: " 형식으로 번호를 출력한 후, 반대 순서로 단어를 출력합니다.

예제 코드

이제 이 문제를 해결하는 Python 코드를 살펴보겠습니다.

# 첫 번째 줄에서 전체 케이스의 개수 N을 입력받는다.
N = int(input())

# 각 케이스를 반복하며 처리한다.
for i in range(1, N + 1):
    # 각 케이스에 대한 단어 입력을 받는다.
    sentence = input().strip()  # strip()을 사용해 앞뒤 공백 제거
    
    # 입력받은 문장을 단어 단위로 분할
    words = sentence.split()
    
    # 단어 리스트를 뒤집는다.
    reversed_words = words[::-1]
    
    # 'Case #x: ' 형식으로 결과를 출력
    print(f"Case #{i}: {' '.join(reversed_words)}")

실행 예제

다음은 입력과 출력 예제입니다.

입력:

5
Hello World
Programming is fun
Python is powerful
Reverse these words
Learning is continuous

출력:

Case #1: World Hello
Case #2: fun is Programming
Case #3: powerful is Python
Case #4: words these Reverse
Case #5: continuous is Learning

코드 설명

1. input() 함수로 NNN을 입력받아 테스트 케이스의 수를 가져옵니다.
2. strip() 메서드로 각 줄의 앞뒤 공백을 제거하고, split()으로 단어를 리스트로 만듭니다.
3. 리스트 슬라이싱 [::-1]을 사용하여 단어의 순서를 뒤집습니다.
4. ' '.join()으로 뒤집힌 단어 리스트를 다시 문자열로 합쳐서 출력 포맷에 맞춰 출력합니다.

마무리

이 코드는 주어진 문제를 해결하는 데 필요한 기본적인 문자열 처리 기법을 포함하고 있습니다. 입출력 포맷과 리스트 조작법을 연습할 수 있는 좋은 예제입니다.

이 코드를 여러분의 Python 학습에 도움이 되기를 바랍니다!

TODAY TIL

안녕하세요! 오늘은 코딩 테스트에서 자주 나오는 스택(Stack) 구현 문제를 함께 풀어보겠습니다. 이 문제는 입력으로 주어지는 명령어들을 스택을 통해 처리하는 프로그램을 작성하는 것입니다. 명령어의 종류와 해결 방법을 차근차근 적어보려고 합니다.

문제 설명

우리는 다음과 같은 명령어를 처리할 수 있는 스택을 구현해야 합니다:

• push X: 정수 X를 스택에 넣습니다.
• pop: 스택에서 가장 위에 있는 정수를 빼고 출력합니다. 스택이 비어 있으면 -1을 출력합니다.
• size: 스택에 들어있는 정수의 개수를 출력합니다.
• empty: 스택이 비어 있으면 1, 아니면 0을 출력합니다.
• top: 스택의 가장 위에 있는 정수를 출력합니다. 스택이 비어 있으면 -1을 출력합니다.

코드 구현

먼저, Python의 sys.stdin.readline()을 사용해 입력을 빠르게 처리하고 각 명령어를 효율적으로 처리하는 코드를 작성하겠습니다.

import sys
input = sys.stdin.readline

# 스택 초기화
stack = []

# 명령 수 입력
N = int(input().strip())

# 명령 처리
for _ in range(N):
    command = input().strip()
    
    if command[:4] == "push":
        # push X 처리
        stack.append(int(command.split()[1]))
    elif command == "pop":
        print(stack.pop() if stack else -1)
    elif command == "size":
        print(len(stack))
    elif command == "empty":
        print(1 if not stack else 0)
    elif command == "top":
        print(stack[-1] if stack else -1)

코드 설명

• import sys: Python의 기본 입력 함수 input()은 느릴 수 있기 때문에 sys.stdin.readline()을 사용하여 입력 속도를 최적화했습니다.
• 스택 구현: Python의 리스트를 사용해 스택을 구현합니다. append()로 push 연산을, pop()으로 pop 연산을 쉽게 처리할 수 있습니다.
• 명령어 처리: 명령어는 if-elif 조건문으로 처리하며, 명령어가 push로 시작하는지 command[:4] == "push"로 확인해 split()으로 숫자를 추출합니다.
• 출력 처리:
  • pop: 스택이 비어 있으면 -1을 출력하고, 아니면 마지막 요소를 제거하고 출력합니다.
  • size: len(stack)을 출력합니다.
  • empty: 스택이 비어 있으면 1, 아니면 0을 출력합니다.
  • top: 스택의 마지막 요소를 출력하되, 비어 있으면 -1을 출력합니다.

마무리

이제 이 코드를 통해 코딩 테스트에서 자주 나오는 스택 문제를 해결할 수 있습니다. 입력을 빠르게 처리하고 명령어를 간단하게 구현하여 시간 초과를 방지할 수 있습니다.

이 글이 도움이 되었다면 블로그 구독과 댓글도 부탁드려요! 앞으로도 더 많은 코딩 팁과 문제 풀이를 공유할 예정입니다. 😊

TODAY TIL

안녕하세요! 이번 포스팅에서는 군대 근무 시간 공평성 확인 문제와 관련된 흥미로운 코딩 문제를 다뤄보겠습니다. 단계적으로 설명하고 코드 구현을 공유합니다.

군대 근무 시간 공평성 확인 문제 풀이 (단계별 접근법)

문제 개요

푸앙이와 동기들은 군대에서 4교대 근무를 합니다. 각 시간대(08:00 :12:00, 12:00 : 18:00, 18:00 :22:00, 22:00 :08:00)별로 근무 시간이 다르고, 각자의 근무 시간이 최대한 공평하게 배분되기를 원합니다. 주어진 근무표가 공평하게 분배되었는지, 즉 각 근무자의 총 근무 시간 차이가 12시간 이하인지 판단하는 프로그램을 작성해보겠습니다.

단계별 문제 해결 과정

1단계: 문제 이해하기

• 주어진 정보
  • 주 수(N)가 주어지고, 각 주마다 4개의 근무 시간이 제공됩니다.
  • 시간대는 각각 4시간, 6시간, 4시간, 10시간으로 구성됩니다.
  • 근무표에서 -는 근무자가 없는 것을 의미하고, 근무자가 여러 명일 경우 공백으로 구분됩니다.
• 목표
  • 근무표에서 모든 근무자의 총 근무 시간을 계산하여, 최대 근무 시간과 최소 근무 시간의 차이가 12시간 이하인지 확인합니다.
  • 근무자가 없는 경우는 공평한 것으로 간주합니다.

2단계: 계획 세우기

1. 입력 처리: 주의 개수 N을 입력받고, 각 주별로 4줄씩 근무표를 읽어옵니다.
2. 근무 시간 계산하기: 각 시간대의 근무자를 확인하여 근무 시간을 누적합니다. 각 시간대에 따라 4, 6, 4, 10시간을 해당 근무자에게 추가합니다.
3. 공평성 검사: 모든 근무자의 근무 시간을 비교하여 차이가 12시간 이하인지 확인하고, 결과를 출력합니다.

3단계: 코드 작성 (단계별로 해결)

각 단계를 코드로 작성하면서 이해해보겠습니다

# 1. 입력 처리
N = int(input())  # 주의 개수 입력받기
schedule = [input().strip() for _ in range(N * 4)]  # 전체 근무표 입력받기

설명: N은 주의 개수이고, 근무표는 N * 4 줄로 주어집니다. schedule 리스트에 각 줄을 저장합니다.

# 2. 근무 시간 정의
hours = [4, 6, 4, 10]  # 각 시간대의 근무 시간 (08:00~12:00, 12:00~18:00, 18:00~22:00, 22:00~08:00)
work_time = {}  # 각 사람의 총 근무 시간을 저장할 딕셔너리

• 설명: 각 시간대별 근무 시간을 리스트에 저장하여 반복문에서 참조하기 쉽게 합니다.
• 딕셔너리 생성: work_time은 각 근무자의 이름을 키로 하고 근무 시간을 값으로 저장합니다.

# 3. 근무 시간 누적 계산
for i in range(N):  # 매 주마다 4개의 시간대가 있음
    for j in range(4):  # 각 시간대별로 근무자 확인
        people = schedule[i * 4 + j].split()  # 각 시간대별 근무자를 공백으로 분리
        for person in people:
            if person != '-':  # 근무자가 있는 경우만 처리
                if person not in work_time:
                    work_time[person] = 0
                work_time[person] += hours[j]  # 해당 시간대의 근무 시간을 더해줌

설명: i와 j를 이용해 각 주의 근무표에서 4개의 시간대를 차례로 가져오고, split()으로 각 시간대별 근무자를 분리합니다. -이 아닌 근무자에게만 시간을 누적합니다.

# 4. 공평성 검사
if work_time:  # 근무자가 있는 경우
    max_hours = max(work_time.values())
    min_hours = min(work_time.values())
    print("Yes" if max_hours - min_hours <= 12 else "No")
else:  # 근무자가 없는 경우
    print("Yes")

• 설명: 모든 근무자의 근무 시간을 비교하여 차이가 12시간 이하인 경우 “Yes”, 그렇지 않으면 “No”를 출력합니다.
• 예외 처리: 근무자가 없다면 바로 "Yes"를 출력합니다.

코드 전체

위의 각 단계를 하나의 코드로 합치면 다음과 같습니다.

# 입력 처리
N = int(input())  # 주의 개수
schedule = [input().strip() for _ in range(N * 4)]  # 전체 근무표 입력받기

# 각 시간대에 해당하는 근무 시간 정의
hours = [4, 6, 4, 10]  # 08:00~12:00, 12:00~18:00, 18:00~22:00, 22:00~08:00
work_time = {}  # 각 사람의 총 근무 시간을 저장할 딕셔너리

# 근무 시간 계산
for i in range(N):  # 매 주마다 4개의 시간대가 있음
    for j in range(4):  # 각 시간대별로 근무자 확인
        people = schedule[i * 4 + j].split()  # 각 시간대별 근무자를 분리
        for person in people:
            if person != '-':  # 근무자가 있는 경우만
                if person not in work_time:
                    work_time[person] = 0
                work_time[person] += hours[j]  # 해당 시간대의 근무 시간을 추가

# 공평성 검사
if work_time:  # 근무자가 있는 경우
    max_hours = max(work_time.values())
    min_hours = min(work_time.values())
    print("Yes" if max_hours - min_hours <= 12 else "No")
else:  # 근무자가 없는 경우
    print("Yes")

결론

이 문제를 통해 단계별로 문제를 나누어 풀어보았습니다. 입력을 먼저 처리한 후, 근무 시간을 누적 계산하고 공평성을 검사하는 방식으로 해결했습니다. 각 단계마다 목표를 명확히 설정하고 코드를 작성해 가면 더욱 이해하기 쉬울 것입니다.

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('!')  # 일치하는 제목이 없음

코드 설명

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

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