[백준BOJ] 단계별로 문제풀기 - 정렬 정답 및 후기(파이썬, python)

백준 알고리즘에서 제공되는 문제들 중 단계별로 문제 풀기 - 정렬을 파이썬으로 풀어보았다. 코드는 9문제 통째로 깃허브에 올려놓았으며 각 문제마다 주석으로 표시해놨다.

 

www.acmicpc.net/step/9

정렬 단계

원본 코드는 깃허브에!

github.com/tomy9729/Algorithm/blob/master/BaekJoon/Step-by-step%20troubleshooting(%EB%8B%A8%EA%B3%84%EB%B3%84%EB%A1%9C%20%EB%AC%B8%EC%A0%9C%ED%92%80%EA%B8%B0)/12.%20%EC%A0%95%EB%A0%AC

tomy9729/Algorithm

 

0. 전체 후기

정렬이란 원소들을 어떠한 규칙에 따라 열거하는 알고리즘이다. 정렬은 어떠한 규칙에 대해서 얼마나 효율적인 아이디어로 구현할 것인가가 중요한 것 같다. 예전에 c언어로 버블 정렬, 합병 정렬, 퀵 정렬 등을 직접 구현해본 적이 있는데 이러한 정렬들의 가장 큰 차이는 얼마나 빨리 정렬하느냐이다. 파이썬에서는 배열에 sort() 함수가 내장되어 있는데 이 함숙가 퀵 정렬을 사용하기 때문에 매우 편리했다. 아마 c언어 등 다른 언어로 풀었다면 퀵 정렬을 직접 구현하여 풀지 않았을까 싶다. 

 

1. 2750번 수 정렬하기

n개의 숫자를 입력받고 오름차순으로 정렬하면 된다. 앞서 말했듯이 sort함수로 쉽게 문제를 해결할 수 있다.

#2750번 수 정렬하기
n = int(input())
arr = []

for i in range(n) : 
  arr.append(int(input()))

arr.sort()

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

 

2. 2751번 수 정렬하기 2

문제 구성은 위 문제와 같지만 차이점이 하나 있다. 더 짧은 시간에 문제를 해결해야 한다. 살짝 기대하는 마음으로 위 문제에서 해결한 코드를 복사해서 제출해봤지만 역시나 시간 초과를 했다. 처음에는 더 빠른 정렬 방법을 사용해야하나 싶었다. 이 과정에서 sort함수가 퀵정렬이라는 것을 알았다. '퀵정렬보다 빠르게 수행하기 위해서 기수정렬을 사용하라는 건가?'하고 기수정렬로 풀까하다가 그보다 간단하게 문제를 해결할 수 있었다. 두가지 방법이 있다. 첫 번째 방법은 Pypy3로 제출하는 것이다. Pypy3는 python3보다 속도가 빠르기 때문에 수 정렬하기2에서 시간초과를 회피할 수 있다. 하지만 이 방법은 영 찜찜한 방법이다. 두 번째로 숫자를 입력할 때 input()대신 sys.stdin.readline()를 사용하는 것이다. input()의 경우 사용자의 입력을 받기 위해 prompt를 띄우고, 입력을 받고, 문자열로 변환하고 등의 과정을 거친다. 그에 비해 sys.stdin.readline()은 버퍼를 통해 사용자의 입력을 받고 읽는다. 즉 입력하는 횟수가 많으면 많을 수록 input()을 사용하는 경우와 sys.stdin.readline()을 사용하는 경우의 시간 차이는 크게 벌어진다. input()대신 sys.stdin.readline()을 사용함으로써 시간초과를 회피할 수 있다. 

#2751번 수 정렬하기2
import sys
n = int(sys.stdin.readline())
arr = []

for i in range(n) : 
  arr.append(int(sys.stdin.readline()))

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

 

3. 10989번 수 정렬하기 3

3번 문제 역시 위 두 문제와 매우 비슷하다. 다른 점이 있다면 이번에는 메모리 제한이 8MB로 낮다. 참고로 1번 문제에서 사용한 메모리는 28MB, 2번 문제에서 사용한 메모리는 71MB이다. 가장 먼저 든 생각은 카운팅 정렬이었다. 단 카운팅 정렬만 사용한다고 해서 문제가 해결되지는 않았다. 처음 카운팅 정렬을 구현할 때는 입력하는 숫자들의 배열, 카운트 배열, 정렬이 완료된 배열 총 세 개를 사용했는데 배열을 세 개나 사용해서 메모리 초과가 발생하는 듯하여 배열 사용을 최소화하는 것을 목표로 했다. 그래서 나온 코드가 아래 코드이다. 코드를 보면 카운트 배열만 존재한다. 문제 정답 기준은 정렬된 배열의 유무가 아닌 배열의 출력물이다. 때문에 정렬이 완료된 배열을 따로 저장하지 않고 카운트에 저장된 수만큼 해당 index를 출력하는 방법으로 문제를 해결했다. 실제로도 이 코드가 출제자가 의도한 정답인지는 확실히 모르겠다. 추가로 숫자를 입력받을 때 input대신 sys.stdin.readline을 쓰면 메모리를 덜 쓸 수 있다.

#10989번 수 정렬하기3
import sys
input = sys.stdin.readline
n = int(input())
count = [0]*10001

for i in range(n) : 
  count[int(input())] += 1

for i in range(10001) : 
  for j in range(count[i]) : 
    print(i)

 

4. 2108번 통계학

항상 문제를 잘 읽어야 한다. 산술평균, 중앙값, 최빈값, 범위 총 4개를 출력해야 하는데 최빈값의 조건이 조금 특이하다. 최빈값이 두 개 이상인 경우 두 번째로 큰 최빈값을 출력해야 한다. 또한 입력되는 정수는 4000을 넘지 않는 절댓값이다. 3번 문제와 마찬가지로 카운팅 정렬로 접근했으며 index를 활용하려고 했다. 입력되는 정수의 범위는 -4000~4000이기 때문에 배열의 크기를 8000으로 설정하여 -4000~4000이 0~8000에 대응되도록 숫자의 빈도수를 저장했다. 산술평균, 중앙값, 범위는 계산식에 맞게 출력하면 쉽게 해결할 수 있다. 문제는 최빈값을 출력하는 것인데 최빈값이 두 개 이상이면 두 번째로 큰 최빈값을 출력하는 것 때문에 조금 시간이 걸렸다. 먼저 최빈값이 두 개 이상인지 확인하고 두 개 이상이면 두 번째 최빈값을 출력하고 아닌 경우 첫 번째 최빈값을 출력하도록 했다. 이 때문에 코드가 쓸데없이 길어진 느낌이다. 문제를 풀고 나서 다른 사람들의 코드를 봤는데 최빈값만 따로 배열을 만들어 배열의 크기에 따라 최빈값을 출력하는 코드가 가장 깔끔해 보였다.

#2108번 통계학
import sys
input = sys.stdin.readline
n = int(input())
arr = []
count = [0]*8001 #음수도 나오기 때문에 음수의 크기를 고려하여 배열 크기 선정
count_max = 0

for i in range(n) : 
  temp = int(input())
  arr.append(temp)
  count[temp+4000] += 1

arr.sort()
print(round(sum(arr)/n))
print(arr[n//2])

for i in range(8001) : #최빈값이 여러개 나오는 경우를 확인하기 위함
  if count[i] == max(count) : 
    count_max += 1

if count_max == 1 : #최빈값이 한 개인 경우
  print(count.index(max(count))-4000)
else :              #최빈값이 여러개인 경우
  temp = 0
  for i in range(8001) : 
    if count[i] == max(count) and temp == 1 :
      print(i-4000)
      break
    if count[i] == max(count) : #최빈값 중 두번째로 큰 수를 출력하기 위함
      temp += 1

print((max(arr)-min(arr)))

 

5. 1472번 소트 인사이드

입력받은 숫자를 % 연산자와 //연산자를 통해 배열로 옮기고, 내림차순으로 정렬했다. 그다음 배열들을 공백 없이 쭉 출력했다.

#1472번 소트인사이드
n = int(input())

arr = []
while n :
  arr.append(n%10)
  n = n//10

arr.sort(reverse=True) #내림차순으로 정렬

for i in range(len(arr)) : 
  print(arr[i],end='')

 

6. 11650번 좌표 정렬하기

6번 문제와 7번 문제는 매우 비슷한 문제인데 여기서 파이썬의 사기성이 또 보인다. 파이썬은 sort 혹은 sorted함수에 key라는 파라미터가 있는데 어떤 값을 주느냐에 따라 각 좌표마다 정렬을 쉽게 할 수 있다. 아래 코드에서 "sorted(xy, key = lambda x : (x [0], x [1]))"는 배열 xy를 xy의 첫 번째 값을 기준으로 오름차순 정렬한 다음 두 번째 값을 기준으로 오름차순 정렬을 하라는 의미이다. x [0] 대신 -x [0]를 사용하면 내림차순으로 정렬하라는 의미이다.

 

#11650번 좌표 정렬하기
n = int(input())

xy = [[0]*2 for i in range(n)]

for i in range(n) :
  temp_x, temp_y = input().split()
  xy[i][0] = int(temp_x)
  xy[i][1] = int(temp_y)

result = sorted(xy, key = lambda x : (x[0],x[1]))  

for i in range(n) : 
  print("%d %d"%(result[i][0],result[i][1]))

 

7. 11651번 좌표 정렬하기 2

6번 문제에서 x[0]와 x[1]의 위치만 바꿔주었다. 

#11651번 좌표 정렬하기2
n = int(input())

xy = [[0]*2 for i in range(n)]

for i in range(n) :
  temp_x, temp_y = input().split()
  xy[i][0] = int(temp_x)
  xy[i][1] = int(temp_y)

result = sorted(xy, key = lambda x : (x[1],x[0]))  

for i in range(n) : 
  print("%d %d"%(result[i][0],result[i][1]))

 

8. 1181번 단어 정렬

단어들을 정렬하는데 첫 번째로 단어의 길이순(오름차순), 두 번째로는 길이가 같으면 사전 순으로 정렬해야 한다. 또한 중복되는 단어들은 한 번만 출력한다. 문자열을 대상으로 sort함수를 사용하게 되면 사전 순으로 정렬된다. 먼저 사전순으로 정렬한 다음 key를 통해 길이 순으로 한번 더 정렬하면 두 조건에 맞게 단어들이 정렬된다. 다음으로 단어들을 중복되지 않게 단어들을 출력해야 한다. 이를 위해 새로운 배열을 하나 더 추가하였다. 새로운 배열에 정렬된 단어들을 순서대로 저장하는데 만약 새로운 배열의 마지막 단어와 같은 단어가 들어오면 continue를 통해 스킵되도록 하였다.

#1181번 단어 정렬
n = int(input())

words = []
for i in range(n) : 
  words.append(input())

words.sort()
words.sort(key=lambda x:len(x))
result = []

for i in range(n) : 
  if i == 0 :
    result.append(words[i])
  elif result[len(result)-1] == words[i] : 
    continue
  else : 
    result.append(words[i])

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

 

9. 10814번 나이순 정렬

나이순으로 정렬하되 나이가 같으면 먼저 가입한 사람이 앞으로 오게 정렬해야 한다. 즉 값이 같은 원소끼리는 전후관계가 바뀌지 않도록 정렬해야한다. 먼저 가입한 사람을 특정하기 위해 가입 순서에 따라 숫자를 추가로 입력했다. 코드를 보면 user배열에 나이와 이름 그리고 추가로 index를 저장한다. 다음 sort함수에서 key를 통해 나이와 index기준으로 정렬했다. 문제를 풀 때는 index를 꼭 활용해야 한다고 생각했는데 다른 사람들의 코드를 쭉 훑어보다 보니 중요한 건 index가 아니라 나이와 이름을 묶어주는 거였다. 참고로 index 부분을 빼도 정답이다.

#10814번 나이순정렬
n = int(input())

user = [[0]*3 for i in range(n)]

for i in range(n) : 
  age,name = input().split()
  age = int(age)
  user[i][0] = age
  user[i][1] = name
  user[i][2] = i

user.sort(key=lambda x:(x[0],x[2]))

for i in range(n) : 
  print(user[i][0], end = ' ')
  print(user[i][1])