코딩테스트

[Python] 백준 코테 연습 - 구현

you__me 2025. 1. 19. 15:32

 

소가 길을 건너간 이유 - 브론즈 1

https://www.acmicpc.net/problem/14467

N = int(input())

cow = {}
ans = 0

for _ in range(N):
    a, b = map(int, input().split())
    if a in cow:
        if cow[a] != b:
            cow[a] = b
            ans += 1
    else:
        cow[a] = b

print(ans)

 

 

전구 - 브론즈 2

https://www.acmicpc.net/problem/21918

N, M = map(int, input().split())
bolt = list(map(int, input().split()))

for _ in range(M):
    command = list(map(int, input().split()))
    if command[0] == 1:
        bolt[command[1] - 1] = command[2]
    elif command[0] == 2:
        for i in range(command[1] -1, command[2]):
            bolt[i] = bolt[i] ^ 1  # XOR 연산
    elif command[0] == 3:
        for i in range(command[1] - 1, command[2]):
          bolt[i] = 0
    else:
        for i in range(command[1] - 1, command[2]):
          bolt[i] = 1

print(*bolt)
  • ^ 비트 연산자(XOR)을 이용해서 0과 1을 바꾸었다.
  • 런타임 에러(TypeError) 발생 -> bolt[commadn[1] -1 commadn[2]] = 0 리스트 값을 한번에 바꾸는 연산은 안됨..

 

🐜 기적의 매매법 🐜 - 실버 5

https://www.acmicpc.net/problem/20546

cash = int(input())
securities = list(map(int, input().split()))

a_cash = cash
a_secutiry = 0

b_cash = cash
b_security = 0

for i in range(len(securities)):
    a_secutiry += a_cash // securities[i]
    a_cash %= securities[i]

for i in range(3, len(securities)):
    if securities[i-3]>securities[i-2]>securities[i-1]>securities[i]:
        b_security += b_cash // securities[i]
        b_cash %= securities[i]
    if securities[i-3]<securities[i-2]<securities[i-1]<securities[i]:
        b_cash += b_security * securities[i]
        b_security = 0


if a_secutiry*securities[-1]+a_cash > b_security*securities[-1]+b_cash:
    print('BNP')

elif a_secutiry*securities[-1]+a_cash < b_security*securities[-1]+b_cash:
    print('TIMING')
else:
    print('SAMESAME')

 

 

기상캐스터 - 실버 5

https://www.acmicpc.net/problem/10709

H, W = map(int, input().split())
cloud = list(input() for _ in range(H))
next_cloud = [[-1]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if cloud[i][j] == 'c':
            next_cloud[i][j] = 0
        elif 'c' in cloud[i][:j]:
            next_cloud[i][j] = j - cloud[i][:j].rindex('c')  # 가장 오른쪽의 해당 문자를 가진 index 반환

for i in range(H):
    print(*next_cloud[i])
  • c가 있는 곳의 위치를 찾기 위해 rindex 연산자를 사용했다.

 

NBA 농구 - 실버 3

https://www.acmicpc.net/problem/2852

import datetime
N = int(input())

team_dic = {'1': 0, '2': 0}
ans_1 = datetime.datetime.strptime('00:00', '%M:%S')
ans_2 = datetime.datetime.strptime('00:00', '%M:%S')

time = datetime.datetime.strptime('00:00', '%M:%S')

a , b = input().split()
team_dic[a] += 1
time = datetime.datetime.strptime(b, '%M:%S')

for i in range(N-1):
    a , b = input().split()
    
    if team_dic['1'] > team_dic['2']:
        ans_1 += datetime.datetime.strptime(b, '%M:%S') - time
    elif team_dic['1'] < team_dic['2']:
        ans_2 += datetime.datetime.strptime(b, '%M:%S') - time

    team_dic[a] += 1
    time = datetime.datetime.strptime(b, '%M:%S')

if team_dic['1'] > team_dic['2']:
    ans_1 += datetime.datetime.strptime('48:00', '%M:%S') - time
elif team_dic['1'] < team_dic['2']:
    ans_2 += datetime.datetime.strptime('48:00', '%M:%S') - time
      

print(ans_1.strftime('%M:%S'))
print(ans_2.strftime('%M:%S'))
  • 시간 계산을 편하게 하기 위해 datetime 객체를 사용했다. strptime, strftime 함수를 이용해서 문자열 및 datetime 객체간 변환을 할 수 있다.

 

달팽이 - 실버3

https://www.acmicpc.net/problem/1913

n = int(input())
num = int(input())
dx = [-1,0,1,0]
dy = [0,1,0,-1]  # 상, 우, 하, 좌 순서
graph = [[0]*n for _ in range(n)]
number = 2
x = n//2
y = n//2
graph[x][y] = 1
repeat = 1
i = 0 # dx,dy 가리키는 변수

answer = [x+1,y+1]
while x!=0 or y !=0:
   flag = 0
   for _ in range(2):
      for _ in range(repeat):
         x += dx[i]
         y += dy[i]
         graph[x][y] = number
         if number == num:  # 위치를 찾고자 하는 자연수이면 answer에 위치 저장
            answer = [x+1,y+1] 
         if x == 0 and y == 0: 
            flag = 1
            break
         number += 1
      if flag == 1: break
      i = (i+1)%4
   repeat += 1

for i in graph:
   print(*i)
   
print(*answer)
  • 시작점(N//2, N//2) 위치에서 num을 하나씩 증가하며 배열에 넣어준다.
  • 상, 우, 하, 좌 순으로 움직이며, 상 - 우 - 하,하 - 좌,좌 - 상,상,상... 등 두 번 방향을 바꿀 때마다 이동 횟수가 1씩 늘어난다.
  • 반복하며 flag=1일 때, 즉 마지막 숫자를 채울 때 빠져나온다.
  • https://imzzan.tistory.com/247
 

[백준][Python] 1913번 달팽이

1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를

imzzan.tistory.com

 

랭킹 전 대기열 - 실버2

https://www.acmicpc.net/problem/20006

p, m = map(int, input().split())
rooms = {}
players = {}
a = 0  # 새 방 생성을 판단하기 위한 변수

for _ in range(p):
    l, n = input().split()
    players[n] = int(l)
    
    for room in rooms:
        if len(rooms[room]) < m and int(l) - 10 <= players[room] <= int(l)+10:
            rooms[room].append(n)
            a = 1
            break

    if a == 0:
        rooms[n] = [n]
    a = 0
    
# print(rooms)
# print(players)
for key in rooms.keys():
    if len(rooms[key]) == m:
        print('Started!')
        name = sorted(rooms[key])
        for i in range(len(name)):
            print(players[name[i]], name[i])
    else:
        print('Waiting!')
        name = sorted(rooms[key])
        for i in range(len(name)):
            print(players[name[i]], name[i])
  • 질문게시판 보고 다양한 반례를 넣어본 후 풀기...문제에서 입력 예시가 부족해서 헷갈렸다.
  • 닉네임은 중복되지 않으므로 닉네임 및 레벨을 저장하는 player 딕셔너리와, 방을 저장하는 room 딕셔너리를 활용하여 해결했다.

 

한 줄로 서기 - 실버2

https://www.acmicpc.net/problem/1138

N = int(input())
people = list(map(int, input().split()))
answer = [0] * N

for i in range(N):
    cnt = 0  # 앞에 있는 사람 수
    for j in range(N):
        if cnt == people[i] and answer[j] == 0:
            answer[j] = i + 1
            break
        elif answer[j] == 0:
            cnt += 1


print(*answer)
  • 키가 1인 사람부터, 앞에 있는 사람의 수(people[i])가 cnt와 일치할 때 알맞은 위치에 들어간다.
  • cnt는 answer[j] 가 0일 때만 +1 한다. 0이 아닌 경우는 키가 작은 사람이 위치한 경우

 

배열 돌리기 - 실버1

 

https://www.acmicpc.net/problem/17276

import copy
T = int(input())

for _ in range(T):
    N, D = map(int, input().split())
    nums = [list(map(int, input().split())) for _ in range(N)]
    if D<0:
        D += 360

    next_nums = copy.deepcopy(nums)
    for _ in range(D//45):
        for i in range(N):
            for j in range(N):
                if i == j:
                    next_nums[i][N//2] = nums[i][j]
                elif j == N//2:
                    next_nums[i][N-i-1] = nums[i][j]
                elif j == N-i-1:
                    next_nums[N//2][j] = nums[i][j]
                elif i == N//2:
                    next_nums[j][j] = nums[i][j]
        nums = copy.deepcopy(next_nums)

    for i in range(N):
        for j in range(N):
            print(next_nums[i][j], end=' ')
        print()
  • D가 음수인 경우는 D를 반대로 360+=D한 경우와 같으므로 양수로 바꾼 후 무조건 시계방향으로만 계산한다.
  • 주대각선, 가운데 열, 부대각선, 가운데 행에 대하여 각각 경우를 나누어 직접 값을 옮겨주었다.
  • deepcopy 이용.

 

배열 돌리기1 - 골드5

https://www.acmicpc.net/problem/16926

from sys import stdin
from collections import deque

N, M, R = map(int, stdin.readline().split())

matrix = []
answer = [[0]*M for _ in range(N)]
deq = deque()

for i in range(N):
    matrix.append(list(stdin.readline().split()))

loops = min(N, M) // 2
for i in range(loops):
    deq.clear()  # 1차원 배열 변환
    deq.extend(matrix[i][i:M-i]) # 위쪽
    deq.extend([row[M-i-1] for row in matrix[i+1:N-i-1]])  # 오른쪽
    deq.extend(matrix[N-i-1][i:M-i][::-1])  # 아래쪽
    deq.extend([row[i] for row in matrix[i+1:N-i-1]][::-1])  # 왼쪽
    
    deq.rotate(-R)
    
    # 결과를 다시 2차원 배열에 저장
    for j in range(i, M-i):                 # 위쪽
        answer[i][j] = deq.popleft()
    for j in range(i+1, N-i-1):             # 오른쪽
        answer[j][M-i-1] = deq.popleft()
    for j in range(M-i-1, i-1, -1):           # 아래쪽
        answer[N-i-1][j] = deq.popleft()  
    for j in range(N-i-2, i, -1):           # 왼쪽
        answer[j][i] = deq.popleft()    

for line in answer:
    print(" ".join(line))
 

[Python] 백준 16926번: 배열 돌리기 1

백준 16926번: 배열 돌리기 1 문제 풀이에 대한 기록입니다.

velog.io

 

 

빗물 - 골드 5

https://www.acmicpc.net/problem/14719

h, w = map(int, input().split())
world = list(map(int, input().split()))

ans = 0
for i in range(1, w - 1):
    left_max = max(world[:i])
    right_max = max(world[i+1:])

    compare = min(left_max, right_max)

    if world[i] < compare:
        ans += compare - world[i]

print(ans)
  • 처음에는 시작 블록과 비교해서 시작 블록과 같거나 높은 블록을 만날 때 계산했는데, 시작 블록이 가장 높을 수도 있음을 고려해야함.
  • 그냥 위 풀이와 같이 각 index 별로 하나씩 계산하는게 더 쉬운 듯....
  • https://seongonion.tistory.com/115
 

[백준] 14719번 빗물 - 파이썬(Python)

문제 (링크) https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미

seongonion.tistory.com

 

 

달력 - 골드5

https://www.acmicpc.net/problem/20207

N = int(input())

calender = [0]*366  # 일정 저장
ans_list = []  # 일정이 있는 날 리스트
sub_list = []
ans = 0

for _ in range(N):
    S, E = map(int, input().split())
    for i in range(S, E+1):
        calender[i] += 1


for n in calender:
    if n==0:
        if sub_list:
            ans_list.append(sub_list)
            sub_list = []
    else:
        sub_list.append(n)

if sub_list:
    ans_list.append(sub_list)

for num in ans_list:
    ans += len(num)* max(num)

print(ans)

 

 

 

폴더 정리 - 골드3

https://www.acmicpc.net/problem/22860

import sys
N, M = map(int, sys.stdin.readline().split())
dic = dict()

def find_file(start_path):
    global num
    stack = [start_path]
    while stack:
        cur_path = stack.pop()
        for i in dic.get(cur_path):
            if i in dic:
                stack.append(i)
            if i not in dic:
                file_list.add(i)
                num += 1
    return

for i in range(N + M):
    P, F, C = map(str, sys.stdin.readline().split())
    if P not in dic:
        dic[P] = []
    if C=='1' and F not in dic:
        dic[F] = []

    dic[P].append(F)

Q = int(sys.stdin.readline())
for i in range(Q):
    visited = []
    file_list = set()
    num = 0
    path = list(map(str, sys.stdin.readline().rstrip().split('/')))
    find_file(path[-1])
    print(len(file_list), num)
 

백준 22860번 폴더 정리(small) 문제 풀이(Python, 구현, DFS, Hash, Gold 3)

백준 22860번 폴더 정리(small) 문제 바로가기이 문제는 되게 복잡해 보이지만 단순하게 보면 입력에서 주어지는 값들을 토대로 트리 구조를 만들고, 여러 개의 쿼리문에 대한 출력으로 해당 폴더

velog.io

 

 

# 회고

 

DFS오랜만....단순 구현만 하다가 DFS를 생각 못했다.

딕셔너리에 저장하는 방식까지만 맞았따.