https://codeforces.com/problemset/problem/1660/C
대회에서는 1시간 가량 고민했지만 풀지 못했다.
문자열이 주어지면 짝수로 짝지어지는 문자열로 만들기 위해 최소 몇개의 문자를 지워야 하는지 구하는 문제이다.
6
aabbdabdccc
zyx
aaababbb
aabbcc
oaoaaaoo
bmefbmuyw
첫 번째 case인 aabbdabdccc
는 aabbddcc
로 만들면 된다. 연속으로 짝수개가 생기게 하면 되는 것이다.
두 번째 case인 zyx
는 다 지우면 된다.
그럼 입력받은 문자열 앞에서부터 확인하며 배열에 그 문자열이 존재하지 않으면 배열에 담는다. 배열에 문자열이 존재하면 그 사이 값을 제거하면 되니까 배열에 있는 다른 문자들은 제거하는 것이다. 그리고 배열은 초기화한다.
위 과정을 예제로 설명해본다.
예제 1번을 보면 문자열이 a a b b d a b d c c c이다. 첫 문자열부터 하나씩 순회하며 구해본다.
[a]
[b]
[d]
[a, d]
[a, b, d]
[c]
[c]
이게 마지막이니 c를 제거해야 한다. (총 3개 제거)위 같은 방법으로 총 3개를 제거해야 함을 알 수 있다.
t = int(input())
for _ in range(t):
string = input()
visited = []
cnt = 0
for i in string:
if i in visited:
cnt += len(visited) - 1
visited = []
else:
visited.append(i)
print(cnt + len(visited))