오늘의 알고리즘(백준 2751)

1. 백준 2751, 수 정렬하기 2

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

2751번: 수 정렬하기 2

 

---

2. 요구사항 

- 첫번째 입력값 N은 몇개의 수가 입력되는 지를 정한다. 

- N개의 수가 입력되고 나면 이를 오름차순으로 정리해야 한다. 

 

---

3. 어떻게 풀어야 할까? 

- int(input())으로 첫번째 입력값 N을 받는다. 

- map을 이용하여 N개의 input을 배열로 정리한다. 

- N개의 요소를 갖는 배열을 오름차순으로 정렬한다. 

- 1개씩 출력한다. 

 

a) 내가 생각한 코드 

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

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

for data in array:
  print(data)

 

b) 제출결과 

 

c) 왜 그럴까?

- pypy3로 제출한 경우 맞았다고 나오지만, python3로 제출했더니 틀렸다고 나온다. 

- 아마도, 메모리 효율성의 측면에서 차이점이 있기 때문일 것이다, 

- python은 더 적은 메모리를 사용한다. 반면에 pypy의 경우, 더 많은 메모리를 사용한다. 

- 더 자세한 차이점에 대해서 알고 싶다면 아래의 링크를 참고하자. 

 

https://ralp0217.tistory.com/entry/Python3-%EC%99%80-PyPy3-%EC%B0%A8%EC%9D%B4

Python3 와 PyPy3 차이

 

https://imksh.com/46

몸소 겪었던 Python과 PyPy의 차이(메모리,속도)

---

4. 해설 및 정답코드 

- N이 최대 1,000,000까지의 범위를 갖고 있다. 

- 그러므로 시간복잡도 O( N log N)의 정렬 알고리즘을 사용해야 한다. 

- 고급 정렬 알고리즘(병합, 퀵, 힙 정렬 등)을 이용하여 해결할 수 있다. 

- 여기서는 병합 정렬을 이용하여 문제를 풀어볼 것이다. 

 

병합 정렬 알고르즘으로 배열을 정렬하는 과정 

 

def merge_sort(array):
  if len(array) <= 1:
    return array
  mid = len(array) // 2 # 배열의 중간 index를 찾는다
  left = merge_sort(array[:mid]) #중간 index를 기점으로 좌우측을 나눈다
  right = merge_sort(array[mid:]) # 재귀함수를 사용하는 이유는 완벽하게 정렬될 때까지 계속 정렬되도록 하기 위함이다. 

  i, j, k = 0, 0, 0 # i는 좌측, j는 우측 배열의 index 값을 의미한다. k는 완성될 배열의 index 값이다.  

  while i < len(left) and j < len(right): 
    if left[i] < right[j]: # 좌우측 배열의 값을 비교한다. 
      array[k] = left[i]  # 비교했을 때, 더 작은 값이 array에 삽입된다. 
      i += 1 # 좌측 배열의 값이 더 작아서 array에 삽입됐다면, 다음 좌측 원소과 우측 원소의 값을 비교한다. 

    else: # 우측 배열의 값이 더 작은 경우, 
      array[k] = right[j] # 우측 배열의 값이 array에 삽입된다.  
      j += 1 # 다음 우측 원소의 값과 좌측 배열의 원소 값을 비교하기 위해 index값을 증가한다. 
    k += 1 # 위의 if 또는 else 문을 거쳤다면, array[k]에는 원소가 삽입되기에 다음 자리로 이동하기 위해 index 값을 증가한다. 

  if i == len(left): # 좌측 배열에 더이상 비교할 원소가 없는 경우 
    while j < len(right): 
      array[k] = right[j]
      j += 1
      k += 1
  elif j == len(right):
    while i < len(left):
      array[k] = left[i]
      i += 1
      k += 1
  return array 

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

for _ in range(n):
  array.append(int(input()))

array = merge_sort(array)

for data in array:
  print(data)