【경쟁 프로 전형적인 90문】002의 해설(python)

개요

경쟁 프로 전형 90문 의 해설 기사입니다.
해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다.

※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다.
※★5이상의 문제는 난이도적으로 후회하고 있기 때문에, 투고 시기가 늦어질 가능성이 있습니다. (대신 정중하게 해설 해 주시는 분이라면 꼭 부탁드립니다)

문제 002-Encyclopedia of Parentheses

문제 개요

길이 N의 "올바른"괄호 열을 사전 순서로 출력합니다.
옳다는 것은
- () 쌍이 갖추어져 있습니다.
- 오른쪽에서 봤을 때 "("보다")"쪽이 많아서는 안된다.
- () 이외의 문자열을 포함해서는 안됩니다.

제약

1 <= N <= 20 \\
Nは整数

해결 방법

N이 작고, 문자열의 단순함으로부터, 궁리해 전체 탐색에서 요구될 것 같다.
일단 같은 것을 포함한 정렬로 전체 패턴 열거하는 것도 생각했지만, 패턴이 최대로 $20!$이 되어 버리기 때문에,
신도 그래. (엄밀하게는, $20!/(10!*10!)$)

그래서 이번에는
1. "("을 1, ")"을 0으로 간주하여 비트 전체 검색
2. 1로 나온 문자열에 "("보다 먼저 ")"가 많이 출현하지 않는지 확인
같은 흐름으로 구현한다.

1에 관해서, 0이나 1의 2가지 × N문자이므로, $O(2^N)$의 계산량.
(비트 전 탐색에 대해서는 여기 )

2에 관해서, N문자를 왼쪽으로부터 검색하는 것만이므로, $O(N)$.

2 ^ N 패턴에서 N 번 검색을 수행하기 때문에,
합계로 $O(N*2^N)$. 이것은, 10^7의 순서가 되기 때문에, 충분히 시간에 맞는다.



인용 소스 : 경쟁 프로 전형 90문 Github

구현

answer.py

# 入力の受け取り
N = int(input())

# カッコ列を格納する配列
pare = []

# ビット全探索
for i in range(1 << N):

# 1の時 "(" を、0の時 ")" を文字列に追加していく
  l = ""
  for j in range(N):
    if i >> j & 1:
      l += "("
    else:
      l += ")"

# 文字列の長さがNの時のみ、左から検索する。その時cntで"("と")"の出現回数を計算する。cntが0より小さくならなかった＋cntが0(出現回数が等しかった)文字列のみをpareに格納する
  if len(l) == N:
    cnt = 0
    flag = True
    for k in range(N):
      if l[k] == "(":
        cnt += 1
      else:
        cnt -= 1
      if cnt < 0:
        flag = False
    if flag and cnt == 0:
      pare.append(l)

# pareを辞書順にソート、順番に出力する
pare.sort()

for i in range(len(pare)):
  print(pare[i])

※ 참고로 위의 코드는 Python으로 제출하면 TLE가 되고 pypy라면 AC가 됩니다.
부드럽게 긴 배열이나 재기 함수를 사용하는 경우를 제외하고는 pypy가 기본적으로 빠르기 때문에 제출은 pypy를 추천합니다.
참고 기사

마지막으로

문제의 해설을 읽어도 다른 사람의 코드를 봐도 확실히 모르는 분
힘에 조금이라도 될 수 있으면 다행입니다.
코드의 개선점이나 그 외, 의견등 있으면, 부담없이 코멘트해 주세요.

여기까지 읽어 주셔서 감사합니다.