컴공0개언어

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

문제에 따르면 논문 $n$편 중, $h$번 이상 인용된 논문이 $h$편 이상이고, 나머지 논문이 $h$번 이하 인용되었다면 $h$의 최댓값을 H-Index라고 한다.

예를들어 인용수가 [3, 0, 6, 1, 5]라고 하면, H-index는 3이 된다.

H-Index를 구하기 위해 정렬을 먼저 하면 [0, 1, 3, 5, 6]가 되는데 3까지는 $h$번 이상 인용된 논문의 수가 $h$이상이고 5부터는 $h$번 이상 인용된 논문의 수가 $h$보다 작게된다.

이렇게 $h$번 이상 인용된 논문의 수가 $h$보다 작게되는 원소를 찾으면 최종 H-Index의 범위는 (이전 원소 값) ~ (현재 원소 값)사이에 위치하게 된다. 따라서 (현재 원소 값)부터 (이전 원소 값)에 대하여 for문을 돌고, $h$번 이상 인용된 논문의 수가 $h이상이 되는 값이 나오면 그 값이 바로 H-Index가 된다.

def solution(citations):
    # len(citations) : 1 <= n <= 1000
    answer = 0
    
    citations.sort() # O(nlogn)
    
    max_h = -1
    for i in range(len(citations)):
        h = citations[i]
        n_h_over = len(citations) - i
        
        if n_h_over >= h:
            max_h = h
        else:
            for h in range(citations[i], max_h-1, -1):
                if n_h_over >= h:
                    max_h = h
                    
                    return max_h
    
    return max_h

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

문제에 나와있는대로 코드를 작성했다.

부분 배열의 시작, 끝 인덱스가 주어지면 부분 배열을 얻어내고 이를 정렬하여 부분 배열의 K번째 수를 얻는 과정을 반복한다.

def solution(array, commands):
    answer = []
    
    for command in commands:
        i, j, k = command[0], command[1], command[2]
        
        part_arr = array[i-1:j]
        part_arr.sort()
        answer.append(part_arr[k-1])
    
    return answer

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

문제에 주어진대로 그대로 코드를 작성하면 해결되는 문제였다.

import heapq

def solution(operations):
    # len(operations) : 1 <= n <= 10000000
    
    answer = []
    heap = []
    
    for operation in operations:
        op = operation.split()[0]
        data = operation.split()[1]
        
        if op == 'I':
            heapq.heappush(heap, int(data))
        elif op == 'D' and len(heap) > 0:
            if data == '1':
                heap.pop()
            elif data == '-1':
                heapq.heappop(heap)
    
    if len(heap) > 0:
        answer = [max(heap), min(heap)]
    else:
        answer = [0, 0]
        
    
    return answer

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

heap을 사용하기 위해 heapq 라이브러리를 이용하였다.

input으로 들어오는 scoville을 heapify하게되면, heap형태로 변환되기 때문에

첫 번째 heapq.heappop()를 통해 가장 맵지 않은 음식의 스코빌 지수, 두 번째 heapq.heappop()를 통해 두 번째로 맵지 않은 음식의 스코빌 지수를 얻을 수 있다.

import heapq

def solution(scoville, K):
    # len(scoville) : 1 <= n <= 1000000
    # 최대 O(nlogn)정도
    answer = 0
    
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        if len(scoville) <= 1:
            return -1
        
        mix_scoville = heapq.heappop(scoville) + heapq.heappop(scoville) * 2
        heapq.heappush(scoville, mix_scoville)
        
        answer += 1
        
    return answer

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

queue에 각 작업마다 배포가 몇 일 후에 진행될 수 있는지를 저장한다.

이 때, 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발되면 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다. 따라서

여기서 저장하려는 배포 일자가 queue에 저장된 최대 배포 일자보다 크면 그동안 queue에 저장된 작업들을 배포할 수 있으므로 answer에 queue의 길이를 저장하고, queue를 비운다.

이러한 과정을 반복하고, 과정이 끝나면 queue에 남아 있는 작업들이 있을 수 있으므로 queue에 남은 작업이 있으면 queue의 길이를 answer에 추가한다.

import math
from collections import deque

def solution(progresses, speeds):
    answer = []
    
    queue = deque()
    max_work_day = -1
    for progress, speed in zip(progresses, speeds):
        work_day = math.ceil((100 - progress) / speed) # 배포까지 걸리는 시간
        
        if max_work_day < work_day:
            if len(queue) > 0:
                answer.append(len(queue))
            
            queue.clear()
                
            max_work_day = work_day
            
        queue.append(work_day)
    
    if len(queue) > 0:
        answer.append(len(queue))
        
    return answer

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

prices의 길이를 n이라고 하면, 최대 O(nlogn)의 풀이가 가능해 보였다.

스택을 이용해서 문제의 요구사항대로 구현하고자 했다. 

스택의 top에 있는 주식의 price가 추가하려고하는 주식의 price보다 같거나 작으면 그냥 스택에 push하고, 크면 스택 top 주식의 price가 추가하려고하는 주식의 price보다 같거나 작아질 때까지 pop을 한다.

따라서 스택을 이용한 풀이의 최종 시간 복잡도가 O(n)가 된다.

def solution(prices):
    # prices의 길이 : 1 <= n <= 100000
    # 최대 O(nlogn) 정도 가능
    
    n_prices = len(prices)
    answer = [0 for _ in range(n_prices)]
    
    stack = [(prices[0], 0)] # (주식 가격, stack에 push된 시점)
    for i, price in enumerate(prices):
        top_price = stack[-1][0]
        
        if top_price > price:
            # top_price <= price가 될 때까지 pop한 후에 push
            while top_price > price:
                stack_top = stack.pop()
                answer[stack_top[1]] = i - stack_top[1]
                
                if len(stack) == 0:
                    break
                
                top_price = stack[-1][0]
            
        stack.append((price, i))
    
    
    while len(stack) > 0:
        stack_top = stack.pop()
        answer[stack_top[1]] = n_prices - 1 - stack_top[1]
    
    # 최종 복잡도 : O(n)
    return answer

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

소스코드의 간결함을 위해 defaultdict를 사용했다.

처음에는 combinations을 이용해서 가능한 모든 의상 종류 조합에 대해서 하나하나 구했는데, 시간복잡도가 O(2^m)이 되어 시간초과가 발생했다.

찾아보니 밑에 소스코드와 같은 풀이가 가능했는데, 약간 고등학교 때 확통 문제를 푸는 듯 했다...

def solution(clothes):
    # 의상 수 : 1 <= n <= 30
    # 의상 종류 수 : 1 <= m <= n
    answer = 1
    type2count = defaultdict(int) # key: 종류, value: 종류 count
    
    # n + m = O(n)
    for _, cloth_type in clothes:
        type2count[cloth_type] += 1
    
    keys = list(type2count.keys())
    
    for key in keys:
        # 종류에 있는 의상 개수가 n개라면 해당 종류의 의상을 선택하는 경우의 수는
        # (0개 선택), (1개 선택), ..., (n개 선택) ==> 총 n+1 경우
        answer *= type2count[key] + 1
        
    answer -= 1 # 모든 종류의 의상을 선택하지 않는 경우의 수를 뺌.
    
    return answer

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

먼저 전화번호들에 대해서 count가 1이므로 dictionary를 초기화한다.

그리고 전화번호들에 대해서 앞에서부터 하나씩 접두어를 저장하는 prefix에 저장하고, prefix가 dictionary에 있으면 접두어가 존재하므로 False를 return한다.

시간복잡도는 phone_book의 길이를 n, 전화번호의 길이를 m이라고 하면 O(nm)이다.

def solution(phone_book):
    answer = True
    prefix_dict = {} # key: phone_number, value: phone_number count
    
    
    for phone_number in phone_book:
        prefix_dict[phone_number] = 1
    
    for phone_number in phone_book:
        prefix = ""
        for digit in phone_number:
            prefix += digit
        
            if prefix in prefix_dict and prefix != phone_number:
                return False
                
    return True