괄호 채우기
실버 IV의견: 0
알고리즘 대회를 준비 중인 지호는 길이 \(N\)의 괄호 문자열을 발견했다. 문자열은 \(\mathtt{(}\), \(\mathtt{)}\), \(\mathtt{?}\) 세 종류의 문자로 이루어져 있다. \(\mathtt{?}\)는 아직 결정되지 않은 자리로, \(\mathtt{(}\) 또는 \(\mathtt{)}\) 중 하나로 채워야 한다.
올바른 괄호 수열이란 다음 조건을 동등하게 만족하는 수열이다: 모든 접두사에서 \(\mathtt{(}\)의 수가 \(\mathtt{)}\)의 수 이상이고, 전체 \(\mathtt{(}\)의 수와 \(\mathtt{)}\)의 수가 같다.
\(\mathtt{?}\)를 모두 채워 올바른 괄호 수열을 만들 수 있으면 그 결과를 출력하고, 불가능하면 \(-1\)을 출력하여라.
- \(1 \le N \le 100\,000\)
- 문자열은 \(\mathtt{(}\), \(\mathtt{)}\), \(\mathtt{?}\)로만 이루어진다.
한 줄에 문자열이 주어진다. 문자열은 \(\mathtt{(}\), \(\mathtt{)}\), \(\mathtt{?}\)로만 이루어진다.
올바른 괄호 수열이 되도록 \(\mathtt{?}\)를 채운 결과를 출력한다. 가능한 답이 여러 가지이면 아무 것이나 출력한다. 불가능하면 \(-1\)을 출력한다.
(??)
(())
\(?\)를 적절히 채울 수 있는지 확인한다. \(((\) \()\)로 채우면 \((())\ \)가 되어 올바른 괄호 수열이 된다.
????
(())
네 \(?\)를 모두 같은 방향으로 채우면 균형이 맞지 않는다. \((())\)처럼 앞 두 개는 \((,\) 뒤 두 개는 \()\)로 채우면 올바른 수열이 된다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
괄호 채우기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
괄호 채우기