백준 1181 [python]

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로
단, 중복된 단어는 하나만 남기고 제거해야 한다.

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다.

sort 함수를 사용하면 쉽게 풀 수 있다.

N = int(input())

setA = set()
listA = list()
for i in range(N) :
    data = input()
    setA.add(data)

for i in setA :
    listA.append([len(i), i])

listA.sort(key= lambda x : (x[0], x[1]))

for x, y in listA :
    print(y)    

1. set 자료구조를 사용해서 중복을 제거한다.
2. set에 저장된 데이터를 list에 담아준다.
   첫 번째 인자로 길이를, 두 번째 인자로 문자열을 갖는 리스트를 저장한다.
3. sort 함수를 사용하여 정렬을 수행한다.
   key와 lambda식을 사용해서 정렬을 수행
   리스트 첫 번째 원소를 기준(길이)으로 정렬을 수행 (x[0])
   길이가 같은 리스트들은 두 번째 원소를 기준(사전순)으로 정렬을 수행한다. (x[1])

결과

하지만 이렇게 풀면 나에게 도움이 되지 않는다고 판단

정렬 알고리즘 카테고리이므로 정렬 자체는 직접 구현해보자 !!!!

알고리즘을 풀기 위한 방법은 다음과 같다.

1. 데이터 입력을 받고, 중복된 데이터를 제거한다.
2. 길이를 기준으로 정렬을 수행한다.
3. 길이가 같은 것끼리 묶어서 정렬을 수행한다.

# 전체 코드
def quick(arr, left, right, option) :

   pl = left
   pr = right
   p = arr[(pl+pr) // 2][option]

   while pl <= pr :
      compl = arr[pl][option]
      compr = arr[pr][option]
      while compl < p :
         pl += 1
         compl = arr[pl][option]
      while p < compr :
         pr -= 1
         compr = arr[pr][option]

      if pl <= pr :
         arr[pl], arr[pr] = arr[pr], arr[pl]
         pl += 1
         pr -= 1
   if left < pr :
      quick(arr, left, pr, option)
   if pl < right :
      quick (arr, pl, right, option)

N = int(input())

setA = set()
arr = list()
for i in range(N) :
   data = input()
   setA.add(data)

for i in setA :
   arr.append([len(i), i])

quick(arr, 0, len(arr) - 1, 0)

s = 0
for i in range(0, len(arr) + 1) :
   if i == len(arr) or arr[i][0] != arr[s][0] :
      quick(arr, s, i - 1, 1)
      s = i

for x, y in arr :
   print(y)

중복 제거

# 중복 제거 코드
for i in range(N) :
   data = input()
   setA.add(data)

for i in setA :
   arr.append([len(i), i])

1. set 자료구조를 활용해서 중복을 제거한다.
2. list 자료구조에 set 자료구조의 원소들을 담는다.

**** set은 순서가 없으므로 list에 담아서 처리했다.

다음과 같이 중복 제거하지 않은 이유

# 시간초과 발생 
# 이처럼 간단한게 담을 수 있지만, 처리 속도가 너무 느리다. 그래서 set에 담았다가 다시 list에 담았다.
for i in range(N) :
   data = input()
   if [len(data), data] not in arr :
      arr.append([len(data), data])

quick 함수

# 퀵정렬 함수 
def quick(arr, left, right, option) :

   pl = left
   pr = right
   p = arr[(pl+pr) // 2][option]

   while pl <= pr :
      compl = arr[pl][option]
      compr = arr[pr][option]
      while compl < p :
         pl += 1
         compl = arr[pl][option]
      while p < compr :
         pr -= 1
         compr = arr[pr][option]

      if pl <= pr :
         arr[pl], arr[pr] = arr[pr], arr[pl]
         pl += 1
         pr -= 1
   if left < pr :
      quick(arr, left, pr, option)
   if pl < right :
      quick (arr, pl, right, option)

이 함수는 퀵정렬을 수행하는 함수이다.
단, 기존 퀵정렬과 다른 점은 option이라는 매개변수를 추가하여, 정렬 기준을 설정

quick 함수 매개변수

arr - 정렬을 수행할 배열
left - 정렬을 수행할 시작 인덱스
right - 정렬을 수행할 마지막 인덱스 + 1
option - 정렬의 기준을 설정 // 첫 번째 원소로 정렬을 할 것인지, 두 번째 원소로 정렬을 할 것인지 결정

길이를 기준으로 정렬

quick(arr, 0, len(arr) - 1, 0)

첫 번째 정렬의 경우 전체를 대상으로 해야하므로 0 ~ len(arr) - 1 범위에 대하여 정렬
우선 첫 번째 원소(길이) 를 기준으로 정렬 수행

길이가 같은 경우 사전순으로 정렬

s = 0
for i in range(0, len(arr) + 1) :
   if i == len(arr) or arr[i][0] != arr[s][0] :
      quick(arr, s, i - 1, 1)
      s = i

첫 번째 정렬 수행 후, 길이가 같다면 사전순으로 정렬해야 한다.
이 때, 각 원소의 길이가 같을 수도 다를 수도 있으므로 길이가 같은 것끼리 묶어서 정렬을 수행해야 한다.
반복문에서 i를 증가해가면서, s번째 원소와 길이가 같은지 체크하고, 같지 않다면 리스트를 잘라서 사전순으로 정렬을 수행하도록 했다.

결과