[programmers] 더 맵게, 가장 큰 수

💡 오늘의 학습 키워드

📌  힙 정렬

 

🥈 더 맵게

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

 

문제 설명

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

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

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

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

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

 

💡 내가 해결한 방식은?

단순 정렬을 통한 풀이 (시간 초과)

def solution_1(scoville, K):
    # 모든 음식이 스코필 지수 이상이 될 때까지 반복 
    mix_cnt = 0
    
    while True:
        # 음식 정렬
        scoville.sort()
        
        # 음식 섞기
        new_sc = scoville[0] + (scoville[1] * 2)
        scoville.pop(0) 
        scoville.pop(1)
        scoville.append(new_sc)
        
        # 가장 작은 원소가 스코빌 지수 이상일 경우 break
        if scoville[0] >= K:
            break
        
        mix_cnt += 1
    
    
    return mix_cnt

min 함수를 통한 풀이 (시간 초과)

def solution_2(scoville, K):
    # 모든 음식이 스코필 지수 이상이 될 때까지 반복 
    mix_cnt = 0
    
    while True:
        # 가장 작은 원소가 스코빌 지수 이상일 경우 break
        if min(scoville) >= K:
            break
        min_sc_a = min(scoville)
        scoville.remove(min_sc_a)
        min_sc_b = min(scoville)
        scoville.remove(min_sc_b)
        
        
        # 음식 섞기
        new_sc = min_sc_a + (min_sc_b * 2)
        
        # 섞은 음식 추가
        scoville.append(new_sc)
        
        # 섞은 횟수 추가
        mix_cnt += 1
    
    return mix_cnt

힙 정렬을 통한 풀이

import heapq

def solution_3(scoville, K):
    # 효율적인 최소 값 접근 방식 필요 -> 힙 정렬
    heapq.heapify(scoville)

    # 섞은 횟수
    mix_cnt = 0
    
    # 스코빌 지수 K 이상 만들 수 없는 경우 -1 리턴
    while scoville:
        # 가장 맵지 않은 스코빌 지수 음식 추출
        min_spicy_a = heapq.heappop(scoville)

        # 스코빌 지수가 모두 K 이상일 경우
        if min_spicy_a >= K:
            break

        # 스코빌 지수를 K 이상 만들 수 없는 경우
        if not scoville:
            return -1
        
        min_spicy_b = heapq.heappop(scoville)

        # 음식 섞기
        new_spicy = min_spicy_a + (min_spicy_b * 2)
        heapq.heappush(scoville, new_spicy)
        
        mix_cnt += 1

    return mix_cnt

---

🥈 가장 큰 수

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

 

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고,이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때,
순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

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

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

 

💡 내가 해결한 방식은?

 

---

✍️  TIL