[BOJ] 1427번: 소트인사이드 (python)

문제 링크 : https://www.acmicpc.net/problem/1427

💡 해결 방법

• priorityQueue를 사용하여 입력받은 수를 음수로 바꿔서 정렬 조건에 넣음
• 우선순위 높은 순(=작은 숫자)으로 정렬되므로 절댓값(입력받은 값)이 큰 음수 먼저 앞으로 정렬되어 내림차순 정렬이 가능해짐
  
  
  

📌 SelectionSort

• 알고리즘

  1. 남은 정렬 부분에서 최솟값(또는 최댓값)을 찾음
  2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap
  3. 남은 정렬 범위 축소
  4. 남은 정렬 없을 때까지 1-3 반복

• 선택 정렬 시간복잡도 : O(n^2)
  
  

🖥️ 코드

• PriorityQueue 사용

import sys

from queue import PriorityQueue

N = sys.stdin.readline().strip()
queue = PriorityQueue()

for i in range(len(N)):
    queue.put((int(N[i])*(-1), N[i]))

for i in range(len(N)):
    print(queue.get()[1], end="")

• 정석

import sys

N = sys.stdin.readline().strip()
queue = []

for i in range(len(N)): #입력 문자열 int 배열로 변환
    queue.append(int(N[i]))

for i in range(len(N)):
    maxIdx = i
    for j in range(i+1, len(N)):
        if queue[maxIdx] < queue[j]:
            maxIdx = j
    if maxIdx != i:
        temp = queue[maxIdx]
        queue[maxIdx] = queue[i]
        queue[i] = temp
        
for i in queue:
    print(i, end="")

✏️ 알고리즘 분류

• 문자열
• 정렬