Baekjoon - 정렬

2752. 수 정렬

 

N개의 수가 주어졌을 때, 오름차순으로 정렬하는 문제이다. (단, 수는 중복 X) 

 

Solution

중복되지 않은 수들만 존재하므로 Set 자료구조를 이용하는 것부터 생각을 출발하였다. 그러나 중복은 기본 옵션이므로 List로 진행하였다. 

 

그래서, Sorted() function 을 사용하여 진행하였다.

Sorted(정렬할 데이터 : iterable, key parameter (어떤 것을 기준으로 : Default : key), reverse parameter (오름차순 : Defalut -> False, 내림차순 : True))

Sort() : 본체 리스트를 정렬 후 반환.
Sorted() : 본체 리스트에서 정렬한 새로운 리스트 반환.

 

N = int(input())

N_set = set() # set은 중복을 허용하지 않음

for i in range(N + 1):
    n = int(input())
    N_set.add(n)
    
# set을 정렬시키기 위해 리스트로 변환 후 정렬
set_to_list = sorted(N_set, reverse=True)

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

 

2587. 대표값2

평균과 중앙값을 구하는 문제이다.

Solution

평균과 중앙값은 Numpy module에서 mean, median을 사용하면 되지만 백준에서는 사용이 불가능하여 정렬 후 check 한다.

num_list = [int(input()) for i in range(5)]

print(int(sum(num_list) / 5))
new_list = sorted(num_list)
print(new_list[2])

 

25305. 커트라인

 

N명 중 k명까지만 상을 받고, 커트라인의 점수를 출력하는 문제이다.

 

Solution

정렬 후에 인덱스 (K)를 통해 점수를 출력한다.

N, k = map(int, input().split())

N_list = list(map(int, input().split()))

new_list = sorted(N_list, reverse=True)

print(new_list[k - 1])

 

2751. 수 정렬하기 2

 

N개의 수가 주어졌을 때, 오름차순 정렬 (수는 중복되지 않게 주어진다).

 

Solution

input()으로 데이터를 입력받으려고 하면 시간 초과가 발생한다.

=> 반복문으로 여러 줄 입력받는 상황에서는 반드시 sys.stdin.readline (한 줄 단위로 입력을 받아 개행 문자를 같이 입력함) 사용한다. 

 

import sys
input = sys.stdin.readline # 반복문으로 여러 줄 입력받는 상황에서는 input() 사용하면 시간 초과

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

for i in range(N):
    N_list.append(int(input()))
    
print(*sorted(N_list), sep='\n')

 

10989. 수 정렬하기 3

 

수 정렬하기 2와 같은 문제이지만, 더욱 빠르게 효율을 낼 수 있도록 하는 문제이다.

Solution

1. 메모리 제한으로 인해 sort 사용 불가.

=> 10,000 보다 작은 자연수라고 하였으므로 10,001 의 배열 선언

2. sys.stdin.readline 사용.

3. append 사용 x

=> 계수정렬 사용!

계수정렬
- 데이터의 크기가 한정되었을 때 사용한다.
- count할 배열을 선언하고, 정렬할 배열 요소가 몇 개 있는지 카운트 배열 각 index를 암기한다.

 

그래서, 배열과 요소의 갯수를 셀 배열을 선언한다.

cnt = [0] * (max(arr) + 1)

 

0 이 아닌 데이터 => 입력 받은 데이터를 확인한다 -> 출력!

 

import sys
input = sys.stdin.readline 

N = int(input())

arr = [0] * (10000 + 1) # 자연수 10,000까지 주어지니 10,001 까지 배열 선언

for i in range(N):
    arr[int(input())] += 1 # 각 입력값에 해당하는 index value 증가

# arr에 기록된 정보 check
for i in range(len(arr)):
    if arr[i] != 0: # 입력받은 데이터들을 출력
        for j in range(arr[i]):
            print(i)

 

1427. 소트인사이드

 

수가 주어지면, 각 자리수를 내림차순 정렬,,

ex) 2143 (input) -> 4321 (output)

 

Solution

List를 str 형식으로 받아서 정렬,,

arr = list(map(int, str(input())))

arr.sort(reverse=True)

for i in arr:
    print(i, end='')

 

11650. 좌표 정렬

 

2차원 평면 위에 점이 N개 존재한다. (좌표는 항상 정수이고, 위치가 같은 두 점은 x)

 

Solution

2차원 배열을 선언하고, 정렬 후 출력한다.

 

n = int(input()) # 총 점의 개수
arr = []

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

arr.sort()
for i in arr:
    print(i[0], i[1])

 

11651. 좌표 정렬하기 2

y를 기준으로 하는데, 같으면 x를 기준으로 진행하는 좌표 정렬하기 문제이다.

Solution

Lambda function 을 사용하여 해결한다.

lambda
- 형식 : lambda 인자 : 표현식

람다 함수를 통해 정렬 기준을 지정한다.

sort(key = lambda x : (x[1], x[0])); # x[0] : x변수, x[1] : y변수
# y기준이 아니면 x기준으로 만들었다.

 

n = int(input())

arr = []

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

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

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

 

1181. 단어 정렬

 

우선순위 정렬을 진행한다.

1. 길이가 짧은 것부터 우선순위

2. 길이가 같으면 사전 순으로 우선순위.

( 단, 중복된 단어는 하나만 남기고 제거 )

 

Solution

lambda x : (len(x), x); # 길이가 짧은 것부터, 아니면 사전순,,

 

import sys
input = sys.stdin.readline

n = int(input()) # 단어의 개수

arr = []

for i in range(n):
    arr.append(input().strip())
        
arr = list(set(arr)) # 중복 제거

arr.sort(key = lambda x : (len(x), x))

for i in arr:
    print(i, sep='\n')

 

10814. 나이순 정렬

 

온라인 저지 회원의 수 : n

회원의 나이 이름을 입력으로 넣는데, 결국 나이가 증가하는 순, 같으면 먼저 가입한 순으로 출력한다.

 

Solution

2차원 배열(회원 나이, 이름) 을 선언하려고 했지만, 가입한 순서를 .index() 로 받기에는 정렬할 때마다 달라진다.

그래서, list를 사용한다 (회원의 나이, 이름, 가입 순서)

 

import sys
input = sys.stdin.readline

n = int(input()) # 온라인 저지 회원의 수

arr = []

for i in range(n):
    [age, name] = input().split()
    arr.append([int(age), name, i]) # 나이, 이름 배열
    
arr.sort(key = lambda x : (x[0], x[2])) # 나이가 증가하는 순인데, 같으면 먼저 가입한 순서

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

 

18870. 좌표 압축

 

Xi를 좌표 압축하면 Xi > Xj 를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

 

Solution

좌표 압축 : 흩뿌려진 좌표들을 연속된 수들로 모아 압축하는 것,,

ex ) [1, 10, 10000, 1000000] -> 좌표를 압축하고 순서대로 표현하면 [0, 1, 2, 3],,

그래서, 

1. 같은 수는 좌표값이 같으므로 Set(집합) 으로 중복값을 제거한다.

2. 정렬 후 각 숫자들과 index를 dictionary 저장,,

Enumerate
- 순서가 있는 자료형 (list, set, tuple, dictionary, String) 을 입력으로 받았을 때, index + value return,,
- for문과 함께 자주 사용
- index와 value를 동시에 접근하면서 loop를 돌리고 싶을 때 사용한다,,

 

So, dictionary의 key : value에 대입한다,,

import sys
input = sys.stdin.readline

n = int(input())  # 좌표의 개수

numbers = list(map(int, input().split()))

unique_numbers = sorted(set(numbers))  # 중복 제거 후 정렬

print(unique_numbers)

# 각 숫자의 압축된 좌표를 딕셔너리에 저장
numDict = {num: i for i, num in enumerate(unique_numbers)}

print(numDict)

# 입력된 numbers 리스트의 순서를 그대로 유지하며 압축 좌표 출력
for i in numbers:
    print(numDict[i], end=" ")