[백준] 8958번 : OX퀴즈 - [C++]

 

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

8958번: OX퀴즈

 

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

 

이 번 문제도 그리 어렵지는 않을 것이다.

필자가 보기엔 입력받은 문자열을 어떻게 다루느냐를 이해하고자 하는 의도가 아닐까 싶다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

문제를 이해하는 것은 그리 어렵지 않을 것이다.

 

우리는 두 가지 규칙만 따르면 된다.

 

• 각 케이스마다 점수를 출력한다.
• O 의 연속 개수 만큼 점수를 누적하여 합산하고 X가 나오면 누적값은 0으로 초기화 된다.

 

 

 

즉, X혹은, O에 따라 누적값을 표현해주는 변수 하나를 갖고 풀이하면 된다.

 

 

간단하게 위 알고리즘 부분만 코드로 보자면 다음과 같이 접근하면 된다.

 

int OX(string& s) {	
	int cumulative = 0;	// O의 연속 개수(누적 개수)를 의미하는 변수
	int sum = 0;

	// 문자열에 대해 각 문자 단위로 순회
	for(char &v : s) {
		/*
		 * O 문자일 경우 누적합을 1 증가시킨 뒤 
		 * 해당 값에 대해 누적합
		 */
		if(v == 'O') {
			cumulative++;
			sum += cumulative;
		}
		else {
			cumulative = 0;
		}
	}
	return sum;
}

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

이전 포스팅과 여타 다를 바 없이 아래와 같이 2가지 입출력 방법을 통해 성능을 비교해보려한다.

 

 

1. 기본 입출력

2. 향상 시킨 입출력

 

 

 

 

---

• 풀이

- 방법 1 : [기본 입출력]

 

#include <iostream>
#include <string>

using namespace std;

int OX(string& s) {
	
	int cumulative = 0;
	int sum = 0;

	for(char &v : s) {
		/*
		 * O 문자일 경우 누적합을 1 증가시킨 뒤 
		 * 해당 값에 대해 누적합
		 */
		if(v == 'O') {
			cumulative++;
			sum += cumulative;
		}
		else {
			cumulative = 0;
		}
	}
	return sum;
}

int main(int argc, const char * argv[]) {

	int T;
	cin >> T;

	for(int i = 0; i < T; i++) {
		string s;
		cin >> s;

		cout << OX(s) << "\n";
	}

	return 0;
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

참고로 필자는 string 순회에서 for-each 문을 사용하긴 했는데, 만약 이 부분이 이해가 가지 않는다면, 다음과 같이 변경해주어도 된다.

 

 

// ... //
	for(int i = 0; i < s.length(); i++) {
		char v = s.at(i);
// ... //
	}

 

 

 

 

---

- 방법 2 : [향상 시킨 입출력]

 

 

 

이 번에는 입력과 출력이 번갈아가면서 발생하기 때문에 stdio 라이브러리와의 동기화를 끊어주고 입출력을 분리시켜 입출력을 향상시켜보았다.

 

알고리즘 자체는 다른 것은 없다.

 

#include <iostream>
#include <string>

using namespace std;

int OX(string& s) {
	
	int cumulative = 0;
	int sum = 0;

	for(char &v : s) {
		/*
		 * O 문자일 경우 누적합을 1 증가시킨 뒤 
		 * 해당 값에 대해 누적합
		 */
		if(v == 'O') {
			cumulative++;
			sum += cumulative;
		}
		else {
			cumulative = 0;
		}
	}
	return sum;
}

int main(int argc, const char * argv[]) {

	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);

	int T;
	cin >> T;

	for(int i = 0; i < T; i++) {
		string s;
		cin >> s;

		cout << OX(s) << "\n";
	}

	return 0;
}

 

 

 

크게 어려울 것은 없을 것이다.

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 36176540  -  방법 2 : 향상시킨 입출력 

채점 번호 : 36176533  -  방법 1 : 기본 입출력

 

 

결과를 보면 그렇게 큰 차이는 아니지만, 약소하게나마 방법 2가 빠른 것을 볼 수 있다.

 

 

---

• 정리

 

이 번 문제는 그리 어렵지는 않았을 것이다. 아마 배열에 포함되는 이유라면 string 구현 형태가 대부분 char 타입의 배열 형태라서 그럴 것이다. 

C로 풀어보신 분들이라면 char 배열을 선언하여 썼었을 것이고, Java나 타 언어에서도 보면 거의 대부분의 언어의 문자열 타입은 내부적으로는 char 타입의 배열 형태라고 보시면 된다.

그렇기 때문에 배열 카테고리에 분류되어 이를 순회하는 방법에 대해 알아보자는 의미이지 않을까..

 

만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.