[2023 알고리즘 스터디] 2조 박주빈 5주차 - 백준 23882, 10989, 2751, 11650

FOSCAR 알고리즘 스터디 5주차 2조 블로깅

 

 

백준 23882번 : 알고리즘 수업 - 선택 정렬 2

 

https://www.acmicpc.net/problem/23882

23882번: 알고리즘 수업 - 선택 정렬 2

 

# a: 배열 크기 k: k번째 교환
a, k = map(int, input().split())

# 배열 int형으로 저장
num_list = [int(i) for i in input().split()]

num_list_sorted = sorted(num_list)

# 교환 횟수
count = 0

for i in range(a-1, 0, -1):
    idx = num_list.index(max(num_list[:i+1]))
    if idx != i:
        num_list[idx], num_list[i] = num_list[i], num_list[idx]
        count += 1
        if count == k:
            for j in num_list:
                print(j, end=' ')
                
if k > count:
    print(-1)

 

 

백준 10989번 : 수 정렬하기 3

 

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

import sys

# 입력 10,000개보다 작거나 같은 자연수
n = int(sys.stdin.readline())
# idx 값이기 때문에 +1해서 10001개 생성
arr = [0]*10001

for _ in range(n):
    num = int(sys.stdin.readline())
    arr[num] += 1

for i in range(10001):
    if arr[i] != 0:
        for _ in range(arr[i]):
            print(i)

 

 

 이 문제의 핵심은 메모리 크기이다. python 내장 함수인 sort() 함수를 사용해 문제를 풀게 되면 메모리 초과로 인해 답이 틀리게 된다. 이 문제는 계수 정렬을 이용해 풀었다.

 

 

백준 2751번 : 수 정렬하기 2

 

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

import sys

n = int(sys.stdin.readline())

num_list = []
for _ in range(n):
    num_list += [(int(sys.stdin.readline()))]

for i in sorted(num_list):
    print(i)

 

 

 문제 10989번과 비교하자면 메모리가 넉넉하게 주어진 대신 시간 제한이 줄었다는 것이다. 그래서 input() 함수 대신 sys.stdin.readline() 함수를 이용해주었다. input() 함수는 sys.stdin.readline()과 달리 prompt message를 출력하고, 개행 문자를 삭제한 값을 리턴하기 때문에 느리다.

 

 

백준 11650번 : 좌표 정렬하기

 

https://www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

 

# n: 점의 개수
n = int(input())

# x, y 좌표 리스트에 담기
xy_list = []
for _ in range(n):
    a, b = map(int, input().split())
    xy_list += [[a, b]]

# xy_list 오름차순으로 정렬
xy_list.sort()

# 정렬된 xy_list에서 x좌표, y좌표 출력
for xy in xy_list:
    print(xy[0], xy[1])

 

 array가 2차원의 경우, sort() 사용시 첫 번째 키 값이 동일하면 자동으로 그 다음 키 값에 따라 정렬된다.