개발자 아지트

문제설명

매운 것을 좋아하는 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.

스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.

새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5

가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

 2.

스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.

새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13

가진 음식의 스코빌 지수 = [13, 9, 10, 12]

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

문제 해결 방법

heapq 모듈을 사용하여 해결하였다. 

코드 구현

import heapq

def solution(scoville, K):
    answer = 0
    
    # 섞은 음식의 스코빌 지수는 newFood 변수로 표시 
    # 최소 값을 빠르게 찾기 위해서 힙을 쓰는듯 !!
    heapq.heapify(scoville)
    
    cnt = 0 
    #cnt는 음식 섞은 횟수 
    while 1:
        if scoville[0] >= K:
            answer  = cnt
            break
        
        if len(scoville) == 1:
            answer = -1
            break
    
        #print(heapq.nsmallest(2, scoville))
        #result = heapq.nsmallest(2, scoville)
        # 위에 두줄은 시행착오의 흔적이라 놔둠
        
        one = heapq.heappop(scoville)
        two = heapq.heappop(scoville)
        newFood = one + (two * 2)
        heapq.heappush(scoville, newFood)

        cnt +=1
    
    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

처음에 scoville의 최소값을 구할 때 heapq.nsmallest함수를 사용해서 구했더니 시간 복잡도가 많이 잡아먹어서 채점 항목은 효율점에서 점수를 다 깎아먹었다. 

찾아보니까 heapq.nsmallest와 같은 함수는 최소값을 찾을 때 정렬을 한번 해서 그런가 O(n log n)의 시간복잡도를 초래한다. 그래서 해당 함수를 사용하지 않고 어떻게하면 최소값을 찾아서 사용할까 했는데 heappop함수를 활용하면 될 일이였다. 

어려웠던 점

없음 !

안녕하세요. 지금 기분이 굉장히 좋습니다.!!!!! 자료구조를 공부하고 이렇게 통쾌하게 문제를 풀어본 경험은 오늘이 처음입니다!!! 세상 사람들아!! 내가 이 문제를 드디어 자료구조로 풀었다!!!!!!

문제설명

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

35

문제 해결 방법

우선 실버2를 푼다는 생각에 넘넘 긴장되고 겁이나서 페이지 하단에 있는 '알고리즘 분류'를 먼저 보고 참고하여 문제를 풀었다. 해당 문제는 우선순위 큐에 속한다. 따라서 파이썬의 heapq모듈을 활용하여 해당 문제를 풀고자 했다. 

코드 구현

import heapq

n = int(input())
#n개의 줄에 n개의 수가 주어짐 
#n개의 줄에 n개의 원소가 들어가게끔 만들어야함
list_list = []
total=[]
for i in range(n): # 이렇게 쓰면 딱 원소가 5개임
    #print('i', i)
    list_list.append(list(map(int, input().split())))
    
    
    for j in range(n):
        total.append(list_list[0][j])
    list_list=[]

    heapq.heapify(total)
    answer = heapq.nlargest(n,total)

    if i==0: 
        pass
    else:
        #print('i', i, 'prev total', total)
        for p in range(n):
            heapq.heappop(total)
    
    #print('i', i, 'total', total)
    #print('i', i, 'answer', answer)
    
   
# total=[]

print(answer[-1])

시간/공간 복잡도

????? 뭘적징

최적화 및 개선

처음에는 '메모리 초과'가 떴다. 엥 메모리초과가 뭐지? 설마 이것이 공간복잡도 인가?? 와우!! 처음 보는 결과다 ㅠㅠ

감격스러운 마음에 막 찾아봤다. 

메모리 초과란?

공간 복잡도를 초과한 경우를 말하고, 공간 복잡도란 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말한다. 

과연내가 어디서 공간을 많이 잡아먹은거지... 첨엔 어떻게 이걸 찾아야 하는건지 잘 모르겠었다. 

그래서 무작정 코드를 다시 봤다.. 코드를 다시 보니까 첫 제출할때는 미처 발견하지 못한 에러들을 3개나 발견했다. !!

혹시나 이 에러를 해결하면 문제를 풀까 해서 다시 제출해봤는데 택도없었다! 

모든 입력을 배열에 저장하면 당연히 메모리 초과입니다. 문제의 메모리 제한은 겨우 8MB입니다. 아무리 작은 자료형으로 저장한다고 해도 short형 (2바이트) 천만 개면 약 20MB로 역시 메모리 초과입니다. 입력을 전부 저장하지 않고 푸는 방법을 생각해 보세요. 힌트는 입력되는 정수의 범위에 있습니다. (백준 가이드)

그래서 설마 내가 total 리스트에 모든 n개의 원소 n개 받은것을 풀어서 넣고 갖고 다닌것이 공간복잡도를 많이 잡아먹는건가 싶어서 그 부분을 좀 최적화 해봤다. 그랬더니 

느낀점

기분이 너무 좋다 진짜!!! 공부할 맛 난다. 오늘 큰거 깨달았다.

코테 준비 및 알고리즘 공부는 이런식으로 하면 되겠구나 

자료구조 및 알고리즘 미리 공부 후에 문제 풀이하기~

근데 한편으로는 아쉽다 이렇게 하면되는걸.. 그동안 맨땅의 헤딩을 즐겨했던 나..
그래서 사기가 많이 떨어졌던 과거의 나... 

나야 고생했고 앞으로 잘해보자~ ^^