공부블로그

TODAY TIL

안녕하세요, 오늘은 재미있는 코딩 문제를 함께 풀어보겠습니다. 이 문제는 센티라는 캐릭터가 마법의 뿅망치를 사용하여 자신보다 키가 큰 거인들을 줄여야 하는 상황입니다. 어떤 전략을 세우고 어떻게 코드를 구현했는지 차근차근 설명하겠습니다.

문제 설명

센티는 여행 중 거인의 나라에 도착했습니다. 그곳에는 자신보다 키가 크거나 같은 거인들이 많았는데, 센티는 이들을 마법의 뿅망치를 이용해 키를 줄이려 합니다. 마법의 뿅망치에 맞으면 키는 ⌊현재 키 / 2⌋로 줄어듭니다. 단, 키가 1이면 더 이상 줄어들지 않습니다. 이 마법의 뿅망치는 사용 횟수 제한이 있습니다.

목표: 센티가 마법의 뿅망치를 전략적으로 사용해 모든 거인이 센티보다 키가 작아지게 할 수 있는지를 판단하고, 그 과정에서 최소 사용 횟수를 출력합니다.

입력 형식

• 첫 번째 줄에 거인의 수 N, 센티의 키 HcentiH_{\text{centi}}Hcenti​, 마법의 뿅망치 사용 제한 T가 주어집니다.
• 두 번째 줄부터 N개의 줄에 각 거인의 키가 주어집니다.

출력 형식

• 마법의 뿅망치를 사용하여 모든 거인의 키가 HcentiH_{\text{centi}}Hcenti​보다 작다면 "YES"와 사용한 횟수를 출력합니다.
• 그렇지 않다면 "NO"와 뿅망치 사용 후 가장 큰 거인의 키를 출력합니다.

문제 풀이 접근법

1. 최대 힙을 이용한 거인 선택:
   • 거인들 중 가장 키가 큰 거인을 빠르게 선택하기 위해 최대 힙을 사용합니다.
   • Python의 heapq 모듈은 기본적으로 최소 힙이므로, 음수로 변환하여 최대 힙처럼 사용합니다.
2. 마법의 뿅망치 사용 전략:
   • 가장 키가 큰 거인을 때리고 줄어든 키를 다시 최대 힙에 넣습니다.
   • 키가 1인 경우는 줄일 수 없으므로 무시합니다.
   • 제한된 사용 횟수 T를 초과하지 않도록 합니다.
3. 결과 판단:
   • 마법의 뿅망치를 사용한 후, 모든 거인의 키가 HcentiH_{\text{centi}}Hcenti​보다 작으면 성공이고, 그렇지 않다면 실패입니다.

코드 구현

import heapq

# 입력 처리
N, H_centi, T = map(int, input().split())
giants = []

for _ in range(N):
    height = int(input())
    heapq.heappush(giants, -height)  # 최대 힙을 위해 음수로 저장

# 마법의 뿅망치 사용 횟수 카운트
use_count = 0

# 뿅망치 사용
while use_count < T and -giants[0] >= H_centi:
    tallest = -heapq.heappop(giants)
    
    if tallest == 1:
        # 키가 1이면 더 이상 줄어들 수 없음
        heapq.heappush(giants, -tallest)
        break
    
    # 뿅망치를 사용하여 키 줄이기
    new_height = tallest // 2
    heapq.heappush(giants, -new_height)
    use_count += 1

# 결과 확인
if -giants[0] < H_centi:
    print("YES")
    print(use_count)
else:
    print("NO")
    print(-giants[0])

코드 설명

1. 입력 처리:
   • 첫 번째 줄에서 거인의 수, 센티의 키, 마법의 뿅망치 사용 제한을 읽어옵니다.
   • 각 거인의 키를 음수로 변환하여 최대 힙에 저장합니다.
2. 반복문:
   • 최대 TTT번의 반복 동안 가장 키가 큰 거인을 선택하여 키를 절반으로 줄입니다.
   • 줄어든 키는 다시 힙에 삽입하여 다음 최댓값을 구할 수 있도록 합니다.
   • 키가 1인 거인은 더 이상 줄일 수 없으므로 바로 종료합니다.
3. 출력:
   • 모든 거인의 키가 센티보다 작아졌다면 YES와 사용 횟수를 출력합니다.
   • 그렇지 않다면 NO와 가장 큰 거인의 키를 출력합니다.

시간 및 공간 복잡도

• 시간 복잡도: O((T+N)log⁡N)O((T + N) \log N)O((T+N)logN)
• 공간 복잡도: O(N)O(N)O(N)

결론

이 문제는 우선순위 큐를 이용하여 가장 큰 값을 효율적으로 처리하는 방법과 제한된 자원을 최적화하여 사용하는 전략을 익히는 데 유용합니다. 블로그 포스팅을 통해 이와 같은 문제의 해결 방법을 체계적으로 학습해 보세요!

이제 여러분도 센티와 함께 거인의 나라를 정복해 보세요! 😊

TODAY TIL

안녕하세요! 여러분이 코딩 테스트에서 마주할 수 있는 흥미로운 문제를 소개합니다. 이 문제는 주어진 N×N  크기의 표에서 N번째로 큰 수를 찾아내는 것입니다. 표의 숫자들은 각자의 위에 있는 숫자보다 크도록 구성되어 있습니다. 예를 들어, N=5N = 5N=5일 때 다음과 같은 표가 있을 수 있습니다

12  7   9  15  5
13  8  11  19  6
21 10  26  31 16
48 14  28  35 25
52 20  32  41 49

이 표에서 다섯 번째로 큰 수를 찾아야 합니다.

입력 설명

• 첫 번째 줄에는 정수 NNN이 주어집니다 (1≤N≤1,5001 \leq N \leq 1,5001≤N≤1,500).
• 그 다음 NNN개의 줄에는 각 줄마다 NNN개의 정수가 주어집니다.
• 숫자들은 −109-10^9−109 이상 10910^9109 이하의 범위를 가지며, 모두 다릅니다.

출력 설명

• 프로그램은 NNN번째로 큰 수를 출력해야 합니다.

해결 전략

이 문제는 단순히 표를 정렬하여 NNN번째로 큰 수를 찾는 방식으로는 효율적이지 않습니다. NNN의 최대값이 1,500이므로 표에 있는 요소의 수는 최대 2,250,000개가 됩니다. 이 큰 데이터를 다룰 때 메모리와 시간 복잡도를 고려해야 합니다.

최적의 해결책은 다음과 같습니다:

1. 최소 힙(min-heap)을 사용하여 NNN개의 가장 큰 수를 유지합니다.
2. 한 줄씩 입력을 받아 즉시 처리하여 메모리 사용을 줄입니다.

코드 설명

이제 문제를 해결하는 코드를 단계별로 설명하겠습니다.

import sys
import heapq

# 입력을 빠르게 받기 위해 sys.stdin을 사용
input = sys.stdin

# N을 입력받음
N = int(input.readline().strip())
min_heap = []  # 최소 힙을 저장할 리스트

# N개의 행에 대해 각 숫자를 읽어들임
for _ in range(N):
    row = map(int, input.readline().split())  # 한 줄의 숫자를 공백 기준으로 분리하여 처리
    for num in row:
        # 힙의 크기가 N보다 작은 경우 숫자를 추가
        if len(min_heap) < N:
            heapq.heappush(min_heap, num)
        else:
            # N개의 숫자가 이미 힙에 있으면, 새로운 숫자가 최소값보다 큰 경우 교체
            if num > min_heap[0]:
                heapq.heappushpop(min_heap, num)

# 힙의 최솟값이 N번째로 큰 수가 됨
print(min_heap[0])

코드 설명 (더 자세히)

• heapq 모듈은 Python에서 힙 자료구조를 다룰 수 있는 모듈입니다. 이 문제에서는 최소 힙을 사용해 NNN개의 가장 큰 수를 유지합니다.
• sys.stdin.readline(): 표의 크기가 크기 때문에, 입력을 빠르게 받기 위해 input() 대신 sys.stdin.readline()을 사용했습니다. 이는 큰 입력을 더 효율적으로 처리합니다.
• 히프 유지: 힙에 NNN개의 요소만 유지하여 메모리를 절약합니다. 새로운 숫자가 힙의 최솟값보다 클 경우에만 추가하고 기존 최소값을 제거합니다.

예제 실행

입력 예시

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

이 경우, 다섯 번째로 큰 수는 35입니다. 프로그램은 이 값을 올바르게 출력합니다.

시간 및 공간 복잡도 분석

• 시간 복잡도: O(N2log⁡N)O(N^2 \log N)O(N2logN). 각 숫자마다 힙 연산이 O(log⁡N)O(\log N)O(logN)이고 총 N2N^2N2개의 숫자를 처리합니다.
• 공간 복잡도: O(N)O(N)O(N). 힙의 크기는 항상 NNN으로 유지되므로 메모리 사용량이 제한적입니다.

결론

이 접근법은 메모리와 시간 효율성을 모두 고려하여 NNN번째로 큰 수를 찾는 데 적합합니다. 만약 여러분이 비슷한 문제나 더 좋은 최적화 방법을 알고 있다면 댓글로 알려주세요!

이제 이 코드와 설명을 통해 여러분도 이 문제를 해결할 수 있기를 바랍니다. 코딩 테스트나 실무 프로젝트에서도 도움이 되길 바랍니다!

TODAY TIL

안녕하세요! 오늘은 배열에서 연속으로 나타나는 숫자를 제거하는 문제를 해결하는 방법을 소개하겠습니다. 이 문제는 배열 arr에 연속으로 나타나는 숫자가 있을 때, 중복된 숫자를 하나만 남기고 제거하여 반환하는 문제입니다. 문제 풀이를 단계별로 설명하겠습니다.

문제 설명

• 배열 arr가 주어집니다.
• 배열의 각 원소는 0부터 9까지의 숫자로 이루어져 있습니다.
• 연속적으로 나타나는 숫자를 하나만 남기고 제거한 배열을 반환합니다.
• 예를 들어:
  • arr = [1, 1, 3, 3, 0, 1, 1]이면 [1, 3, 0, 1]을 반환해야 합니다.
  • arr = [4, 4, 4, 3, 3]이면 [4, 3]을 반환해야 합니다.

제한사항

• 배열 arr의 크기: 최대 1,000,000
• 배열 arr의 원소: 0 이상 9 이하의 정수

문제 해결 접근법

1. 문제 이해 및 계획

• 주어진 배열을 순회하면서 연속된 숫자가 중복인지 확인하고, 중복이 아니면 결과 배열에 추가합니다.
• 각 숫자를 이전 숫자와 비교하여 중복 여부를 판단합니다.

2. 구현 단계

• 빈 배열 result를 초기화하여 중복되지 않은 숫자를 저장합니다.
• previous 변수로 이전 숫자를 저장합니다.
• arr의 각 원소를 순회하며, previous와 비교해 다를 경우에만 result에 추가합니다.

3. 코드 구현

다음은 문제를 해결하는 Python 코드입니다:

def solution(arr):
    result = []  # 결과를 저장할 배열
    previous = None  # 이전 원소를 저장할 변수

    for num in arr:
        # 이전 원소와 다를 때만 결과 배열에 추가
        if num != previous:
            result.append(num)
            previous = num  # 현재 숫자를 이전 숫자로 갱신

    return result

# 테스트 케이스
print(solution([1, 1, 3, 3, 0, 1, 1]))  # 출력: [1, 3, 0, 1]
print(solution([4, 4, 4, 3, 3]))        # 출력: [4, 3]

4. 코드 설명

• result 배열은 중복이 제거된 숫자들을 저장합니다.
• previous 변수는 이전 숫자를 저장해 연속 중복을 판단합니다.
• arr의 각 숫자를 순회하며 previous와 비교해 다르면 result에 추가하고, previous를 현재 숫자로 갱신합니다.

5. 시간 및 공간 복잡도

• 시간 복잡도: O(n)O(n)O(n) — 배열을 한 번 순회하므로 매우 효율적입니다.
• 공간 복잡도: O(n)O(n)O(n) — 중복이 제거된 결과 배열을 저장하기 때문입니다.

마무리

이 코드로 연속된 중복 숫자를 손쉽게 제거할 수 있습니다. 배열의 길이가 최대 1,000,000인 경우에도 효율적으로 동작합니다. 문제를 풀면서 알고리즘의 효율성과 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

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

문제 설명

수많은 마라톤 선수들이 마라톤에 참여했는데, 단 한 명의 선수를 제외하고는 모두 완주했습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 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 배열의 길이입니다.

마무리

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

TODAY TIL

안녕하세요! 이번 포스팅에서는 비밀번호 찾기 문제 와 관련된 흥미로운 코딩 문제를 다뤄보겠습니다. 단계적으로 설명하고 코드 구현을 공유합니다.

문제 설명

창영이는 민균이의 컴퓨터에서 비밀번호가 포함된 텍스트 파일을 얻었습니다. 이 파일에는 여러 단어가 줄마다 적혀있으며, 민균이의 비밀번호는 특정 조건을 만족해야 합니다:

1. 목록에 포함된 단어의 길이는 모두 홀수입니다.
2. 비밀번호를 뒤집은 형태의 문자열도 목록에 포함되어 있습니다.

목표는 목록에서 비밀번호를 찾아 비밀번호의 길이와 가운데 글자를 출력하는 것입니다.

문제 해결을 위한 단계별 접근 방법

1단계: 입력받기

• 첫째 줄에 단어의 개수 NNN이 주어집니다.
• 이후 NNN개의 단어를 입력받아 words 리스트에 저장합니다.

# 입력 받기
N = int(input())
words = [input().strip() for _ in range(N)]

2단계: 단어와 뒤집은 단어 비교

• 모든 단어에 대해 해당 단어의 뒤집힌 형태가 리스트에 있는지 확인합니다.
  • 예를 들어, 단어가 "tulipan"이라면, 뒤집은 형태는 "napilut"입니다.
• 이를 위해 for 루프를 사용해 words 리스트의 각 단어를 순회하며 뒤집힌 단어가 words에 있는지 검사합니다.

# 비밀번호 찾기
password = ""
for word in words:
    reversed_word = word[::-1]  # 단어 뒤집기
    if reversed_word in words:  # 뒤집은 단어가 목록에 있는지 확인
        password = word
        break

3단계: 비밀번호 길이와 가운데 글자 찾기

• 비밀번호를 찾았다면:
  • 길이는 len(password)로 구할 수 있습니다.
  • 가운데 글자는 (길이 // 2) 인덱스를 통해 찾습니다.

# 비밀번호 길이와 가운데 글자 찾기
length = len(password)
middle_char = password[length // 2]

4단계: 결과 출력

• 비밀번호의 길이와 가운데 글자를 한 줄에 출력합니다.

# 결과 출력
print(length, middle_char)

전체 코드

아래는 전체 코드를 정리한 것입니다.

# 1. 입력 받기
N = int(input())
words = [input().strip() for _ in range(N)]

# 2. 비밀번호 찾기
password = ""
for word in words:
    reversed_word = word[::-1]
    if reversed_word in words:
        password = word
        break

# 3. 비밀번호 길이와 가운데 글자 찾기
length = len(password)
middle_char = password[length // 2]

# 4. 결과 출력
print(length, middle_char)

예제와 결과

예제 입력

4
tulipan
napilut
apple
banana

예제 출력

7 i

요약

이 문제는 문자열을 뒤집어 비교하는 방법과 문자열의 가운데 글자를 찾는 기본적인 접근 방식을 통해 해결할 수 있습니다. 단계별로 문제를 나누고 각 단계에서 필요한 작업을 순차적으로 구현하면 쉽게 답을 구할 수 있습니다.

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

 오늘은 파이썬에서 자주 사용하는 딕셔너리와 for문, replace를 쉽게 이해하고 활용하는 방법을 프로그래머스에 관련 문제를 풀어보면서 정리하려고 합니다. 이 글을 통해 딕셔너리의 키와 값, 그리고 이를 활용하는 방법을 알기 쉽게 설명해 보겠습니다.

문제 상황: 숫자와 영단어의 변환

코딩을 하다 보면 숫자를 영단어로 바꾸거나, 영단어를 숫자로 바꿔야 하는 상황이 생깁니다. 예를 들어 "one4seveneight" 같은 문자열이 있으면 "1478"로 바꾸고 싶을 때, 파이썬에서 딕셔너리를 활용해 쉽게 해결할 수 있습니다.

1. 딕셔너리의 이해: 키와 값

딕셔너리는 두 가지 요소로 이루어져 있습니다:

• 키 (key): 특정 값을 찾는 데 사용되는 이름입니다.
• 값 (value): 키에 연결된 실제 데이터입니다.

예를 들어, 숫자와 그에 해당하는 영단어를 딕셔너리로 표현해 보겠습니다.

number_dict = {
    "zero": "0",
    "one": "1",
    "two": "2",
    "three": "3",
    "four": "4",
    "five": "5",
    "six": "6",
    "seven": "7",
    "eight": "8",
    "nine": "9"
}

이 딕셔너리에서 키는 "zero", "one" 같은 영단어이고, 값은 "0", "1" 같은 숫자로 이루어진 문자열입니다.

2. 딕셔너리와 for문: 키와 값을 쌍으로 사용하기

 딕셔너리를 반복문 for에서 사용할 때, 키만 가져올 수도 있지만, items() 메서드를 사용하면 키와 값을 쌍으로 가져올 수 있습니다.

예를 들어, for word, digit in number_dict.items():라고 쓰면 word는 키, digit는 값이 됩니다. 따라서, number_dict의 "zero"와 "0"처럼 한 쌍씩 꺼내 올 수 있습니다.

이 구조를 활용해 문자열 속의 영단어를 숫자로 바꿀 수 있습니다.

3. replace() 함수로 변환하기

이제 replace() 함수를 활용해 봅시다. replace(찾을 문자열, 바꿀 문자열) 형태로 쓰며, 문자열에서 찾을 부분을 바꿀 부분으로 교체해 줍니다.

예를 들어 s.replace(word, digit)로 for문 안에서 영단어를 숫자로 바꾸는 작업을 할 수 있습니다.

최종 코드 예시

이제 모든 내용을 종합해서 최종 코드를 작성해 보겠습니다. 예를 들어, "one4seveneight"을 "1478"로 바꾸는 코드입니다:

def solution(s):
    # 숫자 영단어 변환표
    number_dict = {
        "zero": "0", "one": "1", "two": "2", "three": "3", "four": "4",
        "five": "5", "six": "6", "seven": "7", "eight": "8", "nine": "9"
    }

    # for문과 replace로 변환하기
    for word, digit in number_dict.items():
        s = s.replace(word, digit)

    return int(s)  # 숫자 형태로 변환 후 반환

이 코드는 for문을 통해 딕셔너리의 각 키와 값을 가져와 replace로 문자열에서 단어를 숫자로 교체한 후, 숫자로 반환합니다.

정리

• 딕셔너리는 키-값 쌍으로 구성되어 있습니다.
• **for word, digit in dict.items()**를 사용하면 키와 값을 한 쌍씩 가져올 수 있습니다.
• replace() 함수는 찾을 부분과 바꿀 부분을 인자로 받아 문자열을 교체합니다.

이 글을 통해 딕셔너리와 for문, 그리고 replace의 활용법을 잘 이해하셨길 바랍니다! 더 쉬운 설명이나 추가 질문이 있다면 언제든지 댓글로 남겨 주세요. 😊