Part3, Sorting

時間の複雑さ
並べ替えアルゴリズムの平均時間複雑度空間複雑度特性選択並べ替えO(N^2)O(N)の考え方は非常に簡単である.挿入ソートO(N^2)O(N)データが正規に近いときが最も速い.高速ソートO(Nlogn)O(N)は、ほとんどの場合に最適であり、十分に速い.カウントソートO(N+K)(Kはデータの中で最大の正数)O(N+K)(Kはデータの中で最大の正数)データのサイズが限られている場合にのみ利用可能であるが、動作は速い.
 
ソートアルゴリズムの動作の考え方
ソートアルゴリズムコアアイデアソート選択ソート選択ソート「ソート」ソート「選択」ソートされていないデータの中から一番前のデータと位置を選択する方法ソートデータを挿入前から次から次へとソートデータを決定し、「データを挿入」を適切な位置に設定する方法基準データをすばやくソートし、基準より大きいデータと基準より小さいデータを設定するデータ位置カウントを変更する方法特定の値を持つデータカウントをソートする方法
 
Pythonの標準ライブラリに内蔵されているソートライブラリは、最悪の場合の時間的複雑さO(Nlogn)を確保します.
したがって,係数ソートを用いて高速ソートを行う必要がある特別な場合でなければ,Pythonを用いたソートライブラリが最も合理的である.
質問する
Q 23国営水

# 국어 점수가 감소하는 순서로
# 국어 점수가 같으면 영어 점수가 증가하는 순서로
# 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
# 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞에 온다.)

n = int(input())

list_data = []

# list에 tuple 입력하기
for _ in range(n):
    list_data = list(input().split())

result = sorted(list_data, key = lambda x : (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

# 정렬된 학생 정보에서 이름만 출력
for idx in range(len(result)):
    print(result[idx][0])

 
Q 24アンテナ
ちょうど中間値に相当する家にアンテナを取り付けると、アンテナからすべての家までの距離の合計が最小になります.
1 2 3 5 8時
3または5にアンテナを取り付けると、アンテナからすべての家までの距離の合計が最小になります.
ソース

# A.24 안테나
n = int(input())
data = list(map(int, input().split()))
data.sort()

# 중간값(median)을 출력
print(data[(n - 1) // 2])

 
Q 25失敗率
失敗率:ステージに到達しても空になっていないプレイヤー数／ステージに到達したプレイヤー数
ソース

def solution(N, stages):
	answer = []
	length = len(stages)
	
	# 스테이지 번호를 1부터 N까지 증가시키며
	for i in range(1, N + 1):
		# 해당 스테이지에 머물러 있는 사람의 수 계산
		count = stages.coumt(i)
		
		# 실패율 계산
		if length == 0:
			fail = 0
		else:
			fail = count / length
		
		# 리스트에 (스테이지 번호, 실패율) 원소 삽입
		answer.append((i, fail))
		length -= count
		
	# 실패율을 기준으로 각 스테이지를 내림차순 정렬
	answer = sorted(answer, key=lambda t: t[1], reverse=True)

	# 정렬된 스테이지 번호 출력
	answer = [i[0] for i in answer]
	return answer

 
Q 26カードソート
常に最小の2枚のカードを組み合わせたときに最適な年を保証します.
必ず一番小さい2枚のカードを組み合わせなければなりません.
ex)
10 20 40 -> 30 40 -> 70
40 10 20 -> 50 20 -> 70
いずれの場合も、最小のトリガから2つのカードグループを取り出し、それを結合してリストに再挿入するプロセスです.
この場合、最も有効なデータ構造:優先キュー(要素の挿入と削除だけでソート結果が得られます).
優先キューはスタックデータ構造で実装でき、Pythonはheapqライブラリをサポートします.

import heapq

n = int(input())

# 힙(Heap)에 초기 카드 묶음을 모두 삽입
heap = []
for i in range(n):
	data = int(input())
	heapq.heappush(heap, data)
	
result = 0

# 힙(Heap)에 원소가 1개 남을 때까지
while len(heap) != 1:
	# 가장 작은 2개의 카드 묶음 꺼내기
	one = heapq.heappop(heap)
	two = heapq.heappop(heap)
	# 카드 묶음을 합쳐서 다시 삽입
	sum_value = one + two
	result += sum_value
	heapq.heappush(heap, sum_value)

print(result)