수학과의 개발자 도전기

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42628

문제 이해 

- 주어진 연산(operations)을 진행하면서 데이터를 삽입하거나, 최소값 또는 최대값을 제거하는 문제이다.

- 최소값과 최대값은 각각의 heap을 이용하면 된다는 아이디어는 있었지만 하나의 배열에서 진행하기 때문에 최소값을 최소 Heap에서 pop할 때에도 최대 Heap에서 해당 값을 제거해야했다. (최대값을 최대 heap에서 pop할 때에도 마찬가지이다)

- 처음에는 힙에서 원소를 제거하는 방법을 몰라서 while문을 돌면서 최소값 또는 최대값과 동일한 값이 있으면 하나만 빼는 로직을 구현했으나, heap에서는 항상 최소값을 pop하기 때문에 항상 같은 값을 pop한다는 것을 간과했다.

- 그래서 찾아보니 heap에서도 remove를 사용할 수 있다는 것을 알았고, 그것을 적용했다. 

- 최대힙, 최소힙을 따로 구현하지 않아도 하나의 힙으로도 진행할 수 있는 방법도 알게 되었는데 방법은 다음과 같다. 

heap = heapq.nlargest(len(heap), heap)[1:]
heapq.heapify(heap)

nlargest(n, list)를 이용하면 힙에서 가장 큰 수 n개를 뽑아낼 수 있다. 위 코드에서는 heap의 길이만큼의 큰 수를 뽑기에 숫자가 내림차순으로 정렬된다. 이를 인덱스 1부터 슬라이싱 하면 가장 큰 값이 제외될 수 있고, 이를 다시 heapify 하면 된다. 

풀이 로직

- 최소힙(heap)과 최대힙(max_heap)을 각각 선언한뒤 while문으로 operations 원소를 pop한다. 이때 원소는 op, number이다.

- operation은 연산이 삽입(I)인지, 삭제(D)인지 알려준다. number는 -1인 경우에는 최소값 삭제, 1인 경우는 최대값 삭제, 그 외는 삽입하는 숫자다.

- 주어진 operation이 I인 경우에는 최소힙에는 주어진 number 값 그대로 push하고, 최대힙에는 (-number, number) 형태로 push한다. (파이썬에서의 heapq는 최소값이 0인덱스인 최대힙이기 때문이다)

- operation이 D이고, numbe 값에 따라 최대 또는 최소를 pop한다.

    1) number == -1인 경우는 최소값을 pop해야하므로 최소힙에서는 pop을 하고 해당 값을 최대힙에서 제거(remove)한다. 

    2) number == 1인 경우는 최대값을 pop해야하기에 최대힙에서 pop 한 뒤 해당 값을 최소 힙에서 제거 한다. 

- 반복문이 끝난 뒤 heap에 원소가 없다면 [0, 0]을 원소가 있다면 [최대값, 최소값]을 반환한다. 

정답 풀이 

from collections import deque
import heapq

def solution(operations):
    heap = []
    max_heap = []
    operations = deque(operations)
    
    while operations:
        operation, number = operations.popleft().split()
        
        if operation == 'I':
            number = int(number)
            heapq.heappush(heap, number)
            heapq.heappush(max_heap, (-1 * number, number))
        else:
            if len(heap) == 0:
                continue
            if number == '1': # 최댓값 뽑기
                x = heapq.heappop(max_heap)[1]
                heap.remove(x)
            elif number == '-1': 
                x = heapq.heappop(heap)
                max_heap.remove((-1 * x, x))
                    
    if len(heap) == 0:
        return [0, 0]
    else:
        return [heapq.heappop(max_heap)[1], heapq.heappop(heap)]

참고

[Python] 프로그래머스 - 이중우선순위큐

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42626

문제 이해 

- scoville 배열에서 모든 숫자가 주어진 K 이상이 될 때까지의 연산 횟수를 반환하는 문제다. 

- 연산은 (가장 작은 수) + 2 * (두 번째로 작은 수)로 진행하며, 새롭게 업데이트 한 숫자를 다시 scoville에 추가한다. 

- 가장 작은 수를 찾아야하고, len(scoville)이 최대 백 만이기 때문에 배열에서 가장 작은 수가 0 인덱스에 있고, 시간 복잡도가 O(logn)인 heap을 이용해야한다! 

- 위와 같은 방식으로 scoville을 갱신하다가 scoville의 가장 앞 숫자가 K이상이라면 나머지 숫자들도 다 K이상이므로 while문을 break 하면 된다.

- 하지만 만약 scoville에 원소 하나만 남았는데 그 숫자가 K 미만이라면 조건을 만족하지 못하므로 -1을 출력하면 된다.

정답 풀이

import heapq

def solution(scoville, K):
    answer = 0 # K를 만들기 위해 섞은 횟수 
    
    heapq.heapify(scoville)
    
    while len(scoville) >= 2:
        first = heapq.heappop(scoville)
        if first >= K: # 가장 작은 수마저 K이상이므로 모든 수가 K 이상임을 알 수 있음
            break

        result = first + 2 * heapq.heappop(scoville)
        answer += 1
        heapq.heappush(scoville, result)
        
    if scoville[0] < K :
        return -1
    else:
        return answer

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/133501 

- 정답 풀이 : 

참고한 블로그

def solution(distance, scope, times):
    ch = []
    for i in range(len(scope)):
        start, end = sorted(scope[i])
        work, rest = times[i]
        time = start
        while time <= end:
            N = time % (work+rest)
            if 0 < N <= work:
                ch.append(time)
                break
            time += 1

    if ch: return sorted(ch)[0]
    else:  return distance

- 시도해본 풀이 : 

78.6에서 틀렸다

def solution(distance, scope, times):  
    answer = []

    soldiers = []
    for i in range(len(scope)):
        scope[i].sort()
        temp = scope[i] + times[i]
        temp.append(sum(times[i]))
        soldiers.append(temp)
        
    soldiers.sort()
    for i in range(len(soldiers)):
        start, end = soldiers[i][0], soldiers[i][1]
        cycle = end // soldiers[i][4] # 사이클 몇번 도는지 
        for j in range(start, end + 1):
            # 병사 근무 범위에서 근무하는 중일 때 
            if soldiers[i][4] * cycle < j <= soldiers[i][4] * cycle + soldiers[i][2]: 
                answer.append(j)
                break

    if len(answer) == 0:
        return distance
    else:
        return min(answer)

테스트 50%에서 틀렸다. 

def solution(distance, scope, times):  
    sum_times = [sum(times[i]) for i in range(len(times))] # 일 + 휴식 단위 
    answer = []
    location = 1
    for i in range(len(scope)):
        start, end = scope[i][0], scope[i][1]
        cycle = end // sum_times[i] # 사이클 몇번 도는지 
        for j in range(start, end + 1):
            # 병사 근무 범위에서 근무하는 중일 때 
            if sum_times[i] * cycle < j <= sum_times[i] * cycle + times[i][0]: 
                answer.append(j)
                break

    if len(answer) == 0:
        return distance
    else:
        return min(answer)

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/135807

스스로 푼 문제다!

이해는 어렵지 않았는데, 시간 복잡도 때문에 이에 대해 생각해봐야했던 문제다. 

math.gcd 사용하는 법을 익혀야할 것 같다. 

문제 이해 

arrayA 원소의 공약수 중 arrayB의 모든 원소를 나누지 못하는 수를 구하고

arrayB 원소의 공약수 중 arrayA의 모든 원소를 나누지 못하는 수를 구해서

그 중 최댓값을 반환하고, 없다면 0을 반환하면 된다고 이해했다. 

풀이 이해

• 각 배열에 대해 모든 원소를 나누는 공약수가 있는지 확인하기 위해 get_common() 함수를 이용했다. 
  • 처음에는 여기서 모든 원소의 약수를 모은 다음 진행했는데, 이렇게 하면 시간초과가 발생하므로 시간을 줄일 수 있는 방법을 생각했다.
  • 배열의 모든 원소를 나눌 수 있는 수라면 배열의 한 원소를 선택해 그것의 약수로 진행해도 된다라는 생각했다. 그래서 가장 큰 원소의 약수를 temp에 저장한다음 그 원소 중에 arr의 모든 원소를 나눌 수 있는 것들을 result에 모은 다음 반환했다. 
• arrayA와 arrayB에 대해 commons_A, commons_B를 구한 다음 길이에 따라 로직을 다르게 했고, 공통된 연산은 operation()함수를 이용했다. 결과는 answer에 저장했다.
• 이렇게 구한 answer는 조건을 만족하는 수이므로 answer에 원소가 없다면 0을, 있다면 최대값을 반환한다. 
• 이때 arrayA = [3], arrayB = [17]인 경우 각 배열의 원소는 본인이 속한 배열의 원소를 다 나누고, 반대는 다 나누지 못하기 때문에 두 수 모두 조건을 만족한다. 이런 경우는 둘 중 최댓값을 반환하는 로직을 추가해야 테스트 두 개를 통과할 수 있다. (edge case)

- 정답 풀이 :

풀이가 너무 길다.

다른 풀이 참고해서 약수 구하는 것 등 코드 줄일 수 있는 방법을 생각해봐야겠다.

import math

def get_common(arr): #리스트의 모든 원소 약수를 모두 모아서 반환하는 함수 
    temp = []
    arr.sort()
    num = arr[-1]
    for i in range(2, int(math.sqrt(num) + 1)):
        if num % i == 0:
            temp.append(i)
            temp.append(num // i)
            
    result = []
    for i in range(len(temp)):
        flag = True
        for j in range(len(arr)):
            if arr[j] % temp[i] != 0:
                flag = False
                break
        if flag:
            result.append(temp[i])
            
    return result

def operation(arr, commons):
    answer = []
    for i in range(len(commons)):
            flag = True
            for j in range(len(arr)):
                if arr[j] % commons[i] == 0:
                    flag = False
                    break
            if flag:
                answer.append(commons[i])
    return answer
                         
def solution(arrayA, arrayB):
    if len(arrayA) == 1 and len(arrayB) == 1:
        min_num, max_num = min(arrayA[0], arrayB[0]), max(arrayA[0], arrayB[0])
        if max_num % min_num != 0: # 두 수는 소수 관계
            return max_num
    
    commons_A = get_common(arrayA) # A의 모든 원소를 나누는 공약수 
    commons_B = get_common(arrayB) # B의 모든 원소를 나누는 공약수 
    
    answer = []
    if len(commons_A) == 0 and len(commons_B) == 0:
        return 0
    
    elif len(commons_A) == 0:
        answer = operation(arrayA, commons_B)
        
    elif len(commons_B) == 0:
        answer = operation(arrayB, commons_A)
                
    else: 
        answer = operation(arrayA, commons_B)
        answer += operation(arrayB, commons_A)
                      
    if len(answer) == 0:
        return 0 
    else:
        return max(answer)

- 시도해본 풀이 :

테스트 2 / 3 통과했다. 

import math

def get_common(arr): #리스트의 모든 원소 약수를 모두 모아서 반환하는 함수 
    temp = set()
    for i in range(len(arr)):
        num = arr[i]
        for j in range(2, int(math.sqrt(arr[i])) + 1):
            if num % j == 0:
                temp.add(j)
                temp.add(num // j)
                
    temp = list(temp)
    result = []
    for i in range(len(temp)):
        flag = True
        for j in range(len(arr)):
            if arr[j] % temp[i] != 0:
                flag = False
                break
        if flag:
            result.append(temp[i])
            
    return result

def operation(arr, commons):
    answer = []
    for i in range(len(commons)):
            flag = True
            for j in range(len(arr)):
                if arr[j] % commons[i] == 0:
                    flag = False
                    break
            if flag:
                answer.append(commons[i])
    return answer
                         
def solution(arrayA, arrayB):
    commons_A = get_common(arrayA) # A의 모든 원소를 나누는 공약수 
    commons_B = get_common(arrayB) # B의 모든 원소를 나누는 공약수 
    
    answer = []
    if len(commons_A) == 0 and len(commons_B) == 0:
        return 0
    
    elif len(commons_A) == 0:
        answer = operation(arrayA, commons_B)
        
    elif len(commons_B) == 0:
        answer = operation(arrayB, commons_A)
                
    else: 
        answer = operation(arrayA, commons_B)
        answer += operation(arrayB, commons_A)
                      
    if len(answer) == 0:
        return 0 
    else:
        return max(answer)