TIL 코딩공장

백준 파이썬 공부 2025.03.17
5430번 AC (골드 5)

1. 문제
선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. 
AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 
이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 
배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 
예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 
예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.
각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. 
p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

3. 출력
각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 
만약, 에러가 발생한 경우에는 error를 출력한다.

4. 문제 해설
그냥 파이썬에서 제공해주는 
deque 라이브러리의 reverse와 popleft를 이용하여 코드를 작성했다.
그러나 시간초과 엔딩..

>>>코드1. 시간초과

from collections import deque
import sys

def AC(calculation):
    for RD in calculation:
        if RD == 'R':
            num.reverse()
        elif RD == 'D':
            if num:
                num.popleft()
            else:
                print("error")
                return
    print(list(num))

T = int(sys.stdin.readline().strip())
for _ in range(T):
    calculation = sys.stdin.readline().strip()
    n = int(sys.stdin.readline().strip())
    arr = sys.stdin.readline().strip()
    
    if arr == "[]":
        num = deque()
    else:
        num = deque(map(int, arr.strip("[]").split(',')))
    AC(calculation)

보기에 reverse가 시간이 많이 들기 때문에 
reverse 가 홀수번 선언되면 pop을
reverse 가 짝수번 선언되면 popleft를 시행한다.

>>>코드 2.

from collections import deque
import sys

def AC(calculation):
    flag = 0
    for RD in calculation:
        if RD == 'R':
            if flag:
                flag = 0
            else:
                flag = 1
        elif RD == 'D':
            if num:
                if flag:
                    num.pop()
                else:
                    num.popleft()
            else:
                print("error")
                return
    if num:
        if flag:
            num.reverse()
        print("[" + ",".join(num) + "]")
    else:
        print("[]")
    
T = int(sys.stdin.readline().strip())
for _ in range(T):
    calculation = sys.stdin.readline().strip()
    n = int(sys.stdin.readline().strip())
    arr = sys.stdin.readline().strip()
    
    if arr == "[]":
        num = deque()
    else:
        num = deque(arr.strip('[]').split(','))
    AC(calculation)

어우 씨
분명 구조는 맞는데 계속 헤맸다.
일단 덱을 숫자로 저장 한 후 그냥 리스트 출력을 했을 시, 틀렸습니다로 나오는데,
이는 리스트 출력시 ',' 쉼표 뒤에 공백이 존재하기 때문에 틀린 것으로 나온다.

그래서 덱을 숫자로 저장한 후 join으로 출력을 했을경우, Type error가 나온다.
이는 덱을 숫자로 저장했기 때문이라, 덱을 문자열 배열로 저장하도록하면 맞게 된다.

5. 문제 링크
https://www.acmicpc.net/problem/5430

백준 파이썬 공부 2024.11.14
1389번 케빈 베이컨의 6단계 법칙 (실버 1)

1) 문제
케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 
케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 
천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 
최백준과 김선영은 같이 Startlink를 창업했다. 
김선영과 김도현은 같은 학교 동아리 소속이다. 
김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 
즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 
케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 
따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 
따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 
따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 
4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 
5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

2) 입력
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 
둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 
친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. 
A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 
친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 
또, 모든 사람은 친구 관계로 연결되어져 있다. 
사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.

3) 출력
첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 
그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

4) 코드 풀이
BFS 방식(너비 우선 탐색)을 이용하여 풀이한다.

- n+1 길이의 이중리스트 arr 생성
- 입력받은 관계의 인덱스에 해당하는 리스트에 서로의 관계 저장
- 관계의 경로 길이를 계산할 n+1 크기의 visit 리스트 생성 및 -1로 초기화
- 덱을 생성하여, 시작지점의 리스트 값을 0으로 설정
- visit 리스트에서 -1인 사람까지의 경로 확인 및 길이 계산
- 하나씩 popleft하면서, 해당 노드 인덱스의 관계(arr)로 다음 노드를 확인
- 해당 노드의 visit 리스트 값이 -1이면(해당 노드에 접근한적이 없으면) 
그전 노드 경로까지의 케빈 베이컨의 값 +`1 & 다음 노드 덱에 추가
- visit 리스트 값의 총합 == 해당 사람(노드)의 케빈 베이컨의 값
- 케빈 베이컨의 값들 중 최소값을 가진 사람 반환

5) 코드

from collections import deque

n, m = map(int, input().split())
friend = [[] for _ in range(n+1)]

# 관계 입력받기
for i in range(m):
    a, b = map(int, input().split())
    # 관계 friend 리스트에 저장
    friend[a].append(b)
    friend[b].append(a)

# 경로 찾기 함수
def BFS(start):
    # 기본 설정1. 해당 start 노드로부터의 관계 길이 저장할 리스트 visit
    visit = [-1] * (n+1)
    # 현재 위치한 노드를 저장할 deque
    queue = deque()
    # 시작 노드 설정
    queue.append(start)
    # 시작 노드 0으로 초기화
    visit[start] = 0
    
    # 모든 노드를 돌 때까지 (덱이 빌 때까지)
    while queue:
        # 현재 노드 popleft
        node = queue.popleft()
        # 현재 노드와 관계가 있는 다음 노드 확인
        for next_node in friend[node]:
            # 만약 한번도 가지 않은 노드라면 현재 노드까지의 관계 길이 +1
            if visit[next_node] == -1:
                visit[next_node] = visit[node] + 1
                queue.append(next_node)
    # 케빈 베이컨의 수 계산 (인덱스 0의 값이 -1이므로 + 1)
    kevin = sum(visit) + 1
    return kevin
                
# 각 사람의 케빈 베이컨의 수 계산 및 비교 시작
min = float("INF")
ans = 0
for person in range(1, n+1):
    if BFS(person) < min:
        min = BFS(person)
        ans = person
# 출력
print(ans)

6) 문제링크
https://www.acmicpc.net/problem/1389

20240329 백준 파이썬 공부
2346번 풍선 터뜨리기

1. 문제
1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 
단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 
각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 
이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 
다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 
양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 
이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 
이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

2. 입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 
다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 
종이에 0은 적혀있지 않다.

3. 출력
첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

>>>코드1. from collections import deque의 rotate 함수를 이용해서 풀이 + 풍선번호를 저장한 덱을 따로 생성해서 풀이

from collections import deque
n = int(input()) # 풍선의 개수 입력받기
num = deque(range(1, n+1)) # 각 풍선의 번호를 의미하는 리스트
balloon = deque(map(int, input().split())) # 풍선 안에 든 번호 입력받기
result = [] # 터진 풍선의 번호를 저장할 리스트 생성
while balloon:
    p = balloon.popleft() # 첫번째 풍선을 터트리고 그 안의 번호 저장
    result.append(num.popleft()) # 터진 풍선의 번호 저장
    if p > 0: # p가 0보다 크다면, 덱이 왼쪽으로 회전(앞으로 감) == -p+1
        balloon.rotate(-p+1)
        num.rotate(-p+1)
    elif p < 0: # p가 0보다 작다면, 덱이 오른쪽으로 회전(뒤로 감) == -p
        balloon.rotate(-p)
        num.rotate(-p)
print(*result) # 결과 출력

>>>코드2. 동일하게 하되, enumerate 함수를 이용하여, 따로 리스트를 만들지 않고 풀이

from collections import deque
n = int(input())
num = deque(range(1, n+1))
balloon = deque(enumerate(map(int, input().split())))
result = []
while balloon:
    index, p = balloon.popleft()
    result.append(index+1)
    if p > 0:
        balloon.rotate(-p+1)
    elif p < 0:
        balloon.rotate(-p)
print(*result)

>>> enumerate() 함수
- 해당 함수는 리스트의 각 원소를 (인덱스, 원소)의 꼴로 이루어진 튜플로 바꾸어준다.

>>>문제링크
https://www.acmicpc.net/problem/2346

20240328 백준 파이썬 공부
28279번 덱 2

1. 문제
정수를 저장하는 덱을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여덟 가지이다.

- 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
- 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
- 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
- 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
- 5: 덱에 들어있는 정수의 개수를 출력한다.
- 6: 덱이 비어있으면 1, 아니면 0을 출력한다.
- 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
- 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.

2. 입력
첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.
출력을 요구하는 명령은 하나 이상 주어진다.

3. 출력
출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.

>>>코드. from collections import deque의 함수들을 사용해보았다.

import sys
from collections import deque
deq = deque()
for _ in range(int(input())):
    com = list(map(int, sys.stdin.readline().split()))
    if com[0] == 1:
        deq.appendleft(com[1])
    elif com[0] == 2:
        deq.append(com[1])
    elif com[0] == 3:
        if len(deq) == 0:
            print(-1)
        else:
            print(deq.popleft())
    elif com[0] == 4:
        if len(deq) == 0:
            print(-1)
        else:
            print(deq.pop())
    elif com[0] == 5:
        print(len(deq))
    elif com[0] == 6:
        if len(deq) == 0:
            print(1)
        else:
            print(0)
    elif com[0] == 7:
        if len(deq) == 0:
            print(-1)
        else:
            print(deq[0])
    elif com[0] == 8:
        if len(deq) == 0:
            print(-1)
        else:
            print(deq[-1])

>>>문제링크
https://www.acmicpc.net/problem/28279

20240327 백준 파이썬 공부
18258번 큐 2

1. 문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

2. 입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 
둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 
문제에 나와있지 않은 명령이 주어지는 경우는 없다.

3. 출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

>>>코드1. 실패 시간초과

import sys
queue = []
for _ in range(int(input())):
    command = list(sys.stdin.readline().split())
    if command[0] == 'push':
        queue.append(command[1])
    elif command[0] == 'pop':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[0])
            queue.pop(0)
    elif command[0] == 'size':
        print(len(queue))
    elif command[0] == 'empty':
        if len(queue) == 0:
            print(1)
        else:
            print(0)
    elif command[0] == 'front':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[0])
    elif command[0] == 'back':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[-1])

pypy3와 sys.stdin.readline을 사용했지만 시간초과가 나온다

>>>코드2. 성공 >> from collections import deque 사용

import sys
from collections import deque
queue = deque()
for _ in range(int(input())):
    command = list(sys.stdin.readline().split())
    if command[0] == 'push':
        queue.append(command[1])
    elif command[0] == 'pop':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue.popleft())
    elif command[0] == 'size':
        print(len(queue))
    elif command[0] == 'empty':
        if len(queue) == 0:
            print(1)
        else:
            print(0)
    elif command[0] == 'front':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[0])
    elif command[0] == 'back':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[-1])

>>> from collections import deque 사용법
1. 선언
덱 이름 = deque(데이터)

2. 함수 목록
- append(): 오른쪽에 개체 추가
- appendleft(): 왼쪽에 개체 추가
- pop(): 오른쪽에 개체 반환 및 삭제
- popleft(): 왼쪽에 개체 반환 및 삭제
- maxlen(): 큐의 길이 반환
- extend(리스트): 왼쪽에 데이터 추가 확장
- extendleft(리스트): 오른쪽에 데이터 추가 확장
- clear(): 모든 개체 삭제
- remove(개체): 특정 개체 삭제
- reverse(): 데이터 뒤집기
- rotate(숫자): 숫자만큼 데이터 회전(오른쪽으로 밀기) 

>>>문제링크
https://www.acmicpc.net/problem/18258