[240514] 코딩테스트 문제풀이

 
오늘은 알고리즘 책 복습했다 ! 
+ 해시, 트리, 그래프, 정렬 부분 공부 필요함
 
 

1. 트리의 지름

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

from collections import deque
N = int(input())
A = [[] for _ in range (N+1)]


# 데이터 인접 리스트로 구현 -> 튜플 형태로 저장해서 -> 거리 값 꺼낼 수 있도록 하기 위해
for _ in range(N) :
    Data = list(map(int, input().split()))
    index = 0
    S = Data[index] # 트리 인덱스
    index += 1
    while True :
        E = Data[index]
        if E == -1 :
            break
        V = Data[index + 1]
        A[S].append((E,V))
        index += 2

distance = [0] * (N+1)  # 거리 리스트
visited = [False] * (N+1)  # 방문 리스트

def BFS(v) :
    queue = deque()
    queue.append(v)
    visited[v] = True
    while queue :
        now_Node = queue.popleft()
        for i in A[now_Node] :
            if not visited[i[0]] :
                visited[i[0]] = True
                queue.append(i[0])
                distance[i[0]] = distance[now_Node] + i[1] # 거리 리스트 업데이트

BFS(1)
Max = 1

for i in range(2,N+1) :
    if distance[Max] < distance[i] :
        Max = i

# 최댓값 기준으로 다시 한번 돌림 
distance = [0] * (N+1)
visited = [False] * (N+1)
BFS(Max)
distance.sort()
print(distance[N])

 

---

2.  이중 우선순위 큐(🥲시간초과)

• 시간초과 
  • 이유 : remove 때문, 숫자를 찾아야하기 때문에 ... !
  • visited 배열 써라고 하는데 모르겠음 진짜로 ㅜ...ㅜ....ㅜㅜㅜㅜㅜ....

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

import heapq

import sys
input = sys.stdin.readline
A = int(input())

for i in range(A) :

    n = int(input())
    max_heap = []
    min_heap = []

    for i in range(n) :
        a,b = input().split()

        if a == 'I' :
            heapq.heappush(max_heap, -int(b))
            heapq.heappush(min_heap, int(b))

        elif a == 'D' and b == '-1' :  # 최솟값 삭제 연산
            if len(min_heap) != 0 :
                number = heapq.heappop(min_heap)
                max_heap.remove(-number)

        elif a == 'D' and b == '1' :
            if len(min_heap) != 0 :
                number = heapq.heappop(max_heap)
                min_heap.remove(-number)


    if len(min_heap) == 0 :
        print('EMPTY')
    else :
        print(-heapq.heappop(max_heap), end = ' ')
        print(heapq.heappop(min_heap), end = '')

 

---

3. 에디터

• sys.stdin.readline().strip()로 입력받고
• sys.stdout.wirte()로 출력해줘야 함

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

import sys
from collections import deque
word = list(sys.stdin.readline().strip())
n = int(sys.stdin.readline().strip())
left_q = deque()

for i in range(n) :
    input_word = sys.stdin.readline().strip()
    if len(input_word.split()) > 1 :
        plus_word,b = input_word.split()
    else :
        plus_word = 'False'

    if plus_word in 'P' :
        word.append(b)

    elif input_word in 'L' :
        if len(word) > 0 :
            a = word[-1]
            del word[-1]
            left_q.appendleft(a)

    elif input_word in 'B' :
        if len(word) > 0 :
            del word[-1]

    elif input_word in 'D' :
        if len(left_q) > 0 :
            word.append(left_q[0])
            del left_q[0]

if len(word) != 0 :
    sys.stdout.write(''.join(word))
if len(left_q) != 0 :
    sys.stdout.write(''.join(left_q))

 

---

4. 베르트랑 공준

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

import math
A = list()
while True :
    number = int(input())
    if number != 0 :
        A.append(number)

    else :
        break

max_number = max(A) * 2

B = [ i for i in range (max_number + 1)]
for i in range(2,int(math.sqrt(max_number)+1)) :
    for j in range(i+i, max_number+1, i) :
        B[j] = 0

for k in range(len(A)) :
    if A[k] == 1 :
        print(1)
    else :
        a,b = A[k], A[k]*2
        print(len(B[a+1:b])-B[a+1:b].count(0))

 

---

5.