20200401 알고리즘

1. 코니와 브라운

문제

연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다. 이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나는데 걸리는 최소 시간을 구하시오.

조건

1. 코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다. 즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다.
2. 브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다.
3. 코니와 브라운의 위치 p는 조건 0 <= x <= 200,000을 만족한다.
4. 브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다.

입력 형식

표준 입력의 첫 줄에 코니의 위치 C와 브라운의 위치 B를 공백으로 구분하여 순서대로 읽는다.

출력 형식

브라운이 코니를 잡을 수 있는 최소시간 N초를 표준 출력한다. 단 브라운이 코니를 잡지 못한 경우에는 -1을 출력한다.

예제

입력: 11 2

출력: 5

import sys
from collections import deque

if __name__ == '__main__':
    c, b = map(int, input().split())
    MAX = 200001
    dQ = deque()
    dQ.append(b)

    L = 1
    while dQ and c < MAX:
        c += L
        size = len(dQ)
        for _ in range(size):
            now = dQ.popleft()
            for next in (now-1, now+1, 2*now):
                if 0 <= next < MAX:
                    dQ.append(next)
                    if next == c:
                        print(L)
                        sys.exit(0)
        L += 1
    else:
        print(-1)

• 체크를 허용해야 했다!!

2. 체육복 ( 출처: 프로그래머스 )

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

입출력 예 설명

예제 #1 1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2 3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

Solution

def solution(n, l, r):
    reserve = set(r) - set(l)
    lost = set(l) - set(r)
    answer =  n - len(reserve) - len(lost) # init
    
    for v in reserve:
        if v-1 in lost:
            answer += 2
            lost.remove(v-1)
        elif v+1 in lost:
            answer += 2
            lost.remove(v+1)
        else:
            answer += 1
            
    return answer

3. 크레인 인형뽑기 게임

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/64061

Solution

def solution(board, moves):
    stack = list()
    cnt = 0
    for v in moves:
        x = v -1
        for y in range(len(board)):
            if board[y][x] != 0:
                if stack and stack[-1] == board[y][x]:
                    stack.pop()
                    cnt += 2
                else:
                    stack.append(board[y][x])
                board[y][x] = 0
                break
    return cnt