닫는 괄호가 앞서지 않는 올바른 기록
자바스크립트 코딩테스트 문제로 balance-check 주제를 연습해보세요. 난이도는 easy이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
괄호 기록 문자열 record가 주어질 때, 이 문자열이 올바른 괄호열이면 true, 아니면 false를 반환하는 solution 함수를 작성하세요.
올바른 괄호열이란 다음 두 조건을 모두 만족하는 문자열입니다.
- 여는 괄호
(와 닫는 괄호)의 개수가 같다. - 문자열을 왼쪽부터 읽는 모든 순간에, 닫는 괄호의 개수가 여는 괄호보다 많아지지 않는다.
예를 들어 "(())()"는 올바르지만, ")("와 "(()"는 올바르지 않습니다.
제한사항
record의 길이는 0 이상 100,000 이하입니다.record는(와)로만 이루어집니다.- 빈 문자열은 올바른 괄호열로 봅니다.
- 반환값은 불리언 값입니다.
예시
- 입력:
"(())()"→ 출력:true - 입력:
")("→ 출력:false - 입력:
"(()"→ 출력:false - 입력:
""→ 출력:true
힌트
- 전체 개수만 세면
")("같은 경우를 놓칠 수 있습니다. - 문자열을 왼쪽부터 보면서 현재 열려 있는 괄호 수를 하나의 숫자로 관리해 보세요.
- 어떤 시점에 그 숫자가 음수가 되면 더 볼 필요 없이 실패입니다.
해설
이 문제의 핵심은 현재까지 닫히지 않은 여는 괄호 개수를 추적하는 것입니다.
문자를 왼쪽부터 보면서:
(를 만나면 열려 있는 괄호 수를 1 증가)를 만나면 1 감소
시키면 됩니다.
하지만 마지막에 개수가 0인지 보는 것만으로는 부족합니다.
예를 들어 ")("는 여는 괄호와 닫는 괄호 개수는 같지만, 첫 글자부터 닫는 괄호가 먼저 나와 올바른 괄호열이 아닙니다.
그래서 순회 도중에 열린 괄호 수가 음수가 되는 순간 바로 false를 반환해야 합니다.
풀이 순서는 다음과 같습니다.
balance = 0으로 시작합니다.- 문자열을 왼쪽부터 한 글자씩 확인합니다.
(면balance += 1,)면balance -= 1합니다.- 중간에
balance < 0이 되면 즉시false를 반환합니다. - 끝까지 확인한 뒤
balance === 0이면true, 아니면false를 반환합니다.
이 방식은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
JavaScript
에디터 로딩 중...
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
아직 실행하지 않았습니다.
실행 결과
아직 실행하지 않았습니다.
예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.