BOJ 정렬

2750 수 정렬하기

시간복잡도가 O(n^2)으로도 풀 수 있는 문제이다.

#수 정렬1
#선택정렬
lst = []
for _ in range(int(input())):
    lst.append(int(input()))

for i in range(len(lst)):
    min_index = i
    for j in range(i+1, len(lst)):
        if lst[j]<lst[min_index]:
            min_index = j
    lst[i], lst[min_index] = lst[min_index], lst[i]
for l in lst:
    print(l)

선택정렬을 이용해 풀었다.

---

2751 수 정렬하기2

시간복잡도가 O(nlogn)으로만 풀 수 있는 문제이다. 정렬문제에서 O(nlogn)가 가장 작은 복잡도라는 것은 수학적으로 증명되었다고 한다.
해당 복잡도를 가지는 정렬로는 병합정렬 퀵정렬 힙정렬이 있다.
파이썬 내장함수를 사용하는 방법도 있다. 그러나 pypy로 해야 시간초과가 안뜨니 주의해야한다.

#표준 정렬 라이브러리 사용
lst = []
for i in range(int(input()):
	lst.append(int(input())
    
for ii in sorted(lst):
	print(ii)

정상제출된다.

#병합정렬
def merge(left, right):
    result = []

    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left[0])
                left = left[1:]

            else:
                result.append(right[0])
                right = right[1:]
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:]
        elif len(right) > 0:
            result.append(right[0])
            right = right[1:]
    return result


def merge_sort(list):
    if len(list) <= 1:
        return list

    mid = len(list) // 2
    leftList = list[:mid]
    rightList = list[mid:]
    leftList = merge_sort(leftList)
    rightList = merge_sort(rightList)
    return merge(leftList, rightList)
lst = []
for _ in range(int(input())):
    lst.append(int(input()))
for i in merge_sort(lst):
    print(i)

코드출처
병합정렬을 사용했으나 시간초과가 뜬다. 다시 살펴봐야한다.

---

10989 수정렬하기3

백준에서 카운팅 정렬을 사용해보라길래 카운팅 정렬을 사용했더니 시간 초과가 뜬다.

#카운팅 정렬
def counting_sort(array):
    index = [0]*(max(array)+1)
    for i in range(len(array)):
        index[array[i]] += 1
    for i in range(len(index)):
        for j in range(index[i]):
            print(i)

lst = []
for _ in range(int(input())):
    lst.append(int(input()))
counting_sort(lst)

---

2108 통계학

nums = []
ind = {}
n = int(input())
for i in range(n):
    num = int(input())
    nums.append(num)
    if num not in ind.keys():
        ind[num] = 1
    else:
        ind[num] += 1
nums.sort()
# 평균
print(round(sum(nums)/n))
# 중앙값
print(nums[n//2])
# 최빈값
max_keys = [k for k in ind if ind[k] == max(ind.values())]
if len(max_keys) > 1:
    print(sorted(max_keys)[1])
else:
    print(max_keys[0])
# 범위
print(nums[-1]-nums[0])

시간초과..!

솔루션 서칭해보니

• collections의 Counter를 사용할 수 있었다.
• sys.stdin.readline() 이용!
• 보기 쉽게 함수화 하는 습관 들여야겠다.

import sys
from collections import Counter

n = int(sys.stdin.readline())
lst = []
for _ in range(n):
    lst.append(int(sys.stdin.readline()))
lst.sort()
def mean(nums):
    return round(sum(nums)/n)
def median(nums):
    return nums[n//2]
def popular(nums):
    counter = Counter(nums)
    mc = counter.most_common(n=2)
    if len(nums) > 1: #케이스가 하나일때 인덱스 오류 방지
        if mc[0][1] == mc[1][1]:
            return mc[1][0]
        else:
            return mc[0][0]
    else:
        return mc[0][0]
def ran(nums):
    return max(nums) - min(nums)
print(mean(lst))
print(median(lst))
print(popular(lst))
print(ran(lst))

if len(nums) > 1: #케이스가 하나일때 인덱스 오류 방지 부분에서 nums의 길이만 고려해도 되는 걸 보면 [6,6,6,6,6,6]같은 같은 요소가 반복되는 테스트 케이스는 없는 듯하다.
참고코드

---

1427 소트인사이드

num = input()
lst = [i for i in num]
lst.sort(reverse=True)
for i in lst:
    print(i, end='')

---

11650 좌표정렬하기

import sys
n = int(sys.stdin.readline())
lst = []
for _ in range(n):
    x, y = map(int, sys.stdin.readline().split())
    lst.append((x, y))
# key 인자에 함수를 넘겨주면 해당 함수의 반환값을 비교하여 순서대로 정렬한다.
lst.sort(key=lambda x : (x[0], x[1]))
for i in lst:
    print(i[0], i[1])

sort의 key를 lamda함수를 이용해서 넘겨주는 것이 포인트

참고

---

11651 좌표정렬하기2

import sys
n = int(sys.stdin.readline())
lst = []
for _ in range(n):
    x, y = map(int, sys.stdin.readline().split())
    lst.append((x, y))
# key 인자에 함수를 넘겨주면 해당 함수의 반환값을 비교하여 순서대로 정렬한다.
lst.sort(key=lambda x : (x[1], x[0]))
for i in lst:
    print(i[0], i[1])

---

1181 단어 정렬

import sys
words = []
for _ in range(int(sys.stdin.readline())):
    words.append(sys.stdin.readline().strip())
words = set(words)
words = list(words)
words.sort()
words.sort(key = lambda x : len(x))
for i in words:
    print(i)

strip 안하면 출력형식이 잘못되었습니다. 오류를 접할 수도 있다.

내가 푼 것과 다른 솔루션을 보니
단어와 단어등장횟수를 같이 저장하고 이를 key로 사용하면 sort를 두번하지않아도 된다.

words_num = int(input())
words_list = []

for _ in range(words_num):
    word = str(input())
    word_count = len(word)
    words_list.append((word, word_count))

#중복 삭제
words_list = list(set(words_list))

#단어 숫자 정렬 > 단어 알파벳 정렬
words_list.sort(key = lambda word: (word[1], word[0]))

for word in words_list:
    print(word[0])

참고

---

10814 나이순 정렬

names = []
import sys
for _ in range(int(sys.stdin.readline())):
    age, name = sys.stdin.readline().strip().split()
    names.append((int(age), name))
names.sort(key= lambda x : x[0])
for i in names:
    print(i[0], i[1])

(int(age)) 받아온 나이값을 int로 안바꿔서 틀렸었다.
string에서 숫자는 맨 앞자리 값으로만 비교하기 때문에 에러가 난다.
사소한 실수라 더 알아내기 힘들었다.