[BOJ 24552] 백준 24552번 - 올바른 괄호
| 2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 풀이 | ||
|---|---|---|
| A | [BOJ 24542] 튜터-튜티 관계의 수 | |
| C | [BOJ 24544] 카카오뷰 큐레이팅 효용성 분석 | |
| D | [BOJ 24545] Y | |
| G | [BOJ 24548] 도로 정보 | |
| K | [BOJ 24552] 올바른 괄호 | |
| L | [BOJ 24553] 팰린드롬 게임 |
1. 문제
$24552$. 올바른 괄호 (2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2022 Winter) Open Contest K번)
2. 풀이
괄호를 하나 지우고 올바른 괄호열인지 일일이 확인하면 시간초과가 날 수밖에 없으므로 특별한 방법이 필요하다.
)의 개수가 (의 개수보다 많아지는 순간이 생기면 올바르지 않은 괄호열임을 알 수 있다. 따라서, 이 순간을 없애기 위해 이 순간 포함 이전 )이 나타나는 곳에서 )을 하나 없애주어야 한다.
그렇게 하면 그 위치를 포함한 오른쪽 모든 )이 나타나는 곳의 누적합이 $-1$이 되어 올바르지 않은 구간이 해결되기 때문이다.
다섯 번째 및 여섯 번째 표와 같이 빨간색보다 더 오른쪽에서 )을 없애면, 빨간색 구간의 개수가 변경되지 않아서 올바르지 않은 괄호열로 판명이 나버리는 것을 볼 수 있다.
)이 (보다 한 개 더 많은 경우는 이렇게 처리가 가능하다. 그럼 (가 )보다 한 개 더 많은 경우는 어떻게 해야 할까?
이 경우는 문자열 전체를 좌우 방향으로 뒤집어 )가 (보다 한 개 더 많은 경우로 바꿔버린 다음 위 풀이를 그대로 적용하면 된다.
예를 들어 (())(()()와 같은 문자열이 있다면, 좌우 방향으로 뒤집어서 위 예시의 ()())(())로 만들 수 있음을 알 수 있다.
3. 채점 결과
4. 회고
.
댓글남기기