5875번: 오타
올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키
www.acmicpc.net
문제
올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키파를 도와 올바른 괄호쌍이 되도록 고쳐 주자.
키파는 괄호를 입력할 때 매우 조심했기 때문에 최대 한 번 오타를 내었다. 올바른 괄호쌍은 다음과 같이 정의된다:
- ()는 올바른 괄호쌍이다.
- A가 올바른 괄호쌍이라면 (A) 또한 올바른 괄호쌍이다.
- A와 B가 올바른 괄호쌍이라면 AB 또한 올바른 괄호쌍이다.
입력
첫째 줄에 키파가 입력한 괄호열이 주어진다. 길이는 1 이상 100,000 이하이다.
출력
첫째 줄에 하나의 문자만 고쳐서 올바른 괄호쌍이 될 수 있는 경우의 수를 출력한다.
코드
str = input()
stack = []
acc = [[0]*2 for _ in range(len(str)+1)]
for i in range(len(str)):
if str[i] == '(':
acc[i+1][0] = acc[i][0] + 1
acc[i+1][1] = acc[i][1]
stack.append(i+1)
else:
acc[i+1][0] = acc[i][0]
acc[i+1][1] = acc[i][1] + 1
if stack:
stack.pop()
else:
print(acc[i+1][1])
exit()
if stack: # '(' 괄호가 더 많음
print(acc[-1][0]-acc[stack[-1]][0]+1)
else:
print(0)
acc배열의 0열에는 i+1번째 위치까지의 '('의 개수, 1열에는 ')'의 개수를 저장한다.
이 문제는 오타가 최대 1번만 등장하므로 3가지로 나눠서 풀 수 있다.
1. '('이 1번 더 등장
'('이 한 번 더 등장하는 경우에는 위와 같이 for문을 다 돌고 나면 stack에 2개의 문자가 남는다. 그렇다면 둘 중 더 뒤에 나온 문자, 즉 stack의 top에 있는 위치의 '('부터 시작해서 그보다 뒤에 있는 '(' 중 하나를 ')'로 바꾸면 올바른 괄호쌍으로 바꿀 수 있다. 그러므로 전체 '(' 개수(acc[-1][0])에서 stack[-1] 위치까지의 '(' 개수를 빼고 +1 더해준다. +1 더해주는 것은 stack의 top에 있는 위치까지는 ')'로 바꿀 수 있기 때문이다.
2. ')'이 1번 더 등장
')'이 1번 더 등장하는 경우는 stack에 원소가 없는데 ')'이 등장하는 경우이다. 이 경우에는 ')'이 1번 더 등장한 시점에서부터 앞에 있는 ')' 중 하나를 '('으로 바꿔주면 되기 때문에 이제까지의 ')' 개수인 acc[i+1][1]을 출력해주면 된다.
3. 올바른 괄호쌍
for문을 도는 중간에 종료되지 않고 다 돌았는데 stack도 empty인 경우 올바른 괄호쌍이므로 바꿀 문자가 없다.
'문제풀이 > 자료구조' 카테고리의 다른 글
[Python/파이썬] 백준 18115번 카드 놓기 (0) | 2023.11.28 |
---|---|
[Python/파이썬] 백준 22866번 탑 보기 (0) | 2023.11.21 |
[Python/파이썬] 백준 1655번 가운데를 말해요 (0) | 2023.10.08 |
[Python/파이썬] 백준 21939번 문제 추천 시스템 Version 1 (0) | 2023.09.01 |
[Python/파이썬] 백준 2504번 괄호의 값 (0) | 2023.07.18 |