정렬 - 예제

예제) 위에서 아래로

문제

• 제한
  • 시간 : 1초
  • 메모리 : 128MB
• 입력
  • 첫째줄에 수열에 속해있는 수의 갯수 N (1<=N<=500)
  • 둘째줄부터 N+1번째 줄까지 N개의 수 입력. (1<=수<=100,000)
• 출력
  • 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다. (동일한 수의 순서는 자유롭게 출력)
• 예시
  • 입력) 3\n5\n27\n12
  • 출력) 27 15 12

해설

기본 정렬을 사용할 수 있는지 물어보는 문제

# 이코테 6-10

# N개의 정수 입력받아 리스트에 저장
array = []
for i in range(n): 
  array.append(int(input()))

# 파이썬 기본 정렬 라이브러리 이용하여 내림차순 정렬 수행
array = sorted(array, reverse=True)

# 결과출력
for i in range :
  print(i, end=' ')

예제) 성적이 낮은 순서로 학생 출력하기

문제

• 제한

  • 시간 : 1초
  • 메모리 : 128MB

• 입력

  • 첫째줄에 학생의 수 N (1<=N<=100,000)
  • 둘째줄부터 N+1번째 줄까지
    학생 이름 나타내는 문자열 A + 학생의 성적 정수
    (1<=len(A), len(B)<=100)

• 출력

  • 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 동일한 학생의 순서는 자유롭게 출력한다.

• 예시

  • 2
    홍길동 95
    이순신 77
  • 이순신 홍길동

해설

시간, 공간복잡도에 따라 알맞은 정렬을 적용할 수 있는가

학생정보 (점수, 이름)으로 묶어두고, 점수 기준 정렬 수행할 수 있는가

시간복잡도
학생의 정보가 최대 100,000개까지 입력되므로
최악의 경우 O(NlogN)을 사용해도된다.
혹은 O(N) 보장하는 계수정렬을 사용해도 공간복잡도도 괜찮다.

코드

# 이코테 6-11

# 입력받기
n = int(input())
array=[]
for i in range(n) :
  input_data = input().split()
  # 이름은 문자열 그대로, 점수는 정수형으로 변환하여 전환
  array.append(input_data[0], int(input_data[1]))

# key를 이용하여 점수를 기준으로 정렬
array = sorted(array, key=lambda student:student[1])

# 정렬이 수행된 결과를 출력
for student in array : 
  print(student[0], end=' ')

예제) 두 배열의 원소 교체

문제

• 제한

  • 시간 : 2초

• 입력

  • 첫째줄에 N, K (1<=N<=100000 , 0<=K<=N)
  • 둘째줄에 배열 A원소 입력 (0<=모든원소<=10,000,000)
  • 셋째줄에 배열 B원소 입력 (0<=모든원소<=10,000,000)

• 출력

  • 최대 K번의 바꿔치기 연산 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값 출력

• 바꿔치기?

  • 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나 골라서 두 원소를 바꾸는 것.

• 예시

  • 입력
    5 3
    1 2 5 4 3
    5 5 6 6 5
  • 출력
    26

해설

문제 요구조건을 맞추기 위해 기본아이디어 떠올릴 수 있는가 + 이걸 시간복잡도 계산해서 통과함을 보증할 수 있는가

기본아이디어
매번 배열 A에서 가장 작은 원소 골라서, 배열 B에서 가장 큰 원소와 교체
다만, A의 가장작은 원소 < B의 가장 큰 원소여야함

처음 든 생각
1. A와 B를 정렬해두고, 그때그때 큰 원소 선택하기
2. set으로 저장해두고, max()를 이용하여 그때그때 큰 원소 출력
-> 기각 : 중복된 데이터가 들어올 수 있어서 set() 사용 불가능

기본 아이디어

###########이코테 6-12############
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort(reverse=True)

# 첫번째 인덱스부터 확인하며, 두 배열의 원솔르 최대 K번 비교
for i in range(k) :
  # A의 원소가 B의 원소보다 작은 경우
  if a[i] < b[i] :
    a[i], b[i] = b[i], a[i] # swap
  # 종료조건 : A의 원소가 B의 원소보다 크거나 같을때
  else : 
    break