[Codeforces] 1660C. Get an Even Strings [Codeforces Round #780 (Div. 3)]
📚 문제
https://codeforces.com/problemset/problem/1660/C
📖 풀이
대회에서는 1시간 가량 고민했지만 풀지 못했다.
문자열이 주어지면 짝수로 짝지어지는 문자열로 만들기 위해 최소 몇개의 문자를 지워야 하는지 구하는 문제이다.
- Input
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를 배열에 담는다.
[a]
- a가 배열에 있으니 다른 문자가 있는지 확인한다. 없으니 제거할 문자는 없고 배열도 초기화 한다.
- b를 배열에 담는다.
[b]
- b가 배열에 있고 다른 문자는 배열에 없으니 배열을 초기화 한다.
- d를 배열에 담는다.
[d]
- a를 배열에 담는다.
[a, d]
- b를 배열에 담는다.
[a, b, d]
- d가 배열에 있으니 a, b를 제거한 후 배열을 초기화 한다. (2개 제거)
- c를 배열에 담는다.
[c]
- c가 배열에 있으니 배열을 초기화 한다.
- 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))
🔍 결과
Author And Source
이 문제에 관하여([Codeforces] 1660C. Get an Even Strings [Codeforces Round #780 (Div. 3)]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/CODEFORCES-1660C.-Get-an-Even-Strings-Codeforces-Round-780-Div.-3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)