BAEKJOON : 10989, 2108, 11651, 10814, 18870

4139 ワード
コーディングテスト テキストリンク

No. 10989


1. Problem

2. My Solution
  • 入力nのサイズは1000000なので、O(n^2)アルゴリズムを使用すると
    • がタイムアウトする可能性があります.
  • ソートの最大値1000
  • O(n)アルゴリズムを用いたカウントソート
    • import sys

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

count_list = [0 for _ in range(10001)]

for i in range(n):
    num = int(sys.stdin.readline().strip())
    count_list[num] += 1    # count

for i in range(len(count_list)):
    for _ in range(count_list[i]):
        print(i)
    3. Learned
  • 入力の大きさが1億であれば1秒と見なすので,この問題を解決するアルゴリズムの複雑さに注意する,
    • .
  • カウントソートアルゴリズムリファレンスビデオ2

    • No. 2108


    1. Problem


    2. My Solution
  • Python統計ベース統計
    • を使用
    import sys
import statistics 

n = int(sys.stdin.readline().strip())
num_list = []

for _ in range(n):
    num_list.append(int(sys.stdin.readline().strip()))

num_list.sort()

count = statistics.multimode(num_list)

print(round(statistics.mean(num_list)))
print(statistics.median(num_list))

if len(count) == 1:
    print(count[0])
else:
    print(count[1])

print(num_list[-1]-num_list[0])
    3. Others' Solutions
  • カウントソート-4000から4000のリスト宣言に使用する
    • 4. Learned
  • 統計処理は
    • を用いる.
  • マルチモード()関数-高周波数要素
    • を返す

    No. 11651


    1. Problem

    2. My Solution
  • .sort()関数のキーパラメータを用いてステップソート
    • を実現する
  • 初めてx[1]の要素で並べ替え、x[0]の要素で
    • に並べ替えます.
    import sys

test_n = int(sys.stdin.readline().strip())

xy_list = []

for _ in range(test_n):
    xy_list.append(list(map(int,sys.stdin.readline().strip().split())))

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

for i in xy_list:
    print(' '.join(map(str,i)))
    3. Learned
  • .
    • sort()関数を指定するキーパラメータ(ソート基準)

    No. 10814


    1. Problem

    2. My Solution
  • 「エラー」->年齢を文字列として認識し、100は20未満の
    • として処理する
    import sys

test_n = int(sys.stdin.readline().strip())

user_info = []

for _ in range(test_n):
    user_info.append(sys.stdin.readline().strip().split())

user_info.sort(key=lambda x:x[0])

for i in user_info:
    print(' '.join(map(str,i)))
    3. Others' Solutions 
    import sys

test_n = int(sys.stdin.readline().strip())

user_info = []

for _ in range(test_n):
    age, name = sys.stdin.readline().strip().split()
    user_info.append([int(age),name])

user_info.sort(key=lambda x:x[0])

for i in user_info:
    print(' '.join(map(str,i)))
    4. Learned
  • ゆっくりと一つ一つ考えて、間違いなくアルゴリズムを実施しましょう

    • No. 18870


    1. Problem

    2. My Solution
  • はSETデータ型で重複を除去し、その後、その要素の数が何番目に小さいかを指数的に判断する.
  • index()関数の時間複雑度はO(n)->タイムアウト
    • である
    import sys

test_n = int(sys.stdin.readline().strip())

num_list = list(map(int,sys.stdin.readline().strip().split()))
set_list = sorted(list(set(num_list)))
count_list =[]

for i in num_list:
    print(set_list.index(i), end=' ')
    3. Others' Solutions
  • index()関数辞書データ型
    • に使用
  • キー(要素):value(いくつかの項目を表す)
    • import sys

test_n = int(sys.stdin.readline().strip())

num_list = list(map(int,sys.stdin.readline().strip().split()))
set_list = sorted(list(set(num_list)))

dic_list = {set_list[i]:i for i in range(len(set_list))}

for i in num_list:
    print(dic_list[i], end=' ')
    4. Learned
  • ナビゲーションの場合、時間複雑度O(1)のdictデータ型
    • を使用することを推奨する.
    [アルゴリズム]バックアップ-10989(ソート3)/java
    c#属性1(Property)