대기업 코딩테스트 준비 5 : 정렬

ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. (github.com)

ndb796/python-for-coding-test

정렬

• 데이터를 특정한 기준에 따라서 순서대로 나열
  • 그리디랑 자주 쓰임
  • 이진 탐색

 

• 계수 정렬을 꼭 써야 하는 경우가 아니면 기본 제공 정렬 라이브러리를 활용한다.

선택 정렬

for i in range(len(arr)):
    minIdx = i
    for j in range(i+1,len(arr)):
        if arr[minIdx] > arr[j]:
            minIdx = j
    arr[i],arr[minIdx] = arr[minIdx],arr[i]

퀵 정렬

• 호어 분할
  • 0번째 인덱스가 피벗
  • NlogN
    • 각각이 절반으로 나누어 진다고 생각하면 높이가 logN
    • N의 연산이 logN번 수행

def quick_sort(arr):
    def sort(low, high):
        if high <= low:
            return

        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)

    def partition(low, high):
        pivot = arr[(low + high) // 2]
        while low <= high:
            # 오름차순 정렬
            while arr[low] < pivot: # 피벗보다 작으면 패스
                low += 1 
            while arr[high] > pivot: # 피벗보다 크면 패스
                high -= 1
            if low <= high: # 오른쪽이 피봇보다 작고 왼쪽이 크면 바꿔줌
                arr[low], arr[high] = arr[high], arr[low] # 다른 언어에서는 tmp 필요
                low, high = low + 1, high - 1
        return low

    return sort(0, len(arr) - 1)

삽입 정렬

• 순서 유지
  • 이미 정렬된 인풋

for i in range(1,len(arr)):
    for j in range(i,0,-1):
        if arr[j] < arr[j-1]:
            arr[j], arr[j-1] = arr[j-1],arr[j]
            continue
        break

계수 정렬

• O(N+K)
  • 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능
  • 0이상 100 이하 성적 데이터
    • 가장 큰 데이터와 작은 데이터 차이가 너무 크면 못씀
    • 모든 범위를 담을 수 있는 크기의 리스트 선언해야 함
      • 차이가 1,000,000이면
        • 0부터 1000000까지 1,000,001 공간 선언
• 예시
  • 759031629148052
  • 가장큰 수 9부터 0까지 공간 10개 할당
    • arr[10]
  • arr 해당 인덱스에 카운트
  • arr[1] == 2
  • for문 돌면서 갯수만큼 붙인다.

• 이것만 써야 하는 경우는 거의 안나옴
• 공간 비효율 문제

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

병합 정렬

def merge_sort(arr):
    def sort(low, high):
        if high - low < 2: # list 길이 <=1:
            return
        mid = (low + high) // 2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high):
        temp = []
        l, h = low, mid
        # 둘다 안소진
        while l < mid and h < high:
            if arr[l] < arr[h]:
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[h])
                h += 1
        # 뒤 먼저 소진
        while l < mid:
            temp.append(arr[l])
            l += 1
        # 앞 먼저 소진    
        while h < high:
            temp.append(arr[h])
            h += 1

        for i in range(low, high):
            arr[i] = temp[i - low]

    return sort(0, len(arr))

• sorted의 key 매개변수

sorted(arr,key=setting)

def setting(arr):
    return arr[1]

• 기본정렬 라이브러리를 쓰고
• 계수 정렬 가능하면 활용
  • 1초 1억

1. 국영수

n = int(input())
students = [] # 학생 정보를 담을 리스트

# 모든 학생 정보를 입력 받기
for _ in range(n):
    students.append(input().split())

'''
[ 정렬 기준 ]
1) 두 번째 원소를 기준으로 내림차순 정렬
2) 두 번째 원소가 같은 경우, 세 번째 원소를 기준으로 오름차순 정렬
3) 세 번째 원소가 같은 경우, 네 번째 원소를 기준으로 내림차순 정렬
4) 네 번째 원소가 같은 경우, 첫 번째 원소를 기준으로 오름차순 정렬
'''
students.sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

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

2. 안테나

• Median(중간값)에 해당하는 위치의 집에 안테나를 설치한다.
  • 중간값에서 벗어나는 위치에 안테나를 설치하는 경우 총합은 계속 증가한다.

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

# 중간값(median)을 출력
print(a[(n - 1) // 2])

3. 실패율

• 잘 구현한다.

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

4. 카드 정렬하기

• a2 = k1 + k2 = 10 + 20
• a3 = 2a2 + k3 = 2(k1+k2) + k3
• a4 = 2a3 + k4 ... = 2^2a2 + 2k3 +k4
• an = 2^n-2a2 + ...+2an-1+kn -> 앞에 있는 숫자가 클수록 더 커진다.

• 항상 가장 작은 크기의 두 카드 묶음을 알기위해 가장 효율적인 자료구조
  • 우선순위 큐 == heaqp

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)