[백준 알고리즘] 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만으로 이루어져 있다.

출력

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

예제 입력 1

5 OOXXOXXOOO OOXXOOXXOO OXOXOXOXOXOXOX OOOOOOOOOO OOOOXOOOOXOOOOX

예제 출력 1

10 9 7 55 30

 

내가 작성한 코드 (C++ 성공)

#include <iostream>

using namespace std;

int main(){

	int n;
	cin >> n;
	int res[n+1];
	
	string str;
	
	for(int i=0; i<n; i++){
		cin >> str;
		int sum = 0;
		int num[str.size()];
		for(int j=0; j<str.size(); j++){
			if(str.substr(j,1) == "O"){
				num[j]  = 1 + num[j-1];
			} else {
				num[j] = 0;
			}
			sum += num[j];
		}
		cout << sum << "\n";
	}
	
	return 0;
}

 

정리

어떻게 O와 X를 구분해야할까? 라고 생각을 많이했던 문제다.
문제를 보자마자 들었던 생각이 일단 O와 X를 구분해보자 라는 생각이었다.
문자열을 어떻게든 잘라야하는데 하면서 문자열에 대한 검색을 많이 했던 것 같다.
그래서 생각한 방법이 substr 함수를 이용한 방법이었다.
일단 내가 생각한 방법은 이렇다.

1) 문자열을 입력받는다.
2) 문자열에 대한 점수와 문자열의 크기로 배열을 하나 만든다.
3) 문자열의 크기만큼 반복문을 수행한다.
4) 반복문을 통해 입력받은 문자열을 앞에서부터 1칸씩 자른다.
5) 자른 문자를 O인지 X인지 판별하고, O이면 이전의 문자가 O인지 X인지 비교한다.
6) 각 문자에 대한 점수를 배열에 저장하고 배열의 값들을 더해준다.
7) 배열의 합이 점수가 된다.

이런 순서로 생각해서 코드를 작성해보았는데 생각보다 쭉 읽어봤을 때 이해가 되지않아서
예를 들어서 정리해봤다.

1) OOXXOXXOOO 라는 문자열 str 을 입력받는다.
2) 문자열에 대한 점수를 순서에 맞게 문자열 크기의 배열 num[str.size()] 에 저장한다고 하자.
   그리고 반복문을 통해 점수를 더해서 저장할 sum 이라는 변수를 생성한다.
3) 입력받은 문자열을 크기만큼 반복할거다.
    OOXXOXXOOO 의 크기(size) 는 10자리의 문자열이므로 10 이 된다.
    따라서 0부터 10까지 반복하는 반복문을 만들어준다.
    여기서는 str.size() 를 사용하면 크기가 나온다.
4) 반복문을 통해 0부터 문자를 자를 건데 이 때, substr() 를 이용한다.
   str.substr(0,1) == "O" -> 0에서부터 1칸을 자른다. |O|OXXOXXOOO -> O
   str.substr(1,1) == "O" -> 1에서부터 1칸을 자른다. O|O|XXOXXOOO -> O
   str.substr(2,1) == "O" -> 2에서부터 1칸을 자른다. OO|X|XOXXOOO -> X
   이런식으로 9까지 반복한다. 이렇게 각 문자를 잘라준다.
5) 그럼 이제 잘린 문자가 O인지 X인지 판별한다.
   만약 O 라면, 이전의 문자가 O인지 X인지 판별해야한다.
   그 이유는 문제에서 O가 연속으로 2개가 나왔기 때문에 2점이 된다.
   |O|OXXOXXOOO  O|O|XXOXXOOO     OO|X|XOXXOOO   ˙˙˙ ˙˙˙   OOXXOXXOO|O|
   1점                    2점 (O가 연속 2개)     0점 (X는 0점)                             3점 (O가 연속 3개)
6) 각 자리의 문자의 점수를 num[] 배열에 넣어준다.
    num[1]은 1번째 자리의 문자인 'O' 의 점수 1,
    num[2]은 2번째 자리의 문자인 'O' 의 점수 2,
    num[3]은 3번째 자리의 문자인 'X' 의 점수 0,
                               ... ...
    num[10]은 10번째 자리의 문자인 'O' 의 점수 3
7) 배열 num[]의 값들을 전부 더해준다. 배열의 합 = 문자열의 총 점수가 된다.

이렇게 정리해서 적어놓다보니 누군가 이 글을 본다면 꼭 이게 정답인듯 보일 것 같다.
하지만 이 정리는 내가 푼 내용을 정리해놓은 것이기 때문에 참고용으로만 봐주었으면 좋겠다.
설명하기 되게 어려운 문제였구나... 누군가 이 글을 보고 단번에 이해된다고 말해주면 좋겠다ㅎㅎ