[TIL] 프로그래머스 - 입국심사 / 코테에 활용할 수 있는 Pythonic한 코드 조각 / 당분간 계획

[Today I Learned]

# 프로그래머스 - 입국심사

문제 설명
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

@solution.py

애초에 이진 탐색 문제 파트에서 고른 문제이기도 했고, 주어지는 인풋 단위도 엄청 크고, 이진 탐색 문제인건 오케이 알겠어,, 그래서 뭘 이진탐색해야하는데..? 했던 문제. 이진 탐색은 구현이 어렵다기보다는 어떤 걸 이진 탐색할 것인지, 이동 기준은 어떤 것으로 할 것인지 생각하는게 키인것 같다.

0부터 최악의 탐색 소요 시간을 탐색할 array로 두고 이진 탐색을 하면 된다는 힌트를 얻어서 풀이를 시작했다.

def solution(n, times):
    
    # array ) 0 ~ max(times)
    start = 0
    end = max(times) * n
    answer = 0
    
    while start <= end:
        mid = (start+end) // 2
        people = sum([mid//t for t in times])

        if people < n: # 처리해야하는 사람보다 더 적은 사람 처리 > 시간 늘리자
            start = mid + 1
        
        else: # 처리해야하는 사람보다 더 많은 사람 처리
            answer = mid
            end = mid - 1

    return answer

어제의 교훈을 바탕으로 메모리를 생각해 0~max(times) array는 생성하지 않았다. 이진 탐색의 기준은 mid 시간 동안 처리할 수 있는 사람의 수로 두었다. 이 값은 시간 / 각 심사대의 t 로 나눈 값의 몫을 다 더해 계산하였다.처리해야하는 사람, 즉 n 값보다 처리할 수 있는 사람이 더 적은 경우에는 start를 mid+1로, 처리해야하는 사람과 같거나 그보다 많은 사람을 처리해야할 경우에는 end를 mid-1로 바꿔주었다. 처리해야하는 사람과 같더라도 시간을 더 줄일 수 있기 때문에 답을 answer에 저장하고 탐색은 계속하도록 해주었다.

---

이코테 강의에서 남은 단원은 다음과 같았다. 중요한 내용들이지만 단기간에 코딩 테스트를 준비하고 있는 나에게는 선택과 집중이 필요하다고 판단, 남은 기간동안은 배운 유형들의 문제를 계속 연습하는 쪽으로 방향을 정했다.

어떤 문제를 푸는게 좋을까 고민하던중 https://covenant.tistory.com/235 << 이 블로그를 알게 되었고, 추천해주신 문제들을 쭉 풀어가보기로 했다. : >

---

# Python 코드 작성 참고

https://covenant.tistory.com/141 로 시작되는 용감하게 시작하는 코딩테스트 1~3편에서 몰랐던 내용들을 간단하게 정리해보았다.

1-1. 배열 입력

많은 문제들에서 첫 번째 줄에는 입력되는 숫자들의 줄 수를, 다음 줄부터는 숫자들이 공백을 기준으로 주어진다. 이 때 다음과 같은 한 줄의 코드로 입력을 처리할 수 있다.

MAP = [list(map(int, input().split())) for _ in range(int(input()))]

 

1-2. 정수와 배열이 같은 줄에 들어오는 경우

N, *arr = map(int, input().split())

변수 앞에 *을 붙이면 뒤이어 나오는 값이 배열로 저장된다.

 

2. 진법

많은 문제들에서 첫 번째 줄에는 입력되는 숫자들의 줄 수를, 다음 줄부터는 숫자들이 공백을 기준으로 주어진다. 이 때 다음과 같은 한 줄의 코드로 입력을 처리할 수 있다.

# 10진수 > 2,8,16진수 변환
bin(42)
oct(42)
hex(42)

# 2,8,16진수 > 10진수 변환
int('0b111100', 2)
int('0o74', 8)
int('0x3c', 16)

 

3. 배열 초기화

첫 번째 정수를 배열의 가로 크기로, 두 번째 정수를 배열의 세로 크기인 0으로 초기화한 배열 생성

N, M = map(int, input().split())
arr = [[0] * N for _ in range(M)]]

 

4. 순열, 조합

4-1. itertools를 사용한 조합 & 순열

from itertools import combinations

list(combinations([1,2,3,4],3)))
# [(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

from itertools import permutations

list(permutations([0, 1, 2, 3], 3))

 

오늘은 간단한 기본 문제들 위주로 풀었고, 내일부터는 스택부터 다시 찹찹...
그나저나 나 코로나 아니길 ㅠ_ㅠ