공부블로그

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

안녕하세요! 오늘은 마라톤에 참여한 선수 중 단 한 명의 완주하지 못한 선수를 찾는 문제를 해결하는 방법을 다뤄보겠습니다. 이 문제는 코딩 테스트에서 자주 나오는 유형으로, 배열과 정렬을 다루는 좋은 연습이 됩니다.

문제 설명

수많은 마라톤 선수들이 마라톤에 참여했는데, 단 한 명의 선수를 제외하고는 모두 완주했습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어졌을 때, 완주하지 못한 선수의 이름을 반환하는 함수를 작성하세요.

제한사항

• 마라톤에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion 배열의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

문제 해결 방법

이 문제를 효율적으로 풀기 위해 정렬을 사용한 방법을 설명하겠습니다.

해결 방법 순서

1. participant와 completion 배열을 정렬합니다.
2. 정렬된 상태에서 두 배열을 처음부터 비교하면서 일치하지 않는 요소를 찾습니다.
3. 만약 모든 요소가 일치하면 participant 배열의 마지막 요소가 완주하지 못한 선수입니다.

코드 구현

def solution(participant, completion):
    participant.sort()  # 참가자 배열 정렬
    completion.sort()   # 완주자 배열 정렬
    
    # 정렬된 배열에서 비교
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    
    # 마지막 참가자가 완주하지 못한 경우
    return participant[-1]

예제 테스트

예제 #1:

print(solution(["leo", "kiki", "eden"], ["eden", "kiki"]))  # 결과: "leo"

예제 #2

print(solution(["marina", "josipa", "nikola", "vinko", "filipa"], ["josipa", "filipa", "marina", "nikola"]))  # 결과: "vinko"

예제 #3:

print(solution(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]))  # 결과: "mislav"

코드 설명

• participant와 completion 배열을 정렬하여 순서를 맞춥니다.
• 두 배열을 비교하며 첫 번째로 다른 이름을 반환합니다.
• 만약 모든 이름이 일치하면 participant 배열의 마지막 이름을 반환합니다. 이는 정렬된 completion 배열의 마지막 요소와 비교했을 때, 남는 한 명이기 때문입니다.

시간 복잡도

이 솔루션은 정렬에 의해 O(nlog⁡n)O(n \log n)O(nlogn)의 시간 복잡도를 가집니다. nnn은 participant 배열의 길이입니다.

마무리

이 방법은 배열 정렬과 비교를 사용하여 효율적이고 직관적인 솔루션을 제공합니다. 동명이인이 있어도 정확히 동작하도록 설계되었습니다.