Chapter 4. Sorting Algorithm

알고리즘 스터디 4주차의 주제는 정렬 알고리즘이다.

정렬 알고리즘이란?

어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 방법들을 정렬 알고리즘이라고 한다.

문제풀이

이번 주는 강의실 배정(골드 5), 버블 정렬(골드 1)이라는 문제들을 풀어보았다.

강의실 배정(골드 5)

해당 문제는 아래 링크에서 풀어볼 수 있다.
https://www.acmicpc.net/problem/11000

전체코드

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
times = sorted([list(map(int, input().split())) for _ in range(N)])

rooms = list()
heappush(rooms, times[0][1])

for i in range(1, N):
    if times[i][0] >= rooms[0]:
        heappop(rooms)
    heappush(rooms, times[i][1])

print(len(rooms))

S와 T를 입력받을 때마다 둘을 리스트에 담아, 모든 S와 T로 이루어진 리스트들을 다시 times 라는 리스트 안에 담고 sorted()를 이용해 정렬했다.
rooms라는 최소값을 쉽게 얻을 수 있는 heap트리를 이용해 rooms의 최상단 노드와 times[i]의 시작 시간(times[i][0])을 비교했다.

만약 times[i][0]이 rooms[0]보다 크거나 같으면 해당 rooms[0]의 수업이 끝난 후 times[i]의 수업을 시작할 수 있는 것이므로, rooms[0]를 삭제해주고 times[i][1]을 추가해준다.

만약 times[i][0]이 rooms[0]보다 작으면 위 상황과 달리 rooms[0]를 삭제하지 않고 그냥 rooms에 times[i][1]를 추가해준다.

위 방법대로 하면 rooms의 길이가 강의실의 최소 개수를 뜻한다.

버블 정렬(골드 1)

해당 문제는 아래 링크에서 풀어볼 수 있다.
https://www.acmicpc.net/problem/1838

전체 코드

import sys

input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

not_sort = {}
sort = {}
answer = 0

for i in range(N):
    not_sort[A[i]] = i

A.sort()

for i in range(N):
    sort[A[i]] = i

for i in A:
    answer = max(answer, not_sort[i] - sort[i])

print(answer)

i는 리스트 A의 정렬 전과 후를 비교하여 가장 많이 이동한 요소의 인덱스 값 차이가 정답이 되는 문제다.

따라서 리스트 A를 정렬하기 전의 인덱스 값이 필요하다.
키로 리스트 A의 값을 전달하면 정렬하기 전의 인덱스가 값으로 나오는 not_sort라는 딕셔너리를 만들었다.

그 다음, 리스트 A를 sort()를 이용해 정렬했다.
not_sort와 마찬가지로 키로 배열 A의 값을 전달하면 정렬한 후의 인덱스가 값으로 나오는 sort라는 딕셔너리도 만들었다.

for문을 통해 리스트 A의 값을 하나씩 꺼내어 인덱스 차이를 max()를 통해 기존 최대값과 계속 비교해 나가며 정답을 찾는다.