블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.본 글은 [ 백준 ] 2504번: 괄호의 값을 풀고 작성한 글입니다.
문제
설명
4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.
- 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
- 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
- X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.
예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.
- ‘()’ 인 괄호열의 값은 2이다.
- ‘[]’ 인 괄호열의 값은 3이다.
- ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
- ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
- 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.
예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.
여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.
입력
첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.
출력
첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.
풀이
접근법
결국 못 풀어서 다른 사람의 접근법을 확인했다.
이후에도 접근법을 토대로 혼자 풀이했는데 계속해서 IndexError 를 반환했다.
이전에 베어로보틱스 인턴 라이브 코딩 테스트를 했을 때도 느낀 부분이지만 구현 문제를 풀 때는 무조건 안 되는 경우에 대한 예외 처리를 우선하는 걸 생각해야겠다.
올바르지 않는 경우에 대해 먼저 정리를 하고 문제를 접근했으면 조금 더 쉽게 풀 수 있었을 것 같다.
풀이의 경우 괄호를 열 때는 임시 변수에 곱해주고 괄호를 닫을 때는 곱했던 값을 실제 정답으로 반환할 변수에 더해주면 된다.
이때 유의할 점은 연속해서 괄호가 닫히는 경우 이미 여는 과정에서 곱했기 때문에 실제 정답에 더해주면 안 된다는 것이다.
따라서 이전 괄호가 무엇인지 계속해서 확인하는 조건문도 필요하다.
나의 풀이
접근법을 토대로 문제를 풀면 아래와 같다.
S: str = input()
values: dict[str, int] = {"(": 2, "[": 3}
brackets: dict[str, str] = {")": "(", "]": "["}
temp, answer = 1, 0
stack: list[str] = []
previous_bracket: str = ""
is_validated_brackets: bool = True
for bracket in S:
if not bracket in brackets:
temp *= values[bracket]
stack.append(bracket)
else:
if not stack:
is_validated_brackets = False
break
else:
compare_bracket: str = stack.pop()
target_bracket: str = brackets[bracket]
if compare_bracket != target_bracket:
is_validated_brackets = False
break
else:
if not previous_bracket in brackets:
answer += temp
temp //= values[target_bracket]
previous_bracket = bracket
if stack or not is_validated_brackets:
print(0)
else:
print(answer)Big-O
시간 복잡도의 경우 문자열의 길이 N만큼 반복문을 수행하면 되기 때문에 O(N)이다.
추가적으로 해시 테이블의 경우 어떤 값이 존재하는지, 다시 말해 일치하는 키가 존재하는지 확인하는 시간 복잡도는 O(1)로 상수 시간이기 때문에 별도의 영향을 끼치지 못한다.
