[백준] 8958: OX퀴즈 (Python)

OX퀴즈

• https://www.acmicpc.net/problem/8958

8958번: OX퀴즈

 

문제

"OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수는 3이 된다.

"OOXXOXXOOO"의 점수는 1+2+0+0+1+0+0+1+2+3 = 10점이다.

OX퀴즈의 결과가 주어졌을 때, 점수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 0보다 크고 80보다 작은 문자열이 주어진다. 문자열은 O와 X만으로 이루어져 있다.

 

출력

각 테스트 케이스마다 점수를 출력한다.

 

입출력 예제

입력	출력
5 OOXXOXXOOO OOXXOOXXOO OXOXOXOXOXOXOX OOOOOOOOOO OOOOXOOOOXOOOOX	10 9 7 55 30

 

풀이

현재까지 나타난 연속한 O의 수를 cnt에, 전체 점수를 total에 저장한다.

주어진 문자열을 순회하면서 O가 나타나면 cnt를 증가시키고 cnt를 total에 더한다. X가 나타나면 cnt를 0으로 초기화시킨다.

import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	string = input().rstrip()
	cnt = total = 0
	for i in string:
		if i == 'O':
			cnt += 1
			total += cnt
		else:
			cnt = 0
	print(total)

메모리: 31256 KB / 시간: 44 ms

시간 복잡도: O(n) 

공간 복잡도: O(1)