[Python] 백준 코테 연습 - 자료구조

 

큐 - 실버4

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

import queue

q = queue.Queue()

for _ in range(int(input())):
    a = list(input().split())
    if a[0]=='push':
        q.put(int(a[1]))
    elif a[0]=='front':
        if q.empty():
            print(-1)
        else:
            print(q.queue[0])
    elif a[0]=='back':
        if q.empty():
            print(-1)
        else:
            print(q.queue[-1])
    elif a[0]=='size':
        print(q.qsize())
    elif a[0]=='pop':
        if q.empty():
            print(-1)
        else:
            print(q.get())
    elif a[0]=='empty':
        if q.empty():
            print(1)
        else:
            print(0)

• 시간초과

from collections import deque
import sys


N = int(sys.stdin.readline().strip())

dq = deque()

for i in range(N):
  cmd = sys.stdin.readline().strip().split()
  if cmd[0] == 'push':
    dq.append(cmd[1])
  elif cmd[0] == 'pop':
    if len(dq) != 0:
      print(dq.popleft())
    else:
      print(-1)
  elif cmd[0] == 'size':
    print(len(dq))
  elif cmd[0] == 'empty':
    if len(dq) == 0:
      print(1)
    else:
      print(0)
  elif cmd[0] == 'front':
    if len(dq) != 0:
      print(dq[0])
    else:
      print(-1)
  elif cmd[0] == 'back':
    if len(dq) != 0:
      print(dq[-1])
    else:
      print(-1)

• python 자료구조 deque가 queue보다 빠르다.
• 라이브러리 사용안하는 경우..그냥 리스트로 구현해도 통과된다.

 

---

좋은 단어 - 실버 4

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

from collections import deque

N = int(input())
ans = 0

for _ in range(N):
    name = deque()
    word = input()
    for i in word:
        if len(name) > 0:
            if i=='A' and name[-1]=='A':
                name.pop()
            elif i=='B' and name[-1]=='B':
                name.pop()
            else:
                name.append(i)
        else:
            name.append(i)

    if len(name) == 0:
        ans += 1

print(ans)

• 리스트 절단은 시간 초과

 

---

빈도 정렬 - 실버3

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

from collections import Counter

N, C = map(int, input().split())
word = list(map(int, input().split()))

# 등장 순서 기록 (최초 등장 위치 저장)
first_occurrence = {num: word.index(num) for idx, num in enumerate(word)}
# print(first_occurrence)

# 빈도수 계산
word_num = Counter(word)

# 정렬: 1) 빈도수 내림차순, 2) 처음 등장한 순서 기준 오름차순
word_num = sorted(word_num.items(), key=lambda pair: (-pair[1], first_occurrence[pair[0]]))

# 출력
for num, freq in word_num:
    print((str(num) + ' ') * freq, end='')

• Counter 메소드 사용.
• 두 번째 정렬 조건인 등장 순서를 기록하는 first_occurrence 딕셔너리와 빈도수 객체를 저장했다.
• 찾아보니까 굳이 Counter를 안쓰고 정렬할 때 count() 를 사용하면 될 것 같다.

 

---

생태학 - 실버2

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

import sys
input=sys.stdin.readline

trees = dict()
total = 0

while(True):
    tree = input().rstrip()

    if tree=='':
        break

    if tree in trees:
        trees[tree] += 1
    else:
        trees[tree] = 1
    total += 1

sorted_trees= dict(sorted(trees.items()))
for i in sorted_trees:
    print("%s %.4f" %(i, trees[i]/total * 100))

• 시간초과 안나도록 sys를 이용해 입력받기

 

---

N번째 큰 수 - 실버3

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

import heapq as hq
import sys
input = sys.stdin.readline

n = int(input())
heap = []

init_numbers = list(map(int, input().split()))
for num in init_numbers:
    hq.heappush(heap, num)

for i in range(n-1):
    numbers = list(map(int, input().split()))
    for num in numbers:
        if heap[0] < num:
            hq.heappush(heap, num)
            hq.heappop(heap)

print(heap[0])

• 일반적으로 풀면 메모리 초과 오류 발생.
• heap을 이용해서 N번째로 큰 수만 저장 후 비교를 반복한다.
• https://naroforme.tistory.com/entry/%EB%B0%B1%EC%A4%80-2075%EB%B2%88-N%EB%B2%88%EC%A7%B8-%EC%88%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] 2075번 : N번째 수 파이썬

 

 

---

창고 다각형 - 실버2

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

n = int(input())

lst = []
result = 0
for i in range(n) :
    a,b = map(int,input().split())
    lst.append([a,b])
#기둥을 x축 순으로 정렬한다. 
lst.sort()

#가장 높은 기둥의 번호를 알아낸다. 
i = 0
for l in lst :
    if l[1] >result :
        result = l[1]
        idx = i
    i += 1

#초기 높이는 첫번째 기둥의 높이 
height = lst[0][1]

#최대 높이전까지 돌면서 다음 기둥이 현재보다 높으면 
#result에 현재의 면적을 계산해서 더해주고 높이를 다음 기둥으로 갱신한다.
for i in range(idx) :
    if height < lst[i+1][1] :
        result += height * (lst[i+1][0]-lst[i][0])
        height = lst[i+1][1]
    #아니면 그냥 현재면적을 더해준다. 
    else :
        result += height * (lst[i+1][0] - lst[i][0])

#뒤에서부터도 똑같이 진행한다. 
height = lst[-1][1]

for i in range(n-1, idx, -1) :
    if height < lst[i-1][1] :
        result += height * (lst[i][0]-lst[i-1][0])
        height = lst[i-1][1]
    else :
        result += height * (lst[i][0] - lst[i-1][0])

print(result)

• 가장 높은 기둥의 높이를 기준으로 앞뒤에서 계산하면서 찾아간다.
• 처음에는 앞에서부터 단순 계산했는데...복잡해졌당...
• https://velog.io/@holawan/%EB%B0%B1%EC%A4%80-2304%EC%B0%BD%EA%B3%A0-%EB%8B%A4%EA%B0%81%ED%98%95-python

[백준] 2304_창고 다각형 python

 

 

---

괄호 제거 - 골드4

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

from itertools import combinations

expr = list(input())
indices = []
stk = []
answers = set()

for i in range(len(expr)):
    if expr[i] == '(':
        stk.append(i)
    elif expr[i] == ')':
        indices.append((stk.pop(), i))  # 쌍을 이루는 괄호의 index 쌍 리스트트

for i in range(len(indices)):
    for comb in combinations(indices, i+1):  # 괄호 제거 경우의 수 조합
        temp = expr[:]
        for idx in comb:
            temp[idx[0]] = temp[idx[1]] = ""
        answers.add("".join(temp))      # 괄호가 삭제된 식을 정답 set에 추가

for item in sorted(list(answers)):
    print(item)

• 먼저 쌍을 이루는 괄호의 index 리스트를 구한다.
• combinations() 메소드를 이용해 조합 경우의 수를 모두 구한 후 해당 조합에 따라 괄호를 삭제한 수식을 정답 set에 추가한다.
• https://www.acmicpc.net/status?user_id=jain5379&problem_id=2800&from_mine=1

 

---

뱀 - 골드4

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

# 처음 코드...하다가 막힘
N = int(input())
K = int(input())
board = [[0]*N for _ in range(N)]
ans = 0
is_end = 0

for _ in range(K):
    a, b = map(int, input().split())
    board[a-1][b-1] = 1  # 사과의 위치

L = int(input())
directions = ['R', 'B', 'L', 'F']
direct = 0
length = 1
last_row = 0
last_column  = 0
next_row = 0
next_column = 0
board[0][0] = 2
for i in range(L):
    a, b = input().split()
    for j in range(int(a)):
        print(board, directions[direct])
        if directions[direct] =='R':
            next_column +=1
        elif directions[direct] == 'L':
            next_column -=1 
        elif directions[direct] == 'F':
            next_row -=1
        elif directions[direct] == 'B':
            next_row +=1
        ans += 1

        if next_row > N-1 or next_row < 0 or next_column > N-1 or next_column < 0 or board[next_row][next_column]==2:
            print('out', next_row, next_column)
            is_end = 1
            break

        if board[next_row][next_column] == 1:
            board[next_row][next_column] = 2
            length += 1
        elif board[next_row][next_column] == 0:
            board[next_row][next_column] = 2
            if directions[direct] =='R':
                board[next_row][next_column-length] = 0
            elif directions[direct] == 'L':
                board[next_row][next_column+length] = 0
            elif directions[direct] == 'F':
                board[next_row+length][next_column] = 0
            elif directions[direct] == 'B':
                board[next_row-length][next_column] = 0




    if is_end:
        break

    if b == 'D':
        direct = (direct+1)%4
    elif b == 'L':
        if direct == 0:
            direct = 3
        else:
            direct -= 1
    
print(ans)

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
k = int(input())
maps = [[0] * (n+1) for _ in range(n+1)]
for _ in range(k):#사과의 위치
    x,y = map(int,input().split())
    maps[x][y] = 2
info = {}
l = int(input())
for _ in range(l):# 뱀의 방향변환정보 (초, 방향 L:왼쪽 D:오른쪽)
    sec, direct = input().split()
    info[int(sec)] = direct
time = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]
x, y = 1, 1
maps[y][x] = 1
d = 0
snakes = deque([(1, 1)])

while True:
    nx, ny = x+dx[d], y+dy[d]
    # 뱀의 몸통에 닿거나 벽에 부딪히는 경우 종료
    if nx<=0 or ny<=0 or nx>n or ny>n or (nx,ny) in snakes:
        break
    # 사과를 먹지 못하면 꼬리 없애기
    if maps[ny][nx]!=2:
        a,b = snakes.popleft()
        maps[b][a]=0
    x, y = nx, ny
    maps[y][x] = 1
    snakes.append((nx, ny))
    time+=1
	
    # 시간에 해당하는 방향전환 정보가 있을 경우
    if time in info.keys():
        if info[time] == "D":
            d = (d+1)%4
        else:
            nd = 3 if d==0 else d-1
            d = nd
print(time+1)

• 뱀의 길이를 따로 저장하지 않고 바로 지도 리스트에 특정값으로 표시하려고 했는데...막혔다.
• 뱀이 차지하는 좌표를 deque로 저장하면 되는구나...사과를 먹지 못한 경우는 popleft()를 이용해서 길이를 줄인다.
• https://velog.io/@joniekwon/Python-%EB%B0%B1%EC%A4%80-3190%EB%B2%88-%EB%B1%80

[Python] 백준 3190번: 뱀

 

 

---

문제 추천 시스템 Version1 - 골드 4

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

# 처음 코드..시간초과
N = int(input())
dic = dict()

for _ in range(N):
    P, L = map(int, input().split())
    dic[P] = L

sorted_dict = dict(sorted(dic.items(), key=lambda item: (item[1], item[0])))  # 정렬

M = int(input())
for _ in range(M):
    cmd = list(input().split())
    if cmd[0] == 'recommend':
        if cmd[1] == '1':
            print(list(sorted_dict.keys())[-1])
        elif cmd[1] == '-1':
            print(list(sorted_dict.keys())[0])
    elif cmd[0] == 'add':
        sorted_dict[int(cmd[1])] = int(cmd[2])
        sorted_dict = dict(sorted(sorted_dict.items(), key=lambda item: (item[1], item[0])))  # 정렬

    elif cmd[0] == 'solved':
        del sorted_dict[int(cmd[1])]

• 딕셔너리로는 시간초과가 나서...heapq를 사용해야할 것 같은데 어떻게 할지 모르겠닷...ㅎ

import heapq
import sys
from collections import defaultdict

input = sys.stdin.readline

minHeap = []
maxHeap = []
solved = defaultdict(int)
n = int(input())

for _ in range(n):
    p, l = map(int, input().split())
    heapq.heappush(minHeap, (l, p))
    heapq.heappush(maxHeap, (-l, -p))

m = int(input())
for _ in range(m):
    command = input().split()

    if command[0] == "recommend":
        # 어려운 문제 추천
        if command[1] == '1':
            while solved[abs(maxHeap[0][1])] != 0:
                solved[abs(maxHeap[0][1])] -= 1
                heapq.heappop(maxHeap)
            print(-maxHeap[0][1])
        # 쉬운 문제 추천
        else:
            while solved[minHeap[0][1]] != 0:
                solved[minHeap[0][1]] -= 1
                heapq.heappop(minHeap)
            print(minHeap[0][1])
    elif command[0] == "add":
        p = int(command[1])
        l = int(command[2])
        heapq.heappush(minHeap, (l, p))
        heapq.heappush(maxHeap, (-l, -p))
    elif command[0] == "solved":
        solved[int(command[1])] += 1

• 어려운 문제, 쉬운 문제 추천을 위해 min_heap과 max_heap을 각각 만들어준다.
• heapq에 tuple을 저장할 수 있다! 첫번째 값을 기준으로 정렬되며, 값이 같으면 두번째 값을 기준으로 정렬된다.
• solved라는 딕셔너리를 만들어서 해결된 문제를 관리해준다.
• https://velog.io/@jomg2007/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-21939%EB%B2%88

[백준/파이썬] 21939번

 

 

---

# 회고

 

deque, heapq에 익숙해지자...