🔍 [브론즈2/파이썬3] 2750 - 수 정렬하기

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

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

225328

129360

88641

58.191%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

5
5
2
3
4
1

예제 출력 1 복사

1
2
3
4
5

 

 

 

---

 

내 코드 (56ms)

n = int(input())

arr = []
for _ in range(n):
    arr.append(int(input()))
    
arr.sort()
for i in range(n):
    print(arr[i])

 

단순한 코드로 작성했더니 오래 걸렸다.

 

정렬 알고리즘을 제대로 활용하는 연습을 해보면 좋을 것 같아서, 퀵 정렬로 코드를 작성해봤다.

n = int(input())

arr = []
for _ in range(n):
    arr.append(int(input()))

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[0]
    tail = arr[1:]

    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

    return quick_sort(left_side)+[pivot]+quick_sort(right_side)

arr = quick_sort(arr)

for i in range(n):
    print(arr[i])

 

-> 근데 return 부분을 잘못 작성해서 에러 발생함.. 퀵 정렬 좀 더 공부한 후에 다시 풀어야지

---

 

다른 사람 코드  - 버블 정렬(88ms)

# 버블 정렬

n = int(input())

arr = []
for _ in range(n):
    arr.append(int(input()))

def bubble(arr):
    for i in range(n):
        for j in range(i+1,n):
            if arr[i]>arr[j]:
                arr[i], arr[j] = arr[j],arr[i]
    return arr

result = bubble(arr)
for i in range(n):
    print(result[i])

 

다른 사람 코드  - 삽입 정렬(76ms)

# 삽입 정렬

n = int(input())

arr = []
for _ in range(n):
    arr.append(int(input()))

def selection(arr):
    for i in range(n):
        idx = i
        for j in range(i+1,n):
            if arr[idx]>arr[j]:
                idx = j
        arr[idx],arr[i]=arr[i],arr[idx]
    return arr

result = selection(arr)

for i in range(n):
    print(result[i])

찾아보니 퀵 정렬, 버블정렬 등 다양한 방법으로 풀 수 있는 것 같다.

---

깨달은 점

https://wikidocs.net/16040

14. List(리스트)(4) - 리스트 원소 추가, 삭제

https://wikidocs.net/233711

5-05. Sort : Quick Sort

https://wikidocs.net/219271

13-05. 퀵 정렬 #1