04-4. 정렬 문제풀이

📝문제1. 프로그래머스 42889번(실패율)

- 문제

https://programmers.co.kr/learn/courses/30/lessons/42889

- 나의 코드💻

def solution(N, stages):
    answer = []
    array = []
    save = []
    
    count = 0
    stage_num = 1
    
    for i in stages:
        if i >= stage_num:
            array.append(stage_num)
        for k in array:
            if k > i:
                count += 1
            answer.append() 
    
    return answer

- 정답 코드💻

def solution(N, stages):
    answer = []
    length = len(stages)
    
    # 스테이지 번호를 1부터 N까지 증가시키며
    for i in range(1, N+1):
        # 해당 스테이지에 머물러 있는 사람의 수 계산
        count = stages.count(i)
        
        # 실패율 계산
        if length == 0:
            fail = 0
        else:
            fail = count / length
            
        # 리스트에 (스테이지 번호, 실패율) 원소 삽입
        answer.append((i, fail))
        length -= count
        
    # 실패율을 기준으로 각 스테이지를 내림차순 정렬
    answer = sorted(answer, key=lambda t: t[1], reverse=True)
    
    # 정렬된 스테이지 번호 출력
    answer = [i[0] for i in answer]
    return answer
        

- 비교 분석📖

프로그래머스의 카카오 문제라 또 이유없이 쫄았는데 생각보다는 간단했던 문제.. 비록 틀리긴 했지만!

책에 있는 코드를 따라쳐봤는데 이상하게 프로그래머스에서 잘 작동하지 않는다. 나중에 다시 점검해보겠다.

---

📝문제2. 백준 1715번(카드 정렬하기)

- 문제

https://www.acmicpc.net/problem/1715

문제
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력
첫째 줄에 최소 비교 횟수를 출력한다.

예제 입력
3
10
20
40
예제 출력
100

- 나의 코드💻

n = int(input())
array = []
for _ in range(n):
    array.append(int(input()))
array.sort()

def fibo(i):
    if i <= 0:
        return array[0]
    return array[i] + array[i-1]

print(fibo(n-1))

- 정답 코드💻

import heapq

n = int(input())

# 힙(heap)에 초기 카드 묶음을 모두 삽입
heap = []
for i in range(n):
    data = int(input())
    heapq.heappush(heap, data)

result = 0

# 힙(heap)에 원소가 1개 남을 때까지
while len(heap) != 1:
    # 가장 작은 2개의 카드 묶음 꺼내기
    one = heapq.heappop(heap)  # heappop : 가장 작은 항목을 팝하고 반환
    two = heapq.heappop(heap)
    # 카드 묶음을 합쳐서 다시 삽입
    sum_value = one + two
    result += sum_value
    heapq.heappush(heap, sum_value)

print(result)

- 비교 분석📖

이 문제의 핵심 아이디어는 항상 가장 작은 크기의 두 카드 묶음을 합쳤을 때 최적의 해를 보장한다는 점이다. 따라서 매 상황에서 무조건 가장 작은 크기의 두 카드 묶음을 합치면 된다는 점에서, 이 문제는 그리디 알고리즘으로도 분류할 수 있다.

항상 가장 작은 크기의 두 카드 묶음을 얻는 과정을 효과적으로 수행할 수 있는 자료구조는 바로 우선순위 큐이다. 우선순위 큐는 원소를 넣었다 빼는 것만으로도 정렬된 결과를 얻을 수 있다. 우선순위 큐는 힙 자료구조를 이용해서 구현할 수 있으며, 파이썬에서는 heapq 라이브러리를 지원하고 있다.

ex)
10 20 40 -> 30 40 -> 70
50 20 10 40 -> 50 30 40 -> 50 70

heapq 문법을 잘 몰라서 이 문서를 참고했다.
https://docs.python.org/ko/3/library/heapq.html

---

📝문제3. 프로그래머스 42746번(가장 큰 수)

- 문제

https://programmers.co.kr/learn/courses/30/lessons/42746

- 나의 코드💻

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))
    numbers.sort(reverse=True)
    answer = ''.join(numbers)
    
    return answer

- 정답 코드💻

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key = lambda x: x*3, reverse=True)
    
    return str(int(''.join(numbers)))

- 비교 분석📖

- lambda x: x*3 -> numbers의 인자 각각의 문자열을 3번 반복한다는 의미이다. x*3을 하는 이유는 num의 인수값이 1000 이하이므로 3자리수로 맞춘 뒤 비교를 해야 하기 때문이다. 이 문제의 핵심이라고 할 수 있다.

ex) 두 번째 예시를 보면 알 수 있다. 사전값으로만 정렬을 한다면 [9, 5, 34, 30 ,3] 이렇게 정렬된다. 그러나 3이 30보다 앞에 와야 하기 때문에 잘못되었다. numbers는 1000 이하의 숫자이므로 최댓값을 생각해 3을 곱해줬고, 3을 곱하게 되면 [999, 555, 343434, 303030, 333] 이 되니 정렬하면 [999, 555, 323232, 333, 303030]이 된다.

• 마지막에 int로 변환한 뒤 다시 str로 변환하는 이유는 모든 값이 0일 때(즉, '000'일 때를 처리하기 위해)를 대비해서이다.

• 리스트 안의 원소를 문자열로 바꾸는 법 : list(map(str, array))
  -> 사전값으로 배열을 정렬할 수 있다.

• 리스트를 문자열로 합치기 : ''.join(array)

참고 블로그
https://wooaoe.tistory.com/82
https://velog.io/@insutance/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Python-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%88%98

---