1.문제 설명

Have the function BracketCombinations(num) read num which will be an integer greater than or equal to zero, and return the number of valid combinations that can be formed with num pairs of parentheses. For example, if the input is 3, then the possible combinations of 3 pairs of parenthesis, namely: ()()(), are ()()(), ()(()), (())(), ((())), and (()()). There are 5 total combinations when the input is 3, so your program should return 5.

에.. 그러니까, 브라켓의 세트 개수를 인풋으로 줄테니, 그만큼의 브라켓 세트를 갖고 몇 가지의 조합이 나오는지 도출해라. 이거죠! 유남셍?!

<제한 사항>

There Is No Je Han Sa Hang

....코드바이트 친구들이 너그러운 것인지. 아니면 불친절한지 모르겠지만, 별도의 제한 사항을 주지 않았답니다. 무슨짓이든 해서 통과하라는 걸까요,..?

입출력 예

input(2) -> outPut(2)
input(3) -> outPut(5)

입출력 예 설명

For example, if the input is 3, then the possible combinations of 3 pairs of parenthesis, namely: ()()(), are ()()(), ()(()), (())(), ((())), and (()()). There are 5 total combinations when the input is 3, so your program should return 5.

2.풀이과정

급작스럽게 코드바이트에서 한 문제를 풀어보고 싶어졌답니다. 특정 기업에서, 이 사이트를 통해 코딩테스트를 진행한다는 이야기를 들었기 때문이에요.

해당 문제는 나름 Hard 난이도에 속하는 문제였어요.
저는 braket 문제는 다 stack을 통해 풀면 된다 생각했는데, 이 문제는 그에 더해서 완전탐색을 요구하는 느낌이 들었답니다!

제 전략으로 접근한 결과물은 다음과 같았어요

import copy

def search(op, cl, arr):
  global count

  if op == 0 and cl == 0 and len(arr) == 0:
    count += 1
    return
  tmp = copy.deepcopy(arr)
  if op > 0:
    tmp.append("(")
    search(op - 1, cl, tmp)
  tmp = copy.deepcopy(arr)
  if cl > 0:
    if not arr:
      return
    if arr[-1] == "(":
      tmp.pop()
      search(op, cl - 1, tmp)
    else:
      return

def BracketCombinations(num):

  opening = num
  closing = num
  global count

  arr = []
  count = 0
  # code goes here
  
  search(opening, closing, arr)

  return count

# keep this function call here 
print(BracketCombinations(input()))

효율성은 그냥.. 집으로 돌려보낸 코드같이 되어버려서, 정답을 맞히고도 마음에 썩 들지는 않았답니다.

완전탐색의 효과를 가지면서도, 좀 더 효율적이고 빠른 로직과 인사이트를 얻기위해 시간투자를 더 해보고 싶어요.