[Baekjoon] 2309. 7人の小人

5749 ワード
バックアップアルゴリズム テキストリンク
📚 質問する
https://www.acmicpc.net/problem/2309
これは二重ポインタの問題です.
9人中7人のジュニアではなく、一定の条件を満たす2人のスパイを探す問題だ.
すべての人の身長の和を求めて、7人の矮人の身長の和100を減らして、スパイの体重の和を探します.
二つの数の和は,きちんと探さなければならない.
ソートのために、sort()の代わりにBubbleソートを試みた.
長さは9しかないので、タイムアウトの心配はありません.
2つの数を配列の両端に配置し、2つの数の和が必要な値に一致すると、スパイを除去し、残りのジュニアを出力します.
2つの数の和がもっと大きい場合は、eを左に移動し、2つの数の和を減らします.
2つの数の和が小さい場合は、sを右に移動し、2つの数の和を増やします.
📒 コード#コード#
arr = [int(input()) for _ in range(9)]

# 오름차순 버블 정렬, 9개 뿐이니 버블정렬을 사용한다.
for i in range(8):
    for j in range(8-i):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]

ssum = 0
for i in range(9):
    ssum += arr[i]

ssum -= 100     # 합에서 100을 빼 스파이 2명 키의 합으로 바꿔준다.
s = 0
e = 8
while s != e:   # 스파이 2명을 찾아야하므로 투포인터를 사용한다.
    if arr[s] + arr[e] == ssum: # 스파이를 찾으면 종료
        del arr[e], arr[s]  # e와 s에 해당하는 스파이 제거
        break
    elif arr[s] + arr[e] > ssum:
        e -= 1
    else:
        s += 1

for i in range(7):  # 스파이를 뺀 일곱난쟁이 출력
    print(arr[i])
🔍 結果
Java|Java演算(代入、算術、増減)
ASP.NET 3層アーキテクチャ基礎詳細操作図文チュートリアル(一)