알고리즘 공부 12일차

1. 백준 - 숨바꼭질 3

# 백준 13549 숨바꼭질3

from collections import deque
import sys
# sys.stdin = open('input.txt', 'r')
input = sys.stdin.readline

N, K = map(int, input().split())
lst = [0] * 100001

Q = deque()
Q.append(N) #시작 위치 추가

while Q:
    s = Q.popleft()
    if s == K:
        print(lst[s])
        break

    for i in (s*2, s-1, s+1):
        # 0~100000 사이에 존재하고 방문하지 않았으면
        if 0 <= i <= 100000 and not lst[i]:
            if i == s*2:
                lst[i] = lst[s]
            else:
                lst[i] = lst[s] + 1
            Q.append(i)

2. 프로그래머스 - 영어 끝말잇기

def solution(n, words):
    answer = 1 # 끝말잇기가 진행된 횟수
    end = 0 # break 걸렸는지 안걸렸는지 확인
    check = { i : 0 for i in set(words)} # 중복되었는지 확인하기 위한 딕셔너리
    check[words[0]] = 1 # 제일 처음 값은 체크된 것으로
    if len(words[0]) == 1: # 제일 처음 단어 길이가 1이면 끝내버리기
        return [1, 1]
    for i in range(1, len(words)):
        answer += 1
        if words[i-1][-1] != words[i][0]: # 끝말잇기가 맞는지 확인
            end = 1
            break
        elif len(words[i]) == 1: # 단어 길이가 1보다 큰지
            end = 1
            break
        elif check[words[i]] == 1: # 중복된 단어가 아닌지
            end = 1
            break
        else:
            check[words[i]] = 1
    if answer == len(words) and end == 0: # answer가 단어 갯수와 같고, break가 걸린적이 없다면 끝말잇기를 틀린사람이 없는 것
        return [0, 0]
    return [answer % n if answer % n != 0 else n, answer // n if answer % n == 0 else answer // n + 1]