8/8 Coding Test

✅ Programmers

🎈 야근 지수 LV 3

야근을 하는 경우 피로도가 쌓이게 되고 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값으로 계산할 수 있다. N시간 동안 남은 일의 작업량이 works 배열로 주어질 때 퇴근까지 남은 n시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 문제.

n은 1e6이하의 자연수, works의 길이는 [1,20,000]로 주어진다.

import heapq

def solution(n, works):
    if sum(works) <= n:
        return 0
    works = [-i for i in works]
    heapq.heapify(works)
    while n > 0:
        maxi = heapq.heappop(works)
        heapq.heappush(works, maxi+1)
        n -= 1
    return sum([i**2 for i in works])

< 풀이 과정 >

수학적으로 접근해 해결한 문제.
결론적으로 주어진 야근 시간의 최댓값을 -1씩 줄여 남은 시간들의 제곱합을 줄이는 문제.
다음 과정을 거쳐 리턴처리한다.

• 1. 주어진 남은 작업량의 합이 n시간보다 작다면, 0을 리턴한다. (야근 없이 해결 가능)
• 2. 주어진 works를 최대힙으로 구현해주기 위해 -1을 각 원소에 곱해준다.
• 3. heapq.heappop, heapq.heappush 함수를 이용해 (-1 곱한 기준)현재 가장 값이 작은 원소들의 값에 1씩 더해 주는 while loop 반복
• 4. 결론적으로 answer 배열에 모든 원소에 제곱합 진행

최소 힙을 적용시키지 않은 이유는 매번 마지막 원소에 -1적용 후 sorting을 진행해야 하기에 복잡도가 n = 2 1e4 / m = 5 * * 1e4 일때, n * mlogm이므로 효율성 측면에서 시간 초과가 발생할 수 있다.

🎈 숫자 게임

회사의 2xN명의 사원들은 n명씩 두 팀으로 나눠 숫자 게임을 하려 한다. 두 개의 팀은 A,B로 부르고 규칙은 다음과 같다.

• 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받는다.
• 각 사원은 딱 한 번씩 경기를 한다.
• 각 경기당 팀 내 사원이 한 명씩 나와 서로 수를 공개하고 숫자가 큰 쪽이 승리하고 이긴 팀은 승점 1점을 얻는다.
  -> 모든 사원들에게 자연수를 부여한 후, A팀부터 출전 순서를 정해 공개할 때, B팀이 얻을 수 있는 최대 승점을 리턴하는 문제.

def solution(A, B):
    answer = 0
    A.sort(reverse=True)
    B.sort(reverse=True)
    for i in A:
        if i >= B[0]:
            continue
        else:
            answer += 1
            del B[0]
    return answer

< 풀이 과정 >

• 주어진 A, B 배열을 내림차순으로 정렬한다.
• for 문으로 A 배열의 첫번째 값부터 B의 첫번째 값과 비교한다.
• 만일 A 배열이 더 크다면 건너뛰고 반대의 경우 B 승점이 1씩 올라가고 B의 첫번째 원소를 제거한다.

🎈 기지국 설치

현재 N개의 아파트가 일렬로 나열되어 있고, 일부 아파트 옥상에 4g 기지국이 설치되어 있다. 기지국 간 전파 도달 거리가 w일 때 설치된 기지국 기준 양쪽으로 w만큼 전파를 전달한다고 할때, 아파트 전체에 모든 전파를 연결시키고자 한다.

아파트 개수 N, 현재 4g 기지국이 설치된 위치를 배열인 stations로, 5g 기지국의 전파 도달 거리가 w로 주어질 때 5g 기지국을 설치해야 하는 최소 개수 구하는 문제.

import math
def solution(n, stations, w):
    answer = 0
    start = 1
    for i in stations:
        end = i - w
        dist = end - start
        if dist >= 1:
            answer += math.ceil(dist / ((w*2)+1))
        start = i + w + 1
    if start <= n:
        dist = n+1 - start
        answer += math.ceil(dist / ((w*2)+1))
    return answer

< 풀이 과정 >

stations 배열에 포함된 숫자를 기준으로 기지국을 설치할 수 있는 공간은 3부류이다.

• 1. 맨 앞 아파트 ~ 첫번째 기지국 - w
• 2. stations 배열 내 기지국 간 거리
• 3. 맨 뒤 기지국 + w ~ 맨 마지막 아파트

이를 구현한 과정은 다음과 같다.

• 맨 앞 아파트를 start로 두고 시작하여 for문으로 stations 배열 내 값들을 i로 둔다.
• 첫번째 기지국에서 w만큼 빼준 후 첫 아파트에서 부터 전파가 연결되지 않은 곳까지의 거리를 dist 변수로 둔다. (1번 길이 구함)
• dist가 1이상인 경우 해당 위치 내 기지국을 설치하는데 양쪽으로 w만큼 전파 전달이 가능하므로 실질적으로 기지국 하나당 2*w + 1만큼의 거리 만큼 전파 전달이 가능하다.
• 이후 start 위치를 해당 기지국에서 전파 전달이 가능한 끝 + 1로 옮긴다. (2번 길이 구하는 과정 반복)
• 위 과정을 반복하여 마지막 start위치가 n이하인 경우 dist는 n+1 - start가 되고, 3번 길이를 구해 값을 추가해준다.