1764번, 1927번, 16928번

1. 듣보잡

링크 - https://www.acmicpc.net/problem/1764

+) 아니 선생님 듣고, 보기까지한 사람인데 왜 제목이 듣보잡인가요?

컴활선생님 한 번 따라해보고 싶었읍니다.

코드

import sys

input = sys.stdin.readline

n,m = map(int,input().split())

n_dict={}
result=[]

for i in range(1,n+1):
    name = input().rstrip()
    n_dict[name]=i
    
for i in range(1,m+1):
    name = input().rstrip()
    if name in n_dict:
        result.append(name)



print(len(result))
if len(result)>=1:
    result.sort()
    for n in result:
        print(n)

rstrip()함수를 rstip()이라고 잘못써서 계속 에러가 났다 ㄱ-
실행도 안해보고 낸 제 잘못이죠 머..
n_dict도 사실 리스트로 구현해도 됐는데 문제에 사전이란 말이 나와서 사전 써야 하는 줄 알고 dictionary타입으로 구현했다.

2. 최소힙

링크 - https://www.acmicpc.net/problem/1927

코드

import heapq

n = int(input())

q = []
for i in range(n):
    k = int(input())
    if k==0:
        if len(q)==0:
            print(0)
            continue
        print(heapq.heappop(q))
    else:
        heapq.heappush(q,k)

heapq라이브러리를 사용해서 구현했다. 이러면 안되는걸 알지만~ 쉽게 가자고요~

3. 뱀과 사다리 게임

링크 - https://www.acmicpc.net/problem/16928

코드

from collections import deque
import sys

input = sys.stdin.readline

#101짜리 일차원 게임판 생성
game = [0 for i in range(101)]

#사다리, 뱀의 개수
l,s = map(int,input().split())

#사다리 위치 입력받기
for _ in range(l):
    x,y = map(int,input().split())
    #x번째 사다리에 도착하면 y로 간다
    game[x]=y

#뱀의 위치 입력받기
for _ in range(s):
    u,v = map(int,input().split())
    game[u]=v

dx=[1,2,3,4,5,6]
def bfs():
    q = deque()
    visited =[False]*101
    #[위치, count]
    q.append([1,0])
    visited[1]=True
    
    while q:
        now,count= q.popleft()
        if now==100:
            return count
        else:
            for x in dx:
                nx=now+x
                if nx>100: #100넘으면 안된다.
                    continue
                elif game[nx]!=0: #뱀이나 사다리 걸리면
                    if visited[game[nx]]==False:
                        q.append([game[nx],count+1])
                        visited[game[nx]]==True
                else:#그냥 이동이면?
                    if visited[nx]==False:
                        q.append([nx,count+1])
                        visited[nx]=True
                        
print(bfs())

시뮬레이션만 하면 될 줄 알았는데 시뮬레이션+그래프 문제였다.
bfs방식은 저번에 풀었던 숨바꼭질과 비슷했다.
조건을 처리할 때, 문제에 있는 조건들을 그대로 잘 적어주면 되는 문제였다.