[파이썬][프로그래머스] 올바른 괄호
1. 문제
[level 2] 올바른 괄호 - 12909
성능 요약
메모리: 10.3 MB, 시간: 9.54 ms
구분
코딩테스트 연습 > 연습문제
채점결과
정확성: 69.5
효율성: 30.5
합계: 100.0 / 100.0
문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
- "()()" 또는 "(())()" 는 올바른 괄호입니다.
- ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항
- 문자열 s의 길이 : 100,000 이하의 자연수
- 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
입출력 예
| s | answer |
|---|---|
| "()()" | true |
| "(())()" | true |
| ")()(" | false |
| "(()(" | false |
입출력 예 설명
입출력 예 #1,2,3,4
문제의 예시와 같습니다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
2. 해결방법 시간복잡도
- 단순 코딩 O(N)
3. 문제 해결 및 코드
-
주석을 참고하면서 이해를 돕습니다.
4. 알고리즘 및 해설
- 문제는 해당 괄호의 열림과 닫힘이 올바른 지 계산하는 것이다.
- 그래서 조건을 처음에 괄호가 닫힌 상태로 시작하거나 괄호가 열린 상태로 끝나는 경우 또는 입력값의 길이가 홀수인 경우를 제외한다.
- 이후 반복문을 통해 괄호가 열리면 +1을 해주고, 닫히면 -1을 해주면서 값을 구해준다.
- 만약 괄호가 1번 열리고 2번 닫힌 경우는 말이 안되므로 break을 해서 해당 값이 정상적이지 않은 괄호라는 것을 출력한다.
- 최종적으로 cnt값이 0이면 올바르게 괄호가 성립되므로 True 아니라면 False를 출력한다.