[11단계] 정렬

2750번. 수 정렬하기

 

▼해설보기

버블정렬

N = int(input())

numbers = []

for _ in range(N):
   numbers.append(int(input()))

for i in range(len(numbers)):
   for j in range(len(numbers)) :
      if numbers[i] < numbers[j] :
         numbers[i], numbers[j] = numbers[j],numbers[i]   
for n in numbers :
   print(n)

 

삽입정렬

N = int(input())
nums = []

for _ in range(N) : 
    nums.append(int(input()))

# Insert Sort
for i in range(1, len(nums)) :
    while (i>0) & (nums[i] < nums[i-1]) :
        nums[i], nums[i-1] = nums[i-1], nums[i]
        
        i -= 1
        
for n in nums : 
    print(n)

1. 거품정렬

거품정렬은 두 개의 반복문을 필요로 한다.

외부 반복문에서는 정렬의 범위를 줄여나가며, 내부 반복문에서는 앞뒤 값을 비교해 나아가며 원소의 위치를 조정한다.

 

2. 삽입정렬

거품 정렬과는 달리 정렬이 진행될 수록 범위가 넓어진다.
크게 바라보면 outer루프는 순방향, inner루프는 역방향으로 반복을 진행한다.

---

2751번. 수 정렬하기2

 

 

▼해설보기

import sys

n = int(input())
num = []
for _ in range(n):
    num.append(int(sys.stdin.readline()))

num.sort()

for i in num:
    print(i)

input() 으로 몇 개 받는 건 상관없지만 예제의 최댓값 1,000,000 정도까지 받게 되면 시간이 오래 걸린다.

( 특히 반복문 안에서의 input() )

 

그래서 

import sys

sys.stdin.readline()

사용하여 해결한다.

---

10989번. 수 정렬하기3

 

 

▼해설보기

내가 쓴 답(오답)

import sys

n = int(input())
num = []
for _ in range(n):
    num.append(int(sys.stdin.readline()))

num.sort()

for i in num:
    print(i)

 

정답

import sys

n = int(sys.stdin.readline())
num_list = [0] * 10001

for _ in range(n):
    num_list[int(sys.stdin.readline())] += 1

for i in range(10001):
    if num_list[i] != 0:
        for j in range(num_list[i]):
            print(i)

for문 속에서 append를 사용하게 되면 메모리 재할당이 이루어져서 메모리를 효율적으로 사용못한다.

일반적으로 입력값이 크지않은 경우에는 상관없지만 이렇게 입력값이 극한으로 많이 주어질 때에는 메모리를 좀 더 효율적으로 관리해야한다. 입력값이 극한으로 많이 주어질 때는 메모리를 조금 더 효율적으로 관리하기 위해 sys.stidin.readline()을 사용한다. 입력값이 10000개 까지 주어질 수 있으니 10000개 만큼의 리스트를 만들어 놓는다.

그러나 인덱스는 0부터 세기 때문에 이를 계산하기 편하게 길이가 10001인 리스트를 만든다.
리스트에 각 요소마다 0을 할당해놓고 입력값을 받을 때마다 그 입력값의 인덱스에 +1씩 해준다.

입력을 다 받고나면 0보다 큰 요소를 갖는 인덱스들을 찾아서 그 수만큼 인덱스를 출력해주면 된다.

---

2108번. 통계학

 

▼해설보기

 

---

1427번. 소트인사이드

 

▼해설보기

N = int(input())
A = []
A = list(map(int,str(N)))
A.sort(reverse=True)
for n in A :
   print(n, end="")

---

11650번. 좌표 정렬하기

 

▼해설보기

N=int(input())
arr=[]
for i in range(N):
    a,b = map(int,input().split())
    arr.append((a,b))
arr.sort()
for i in range(N):
    print(arr[i][0],arr[i][1])

---

11651. 좌표 정렬하기2

 

▼해설보기

N = int(input())
nums = []

for i in range(N):
   [a,b]= map(int,input().split())
   arr = [b,a]
   nums.append(arr)

nums = sorted(nums)

for i in range (N) :
   print(nums[i][1],nums[i][0])

 

이 문제에서 주의하여야 할 점은 중복되는 수가 있다면 같은 수를 줘야 하지만 단순히 sort만을 이용하면 중복 순위로 인해 값이 커지게 된다. 
그러므로 set을 이용해 중복값을 없애는 작업이 필요하다.
순위를 어떠한 방식으로 매길지 고민을 하다 딕셔너리를 이용하여 풀이한 방법이 가장 좋다고 판단했다.
딕셔너리의 키 값을 순위로 이용하여 딕셔너리에 0부터 추가하는 for문을 작성하였고 다시 원래의 좌표(nums)를 도는 for문으로 value 값을 입력하면 키 값을 반환하는 딕셔너리의 특성을
이용해 문제를 푼다.

 

---

1181번. 단어정렬

 

 

▼해설보기

import sys

n = int(sys.stdin.readline())
lst = []

for i in range(n):
    lst.append(sys.stdin.readline().strip())
lst = list(set(lst))
lst.sort()
lst.sort(key = len)

for i in lst:
    print(i)

https://inee0727.tistory.com/37

[파이썬] 입력 받기 : input()과 sys.stdin.readline()

---

10814번. 나이순 정렬

 

 

▼해설보기

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

for i in range(n):
    age, name = map(str, input().split())
    age = int(age)
    member_lst.append((age, name))

member_lst.sort(key = lambda x : x[0])	## (age, name)에서 age만 비교

for i in member_lst:
    print(i[0], i[1])

---

18870번. 좌표압축

 

▼해설보기

import sys
input = sys.stdin.readline

n = int(input())
dic = {}

nums = list(map(int, input().split()))
sNums = sorted(set(nums))

for i in range(len(sNums)):
    dic[sNums[i]] = i

for j in nums:
    print(dic[j], end=' ')

sort와 sorted