Pythonを用いて10972(次のシーケンス)のBaek Junアルゴリズム問題を解く

5334 ワード
バックアップアルゴリズム コーディングテスト パイ テキストリンク

問題の説明


  • 1からNまでの数列があります.
    • すなわち、
  • シーケンスが与えられ、次のシーケンスが辞書順に求められる.

    • 問題を解く

  • C++ではnext置換関数で以下のシーケンスを得ることができるが、Pythonは提供しないため、単独で実現する必要がある.(googlingで知りました…)
  • の原理はこうです.
    例えば、[1,4,3,2]シーケンスがある場合
    後からiインデックスを指定する場合、i-1がiより小さい場合を探します.
    上記の例では、(1,4)の組合せに対応する.
    このときi−1インデックスはx,iインデックスはyとして格納される.
    その後、x値より大きい値を後ろから探し、発見時にxと交換します.
    その後、yインデックスからソートして接続します.
    原理はこうだそうです.私も初めて見たので、慌てて、新しい事実を知ることができて嬉しいです.

    • 問題コード

    n = int(input())
arr = list(map(int,input().split()))
chk = False
for i in range(n-1,0,-1):
  if arr[i-1] < arr[i]: ## 앞에 숫자가 뒤에숫자보다 작을 경우에
    for j in range(n-1,0,-1):
      if arr[j] > arr[i-1]:
        arr[j],arr[i-1] = arr[i-1],arr[j] ## swap바로 하기
        arr = arr[:i]+sorted(arr[i:])
        chk = True
        break
    if chk:
      print(*arr) ## 리스트 앞에 *을 붙일경우 1 2 3 4처럼 출력이 가능
      break
if chk == False:
  print(-1)
    ES 6学習ノート-Moduleの文法
    HTML