[이것이 취업을 위한 코딩테스트이다 with 파이썬] Ch.14 정렬 문제

📌한 장으로 보는 알고리즘

 

정렬 in Python
 - (보통) 표준 라이브러리 사용
 - (특이경우) 계수 정렬을 이용하여 매우 빠르게 정렬 해야하는 경우

다양한 알고리즘 사용(정렬)
 - 이진 탐색 전 (데이터 정렬되어 있을 때 사용할 수 있음)
 - 크루스칼 알고리즘 (간선의 정보 정렬 과정 필요)

---

📌Q. 23 국영수

 

✔️문제유형

정렬

 

✔️문제

10825번: 국영수

 

✔️나의 문제풀이

n = int(input())
class_dh = []

for i in range(n):
    name, kor, eng, math = input().split()
    student = (name, int(kor), int(eng), int(math))
    class_dh.append(student)

class_dh.sort(key = lambda st: (-st[1], st[2], -st[3], st[0]))

for j in range(len(class_dh)):
    print(class_dh[j][0])

 

✔️다른 사람의 문제풀이

(p.276)

- 튜플 정렬

• 첫 번째 원소 순서로 정렬 → (첫 번째 같은 경우) 두 번째 원소 순서로 정렬 → (두 번째 같은 경우) 세 번째 원소 순서로 정렬

a = [(5,1,5), (3,5,5), (3,1,9), (3,1,1)]
a.sort()

# 정답
[(3,1,1), (3,1,9), (3,5,5), (5,1,5)]

n = int(input())
students = []

# 모든 학생 정보를 입력받기
for _ in range(n):
	students.append(input().split())
    
students.sort(key = lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0])

# 정렬된 학생 정보에서 이름만 출력
for student in students:
	print(student[0])

 

 

✔️리뷰

 - 파이썬 정렬 다중 조건

• 비교할 아이템의 요소가 복수 개일 경우, 튜플로 그 순서를 내보내주면 된다.
  • ex. sorted(e, key = lambda x : (x[0], -x[1]))
  • -를 붙이면, 현재 정렬차순과 반대로 하게 된다.

파이썬 정렬, 다중 조건으로 한 번에 하기.

---

📌Q. 24 안테나

 

✔️유형

수학, 정렬, 그리디 알고리즘

 

✔️문제

18310번: 안테나

 

✔️나의 문제풀이

 - 시간초과

• 정석대로 푼 결과, 시간초과 발생

n = int(input())
home = list(map(int,input().split()))
antener = []
total = 0

for main in home:
    total = 0
    for next_home in home:
        total += (abs(main - next_home))
    antener.append(total)

print(home[antener.index(min(antener))])

 

 - 정답

• 아이디어 : 중간에 위치한 값들이 거리가 제일 적게 차이나지 않을까?
  • home의 len이 홀수인 경우 - 가장 중간 값
  • home len이 짝수인 경우 - len(home)//2 -1값

n = int(input())
home = list(map(int,input().split()))
home.sort()

if len(home) % 2 != 0:
    print(home[len(home)//2])
else:
    print(home[len(home)//2-1])

 

✔️다른 사람의 문제풀이

• 핵심 아이디어 : 정확히 중간값에 해당하는 위치 → 모든 집의 거리의 총합이 최소
     중간값에서 벗어난 위치일 때, 거리의 총합 증가

n = int(input())
data = list(map(int,input().split())
data.sort()

print(data[(n-1)//2])

 

---

📌Q. 25 실패율

 

✔️유형

계수 정렬

 

✔️문제

프로그래머스

 

✔️나의 문제풀이

# N : 전체 스테이지 개수, stages: 사용자가 멈춰있는 스테이지 번호
def solution(N, stages):
    answer = []
    fail = dict()
    
    down = [0] * (N+1)
    up = [0] * (N+1)
    
    for stage in stages:
        up[stage - 1] += 1
        for j in range(stage):
            down[j] += 1
    
    for i in range(len(down)-1):
        if up[i] == 0 or down[i] == 0:
            fail[i] = 0
        else:
            fail[i] = up[i]/down[i]
    
    
    fail_sort = sorted(fail.items(), reverse = True, key = lambda x:x[1])
    
    for k in range(len(fail_sort)):
        answer.append(fail_sort[k][0] + 1)
    
    return answer

 

 

✔️다른 사람의 문제풀이

def solution(N, stages):
    answer = []
    length = len(stages) # stage 1은 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, kwy = lambda t: t[1], reverse = True)

    # 번호 출력
    answer = [i[0] for i in answer]
    return answer

 

✔️리뷰

 - 각 숫자별로 필요한 개수 : count() 함수 사용

 - 인덱스를 이용하여 정렬해야하는 경우 : tuple로 넣어서 조건 정렬 

---

📌Q. 26 카드 정렬하기

 

✔️유형

자료구조, 그리디 알고리즘, 우선순위 큐

 

✔️문제

1715번: 카드 정렬하기

 

✔️나의 문제풀이(다른 사람 문제풀이 참고함)

import heapq

n = int(input())
pre, cur = 0,0
card = []

for _ in range(n):
    heapq.heappush(card, int(input()))

ans = 0

while len(card) > 1:
    pre = heapq.heappop(card)
    cur = heapq.heappop(card)
    ans += (pre+cur)

    heapq.heappush(card, (pre+cur))

print(ans)

 

 

✔️다른 사람의 문제풀이

- 핵심 아이디어 : 항상 가장 작은 크기의 두 카드 묶음을 합쳤을 때, 최적의 해 보장

• 무조건 가장 작은 크기의 두 카드 묶음 합침 → 그리디, 우선순위 큐 사용
• 우선순위 큐 특징
  • 원소를 넣었다 빼는 것만으로 정렬된 결과 얻음
  • 파이썬 heapq 라이브러리 이용

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)
    two = heapq.heappop(heap)
    # 카드 묶음을 합쳐 다시 삽입
    sum_value = one + two
    result += sum_value
    heapq.heappush(heap, sum_value)

print(result)

 

 

✔️리뷰

- 우선순위 큐(heapq) : 정렬된 결과 자동으로 얻을 수 있음

  →  최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리

• heapq.heappop(리스트) : 가장 작은 원소 값
• heapq.heappush(리스트, 원소) : 리스트에 원소 삽

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기