This, Too, Shall Pass Away

✏️ 문제 설명
명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.

아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.

가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

✏️ 제한사항
sizes의 길이는 1 이상 10,000 이하입니다.
sizes의 원소는 [w, h] 형식입니다.
w는 명함의 가로 길이를 나타냅니다.
h는 명함의 세로 길이를 나타냅니다.
w와 h는 1 이상 1,000 이하인 자연수입니다.

✏️ 입출력 예

✏️ 입출력 예 설명
- 입출력 예 #1
문제 예시와 같습니다.

- 입출력 예 #2
명함들을 적절히 회전시켜 겹쳤을 때, 3번째 명함(가로: 8, 세로: 15)이 다른 모든 명함보다 크기가 큽니다. 따라서 지갑의 크기는 3번째 명함의 크기와 같으며, 120(=8 x 15)을 return 합니다.

- 입출력 예 #3
명함들을 적절히 회전시켜 겹쳤을 때, 모든 명함을 포함하는 가장 작은 지갑의 크기는 133(=19 x 7)입니다.

✏️ 내가 작성한 코드

def solution(sizes):
    biglist = list()
    smalllist = list()

    # sizes에서 원소 하나씩 가져와(원소=배열) 그 원소에서 큰값과 작은값을 서로 다른 리스트에 각각 담아줌
    for i in sizes:
        biglist.append(max(i))
        smalllist.append(min(i))

    # 각 리스트에서 가장 큰 값 가져와 곱해주면됨
    return max(biglist)*max(smalllist)

✏️ 참고

명함들이 '회전'될 수 있다는 것을 명심해야한다.

예를 들어 가로 6 세로 16 명함 지갑은 가로 17, 세로 7 명함 지갑에 '회전'시켜서 들어갈 수 있다.

따라서 주어진 배열의 원소(가로,세로 배열)들을 큰값,작은값으로 두고 생각해봐야한다.

가로 6, 세로 16 -> (16,6) 이렇게 생각하기!

[[14,4],[19,6],[6,16],[18,7],[7,11]]

만약 이렇게 배열이 주어진다면,

[[14,4],[19,6],[16,6],[18,7],[11,7]]

이렇게 바꿔서 생각해볼 수 있고

모든 명함을 수납하기 위해선 0인덱스 자리에서 가장 큰 수(19)와 1인덱스 자리에서 가장 큰 수(7)를  곱하면된다 -> 19*7 

문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항
numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

def solution(numbers):
    numbers = [str(i) for i in numbers] # => list(map(str,numbers))
    numbers.sort(key=lambda x:x*3,reverse=True) # ex. '999'>'343434' 문자열 비교연산은 아스키코드로 진행하므로 '999'가 더 큼
    return str(int(''.join(numbers))) # numbers가 [0,0,0] 으로 들어오면 000 이렇게 값나옴. 따라서 int로 정수 0만들어주고 문자열로 출력하라했으니까 다시 str로 감싸줌

>>> 참고

제한사항에서 'numbers의 원소는 0 이상 1,000 이하입니다.' 이 부분을 힌트로 생각해야한다.

원소는 1000이하이므로 곱하기 3하여 길이를 최소 3자리로 만들어 문자 비교연산을 하면 된다.

문제 설명
H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한사항
과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예

입출력 예 설명
이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

def solution(citations):
    citations.sort(reverse=True) # h의 최댓값 찾기위해 내림차순으로 정리
    print(citations)
    for i in range(0, len(citations)+1): 
        hindex = 0
        for item in citations:
            if item >= i: # i번 인용이 item번인용보다 작거나 같으면 hindex증가
                hindex += 1
        if i >= hindex: # "h번 이상" 인용된 논문이 "h편 이상"
            break
    return hindex

>>> 참고

문제를 잘 읽기.

중요 포인트 : h번 이상 인용된 논문이 h편 이상!

hindex의 최댓값은 배열의 길이이다. (h번 이상 인용 h편 이상 ->> 'h편'을 통해 h는 아무리커도 배열크기인 것을 알 수 있음.)

1. 우선순위 큐(Priority Queue)

우선순위가 가장 높은 순서대로 추출된다.

* 큐(Queue) : 선입선출(FIFO), 가장 먼저 삽입된 데이터가 가장 먼저 추출된다. 

2. 힙(Heap)

데이터에서 최대값과 최소값을 가장 빠르게 찾을 수 있도록 만들어진 이진 트리

최대값을 구하기 위한 구조(최대힙, Max Heap), 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류 가능

3. 우선순위 큐 / 힙

우선순위 큐를 구현할 때는 시간 복잡도 측면에서 힙을 이용하는 것이 훨씬 효율적이다.

4. 파이썬에서 제공하는 라이브러리

우선순위큐 라이브러리

from queue import PriorityQueue

pq = PriorityQueue() # 우선순위 큐 생성
pq = PriorityQueue(maxsize=10) # 최대 크기를 10인 우선순위큐

pq.put((1,'a'))
pq.put((0,'b')) # 원소 추가

print(pq.get()) # 출력 : (0, 'b') -> 추출되며 큐에서 삭제됨
print(pq.qsize()) # 출력 : 1

힙큐 라이브러리

import heapq

arr = []
heapq.heappush(arr,3) # 힙 원소 추가
heapq.heappush(arr,1)
heapq.heappush(arr,2)

print(arr) # 출력 : [1, 3, 2]

heapq.heappop(arr)

print(arr) # 출력 : [2, 3]

arr2 = [10,2,7,11]
heapq.heapify(arr2) # 배열을 힙으로 변경

print(arr2) # 출력 : [2, 10, 7, 11]

문제 설명
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항
scoville의 길이는 2 이상 1,000,000 이하입니다.
K는 0 이상 1,000,000,000 이하입니다.
scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

입출력 예 설명
스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

import heapq
def solution(scoville, K):

    heapq.heapify(scoville) # 배열을 최소힙으로 구현 (최소 데이터 뽑아내기위해)
    cnt = 0 # cnt = 섞은 횟수
    while(True):
        onedata = heapq.heappop(scoville) # 가장 작은값 뽑아냄

        if len(scoville)==0 and onedata < K: # scoville 배열의 길이가 0이고 onedata값이 K보다 작으면 반복문종료
            cnt = -1
            break

        if onedata < K: # 스코빌 지수가 7보다 작으면
            twodata = heapq.heappop(scoville) # 또 그 다음 작은값 꺼내고
            heapq.heappush(scoville, onedata + (twodata*2)) # 두개 데이터 연산한 후 scoville배열에 넣어줌
            cnt += 1
        else: # onedata는 배열의 가장 작은 값 가져오는데 그게 K보다 같거나 크면 반복문 종료
            break

    return cnt

문제 설명
배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항
배열 arr의 크기 : 1,000,000 이하의 자연수
배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

입출력 예

def solution(arr):
    answer = []
    prev = arr[0] # 배열 arr 원소별로 비교하기위해 변수에 0인덱스부터 일단 담아둠
    answer.append(prev) # 0인덱스는 return할 배열에 무조건 처음으로 들어가므로 넣어둠

    for i in range(1, len(arr)):
        if arr[i] == prev: # 배열 원소값이 이전 원소값과 똑같다면 continue
            continue
        else :
            answer.append(arr[i]) # 배열 원소값이 이전 원소값과 같지 않다면 return할 배열에 추가
        prev = arr[i]

    return answer

>>> 참고

이 문제는 스택/큐 문제이다.

큐는 FIFO 구조로, 먼저 들어간 데이터가 먼저 추출된다라는 것을 보았을 때

문제에서 배열에 중복되는 값 중 먼저 들어가있는 데이터만 추출되어 return할 배열에 들어가게 된다는 것을 확인.

스택은 LIFO  구조로, 제일 나중에 들어간 데이터부터 추출된다는 것을 보았을 때

이를 활용해서 코드를 구성한다면 배열에서 가장 마지막 원소를 가져오는 arr[-1:]를 쓸 수 있다.

def solution(arr):

    answer = [] # 리턴할 배열

    for i in arr:
        if answer[-1:] == [i]: # 리턴할 배열에서 마지막 데이터 꺼내와 비교
            continue
        answer.append(i)

    return answer

문제 설명
당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
두 번째(1번), 세 번째(2번) 폰켓몬을 선택
두 번째(1번), 네 번째(3번) 폰켓몬을 선택
세 번째(2번), 네 번째(3번) 폰켓몬을 선택
이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항
nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

입출력 예

입출력 예 설명
- 입출력 예 #1
문제의 예시와 같습니다.

- 입출력 예 #2
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

- 입출력 예 #3
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 2번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

def solution(nums):
    answer = []
    cnt = 0

    for i in range(len(nums)):
        if nums[i] not in answer:
            answer.append(nums[i])
            cnt += 1
            if cnt == int((len(nums)))*1/2:
                break

    return cnt

>>> 참고

다른 사람의 풀이를 확인하고,

중복제거(set)을 이용하면 된다는 것을 알았다.

문제에서 두 가지 경우로 나뉜다.

첫번째, n/2마리 > 중복되지않는값들의 합 : '중복되지않는 값들의 합'을 return해야함

두번째, n/2마리 < 중복되지않는값들의 합 : 'n/2'를 return해야함

따라서, 두가지 경우 모두 작은 값을 return하므로 min()을 사용하면된다.

def solution(nums):

    return min(int(len(nums)/2), len(set(nums)))

>>> 참고 2

폰켓몬 문제는 해시 문제 중 하나다.

따라서 key, value를 이용하여 문제를 풀어봤는데 min,set 이용한게 더 낫지만 참고용으로 보기.

def solution(nums):
    # 해시 함수 이용 (key, value)
    ponketmon = {} # 딕셔너리 생성(key, value사용하기위한)

    for i in range(len(nums)):
        if nums[i] in ponketmon:
            ponketmon[nums[i]] += 1
        else:
            ponketmon[nums[i]] = 1

    # print(ponketmon) # {3: 3, 2: 2, 1: 1}
    return  len(ponketmon) if len(ponketmon) < int(len(nums)*1/2) else int(len(nums)*1/2)

문제 설명
배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항
array의 길이는 1 이상 100 이하입니다.
array의 각 원소는 1 이상 100 이하입니다.
commands의 길이는 1 이상 50 이하입니다.
commands의 각 원소는 길이가 3입니다.

입출력 예

입출력 예 설명
[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

def solution(array, commands):
    # array에서 commands의 0번째 요소값부터 1번째 요소값까지 자른후, 정렬하고 거기서 2번째 요소값을 순서로 갖는 값 가져오기

    splitlist = list()

    for i in range(len(commands)):
        arr1 = array[commands[i][0]-1:commands[i][1]] # 자르기
        arr1.sort() # 정렬하기
        splitlist.append(arr1[commands[i][2]-1]) # 해당값 찾아 리스트에 넣기


    return splitlist

>>> 참고

다른 사람의 풀이를 확인하니 나처럼 for문을통해 len으로 range잡아서 [i]에 집어넣으며 해도되지만,

for i,j,k in commands 이렇게 하여 commands의 수를 직접 뽑아오면 더 좋은 것 같다.

def solution(array, commands):
    # array에서 commands의 0번째 요소값부터 1번째 요소값까지 자른후, 정렬하고 거기서 2번째 요소값을 순서로 갖는 값 가져오기

    splitlist = list()

    for i,j,k in commands:
        arr1 = array[i-1:j] # 자르기
        arr1.sort() # 정렬하기
        splitlist.append(arr1[k-1]) # 해당값 찾아 리스트에 넣기

    return splitlist