[정렬 알고리즘] 문제1 - 위에서 아래로(178p)

[이코테] 문제1 - 위에서 아래로(178p)

(한줄평) 정렬 알고리즘 예제 문제 수준으로 여러가지 정렬 알고리즘을 연습해볼 수 있는 문제! 퀵 정렬만 조금 더 연습해보면 좋을 듯!

이 문제는 n개의 수가 주어지고 내림차순 정렬을 하는 문제다.

수의 개수가 500개 이하로 매우 적고 모든 수는 1이상 100,000이하로 어떠한 정렬 알고리즘을 사용해도 해결할 수 있다.

(풀이1) 파이썬 기본 정렬 라이브러리 이용

풀이 시간: 3분 이내

1) 문제 해결 아이디어

가장 단순한 방법으로 sorted()를 이용하여 해결하였다.

 

2) 소스코드

n = int(input())
arr = [int(input()) for _ in range(n)]  # n개의 수

# 1. 정렬 라이브러리(내림차순)
#print(*sorted(arr, reverse=True))

 

(풀이2) 선택 정렬

풀이 시간: 3분 이내

1) 문제 해결 아이디어

선택 정렬을 이용하였고 내림차순 정렬이므로 최댓값을 맨 앞으로 가져오는 것을 반복한다.

 

2) 소스코드

n = int(input())
arr = [int(input()) for _ in range(n)]  # n개의 수

# 2. 선택 정렬(내림차순)
for i in range(len(arr)):
  max_idx = i  # 최댓값 인덱스
  for j in range(i + 1, len(arr)):
    # 최댓값 인덱스 갱신
    if arr[max_idx] < arr[j]:  max_idx = j
  # 최솟값 & 맨 앞 값 swap
  arr[max_idx], arr[i] = arr[i], arr[max_idx]

print(*arr)

(풀이2) 삽입 정렬

풀이 시간: 10분 이내

1) 문제 해결 아이디어

첫번째 값은 정렬되어있다고 가정하고 두번째 값부터 정렬을 시작한다.

내림차순 정렬이므로 현재값이 앞의 값보다 크면 swap한다. 아니면 break로 탈출한다.

 

2) 소스코드

n = int(input())
arr = [int(input()) for _ in range(n)]  # n개의 수

# 3. 삽입 정렬(내림차순)
for i in range(1, len(arr)):
  for j in range(i, 0, -1):
    # 현재값이 앞의 값보다 크면 swap
    if arr[j] > arr[j - 1]:
      arr[j], arr[j - 1] = arr[j - 1], arr[j]
    # 현재값이 앞의 값보다 작거나 같다면 탈출
    else:  break
print(*arr)

(풀이4) 퀵 정렬

풀이 시간: 20분 이내

1) 문제 해결 아이디어

처음에 left를 start + 1 로 초기화해야하는데 start로 초기화하는 바람에 무한루프를 돌았다.

 

2) 소스코드

n = int(input())
arr = [int(input()) for _ in range(n)]  # n개의 수

# 4. 퀵 정렬
def quickSort(arr, start, end):
  # 원소 개수가 1개 이하면 종료
  if start >= end:  return

  pivot = start  # pivot은 첫번째 원소로
  left = start + 1  # 왼쪽에서부터 찾는 작은 수(pivot 다음 수부터)
  right = end    # 오른쪽에서부터 찾는 큰 수

  # 2개로 분할
  while True:
    # pivot보다 작은 수 찾기
    while left <= end and arr[left] >= arr[pivot]: 
      left += 1
    # pivot보다 큰 수 찾기
    while right >= start + 1 and arr[right] <= arr[pivot]:
      right -= 1
    # 엇갈렸다면 pivot과 right swap
    if left > right:
      arr[pivot], arr[right] = arr[right], arr[pivot]
      break
    # 엇갈리지않았다면 left와 right swap
    else:
      arr[left], arr[right] = arr[right], arr[left]
  # 분할 후 왼쪽, 오른쪽 부분에 대해 각각 내림차순 정렬
  quickSort(arr, start, right - 1)
  quickSort(arr, right + 1, end)
  
quickSort(arr, 0, len(arr) - 1)
print(*arr)

 

(풀이5) 계수 정렬

풀이 시간: 3분 이내

1) 문제 해결 아이디어

입력되는 수의 범위가 1이상 100,000이하로 주어졌기 때문에 카운팅을 위해 크기가 100001인 리스트(counting)을 0으로 초기화하여 생성하였다. 내림차순 정렬이므로 역순으로 출력해야한다.

 

2) 소스코드

n = int(input())
arr = [int(input()) for _ in range(n)]  # n개의 수

# 5. 계수 정렬
counting = [0] * (100001)  # 1이상 100,000이하의 자연수이므로

for i in arr:
  counting[i] += 1

for i in range(len(counting) - 1, -1, -1):
  for j in range(counting[i]):
    print(i, end=' ')