반응형
괄호의 점수
- (,)의 두개의 문자로만 구성된 올바른 괄호문자열이 입력으로 주어진다. (짝이 안맞는 경우는 없음)
- “()” 은 1점
- '('과 ')' 사이에 n점짜리 문자열이 있다면 (2*n)점으로 계산
- 둘 이상의 괄호가 나란히 있다면 두 괄호의 점수를 합침
- ex. "(()(()()))" 는 10점
풀이
def getParenthesisScore(st):
Fragments = []
# ')'과 '('이 만나는 지점을 기준으로 나눠 각각을 'Fragment'라 부름
# Fragments는 이들 Fragment들이 담기는 공간
# 예를 들어 ()()(())는 () / () / (())로 나누어져 Fragments에 저장된다.
Fragment = ""
# Fragment가 저장될 공간. () or (()) or ((())) or ...
# Fragments에 현재 축적된 정보(Fragment)를 저장하고 Fragment 리스트는 초기화함.
n = 0
# '('가 나오면 +1
# ')'가 나오면 -1할 변수이다.
# ')'가 나와 -1했는데 0이 되었다는 것은 괄호가 닫혔다는 뜻
for c in st:
if c == '(':
n += 1
Fragment += c
elif c == ')':
n -= 1
Fragment += c
if (n == 0):
# 0이 되어었다는 뜻은 괄호가 닫혔다는 뜻이므로 현재 Fragment를 Fragments에 담고,
Fragments.append(Fragment)
# 다음 Fragment를 담을 수 있도록 Fragment를 초기화한다.
Fragment = ""
score = 0
# 현재 정보 스코어화
# Fragments를 돌면서 각각의 점수를 체크할 것
for Fragment in Fragments:
# 기본 형태인 '()'는 무조건 1점
if Fragment == "()":
score += 1
# 나머지는 *2, 단 그 내부에는 어떤 형태가 있을지 모르므로 재귀를 활용한다.
# 괄호 한 껍데기만 벗기고 재귀진행
# ex. '(())' 에서 '()'만 새로 재귀진행 단 해당 리턴값에 *2를 해서 score에 더해줌
else:
score += getParenthesisScore(Fragment[1:-1])*2
return score
def main():
examples = ["()()(())", "(()(()))", "((()())())", "()", "((()))()"]
# 4, 6, 10, 1, 5 점이 나와야 합니다.
for example in examples:
print(example, getParenthesisScore(example))
if __name__ == "__main__":
main()
- 재귀로 풀어야한다는 직감은 들었다. 괄호 속 괄호가 몇개나 존재할지 알 수없기 때문이다.
- ')'과 '('만나는 것을 기준으로 나누고, 이를 나눠서 처리하도록 했다.
- 리턴조건을 "()"로 하고 그렇지 않을 경우 제일 왼쪽과 제일 오른쪽의 '('와 ')'쌍을 제거한뒤 *2하고 재귀문을 돌도록 한다.
- 문제는 해결했지만 코드가 지저분해서 찝찝한 느낌. 아직 재귀에 익숙하지 않은 것 같다.
- 더 좋은 풀이가 있다면 공유 바랍니다.ㅠ
반응형
'💻 CS > 알고리즘 연습' 카테고리의 다른 글
[알고리즘 연습] 멱집합 (0) | 2020.08.07 |
---|---|
[알고리즘 연습] 회의실 배정 (0) | 2020.08.06 |
[알고리즘 연습] 하노이의 탑 (0) | 2020.08.01 |
[알고리즘 연습] 중복되지 않는 수 찾기 (0) | 2020.08.01 |
[알고리즘 연습] 최대 수익 구하기 (0) | 2020.07.29 |