괄호열이 나타내는 숫자를 출력하는 문제이다.
조건은 아래와 같다.
한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.
‘()’ 인 괄호열의 값은 2이다.
‘[]’ 인 괄호열의 값은 3이다.
‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.
이 문제를 풀기 위해선 잘못된 괄호열의 처리와 점수계산을 해야한다.
잘못된 괄호열은 스택구조를 통해 (가 마지막에 들어있다면 ) 가 들어와야만 하는 식으로 구현하면 된다.
점수계산은 레벨 개념을 사용한다.
레벨은 괄호열 안에 괄호열이 들어갈 수록 높아진다고 가정한다.
높은 레벨의 괄호가 닫히면, 한 단계 낮은 레벨의 점수를 수치에 맞게 더해준다.
글은 쉽게 쓰지만 상당히 어려운 문제이다.
소스
궁금한게 있는데요. 제가 이 문제 3일동안 고민하다가 안되서 인터넷 찾다가 들렸는데요. 이 풀이 방법 이해는 했는데... 이런 생각을 어떻게 하셨죠??? 처음에 이런 생각하는게 쉽지 않을거 같아서요!
답글삭제@노희석 이 문제는 저도 수차례 시행착오를 거쳐서 해결했던것으로 기억합니다.
삭제위와같은 생각도 그런 시행착오중에 깨닫게된 아이디어라고 보시면 될것 같습니다.
그렇군요 ㅋㅋㅋ 대단하시네요 ㅋㅋㅋ 저도 알고리즘 잘해보고 싶은데 혹시 공부 방법을 물어봐도 될까요??
삭제제 방법은 무작정 문제풀이로 시작한거라 도움이 안될것같습니다 ㅎㅎ
삭제다만 알고리즘 교과서 1권 정독, 프로그래밍 문제해결 방법(JM북) 정독, BOJ 문제 꾸준히 풀기, 코드포스 탑코드 등 대회 참가, 고수들의 블로그에서 정보수집 이것들을 반복하시는것이 제가 생각하기에 좋은 공부방법인것 같습니다.