12933 오리(C++)

오리

여러 오리가 꽥꽥 거릴 때, 오리가 몇마리인지 분석하는 문제

1. 문제

---

간단 설명

오리의 울음소리가 녹음된 문자열이 주어진다

문제 자체만 봐서는 이해가 잘 안되는 문제였으나, 힌트를 보고 이해가 됬다

즉, quack 이라는 문자열이 뒤섞인 문자열이 하나 주어지는데

이걸로 오리가 몇마리 있는지 분석하는 문제

2. 문제 분석

---

가장 간단하게 생각할 수 있는 방법으로는

녹음된 문자열 ‘quqaquuacakcqckkuaquckqauckack’을

문자열 앞에서부터 각 문자가, 어떤 오리가 소리를 내었는지 확인하는 방법이다

각 오리에게 문자를 q->u->a->c->k 순으로 할당해주면서

새로운 q가 나오면 새로운 오리를 추가하는 방식으로 진행한다

주의점

• 최대 2500글자이므로, 오리는 최대 500마리까지 나올수 있을듯

• 녹음 파일 자체에 문제가 있을수도 있다

필요변수

• 녹음 문자열 record (최대 2500자)

• 전체 오리의 수 max_duck_size (최대 500)

• 현재 문자가 이상 없는 문자인지 체크할 isPushed

• 오리의 소리를 저장할 변수 string duck[501]

알고리즘

1. 녹음 문자열을 입력받는다
2. 문자열의 앞에서 각 문자가 어떤 오리에 해당하는지 체크하면서 끝까지 확인한다
    2-1. 문자가 'q'라면
        2-1-1. 이미 삽입 완료된 문자라면 루프 종료
        2-1-2. 현재 오리가 비어있거나, 'quack'으로 한번 울었다면 다시 q 삽입 가능하므로,
            - 현재 오리의 맨 뒤에 q를 넣고, isPushed 변수에 넣었다고 표시해둔다
        2-1-3. 만약 전체 오리를 확인했는데, 'q'가 들어갈 자리가 없다면 
            - 새로운 오리가 운 것이므로, 전체 오리 수를 1 증가시키고 그 오리에게 추가한다
    2-2. 문자가 'u'라면
        2-2-1. 이미 삽입 완료된 문자라면 루프 종료
        2-2-2. 전체 오리를 탐색하면서 'u'가 들어갈 자리를 찾는다. 
    2-3. 'a', 'c', 'k' 에 대해서도 같은 방법으로 수행
    2-4. 만약 문자가 들어가지 못했다면 
        - 잘못된 녹음이므로 -1 출력 후 종료
3. 녹음을 다 돌렸으나 음성이 완성되지 않은 경우 -1을 출력 후 종료
    - ex) quackqua 과 같이 quack으로 완성되지 않고 종료된 경우
4. 전체 오리 수를 출력하고 종료한다

시간 복잡도는

최대 2500글자 * 최대 500마리 일때, 1,250,000번 수행한다. 2초 내에 충분히 가능

3. 소스코드

---

#include <iostream>
#include <string>

using namespace std;

string duck[501];

int main() {
	string record;
	// cin >> record;
	record = "qquackuack";

	int max_duck_size = 1;

	for (char ch : record) {
		bool isPushed = false;

		// q가 나온 경우, 
		if (ch == 'q') {
            // 기존 오리들 중에 비어있거나, 한번 'quack'을 완성한 오리를 찾음
			for (int i = 1; i <= max_duck_size; i++) {
				if (isPushed) break;
				if (duck[i].size() % 5 == 0) { // 모듈러 연산을 이용해 어떤 문자 차례인지 확인한다
					duck[i].push_back(ch);
					isPushed = true;
				}
			}
			// 새로운 q가 나타났는데, 들어갈 자리가 없다면 오리 한마리 추가
			if (isPushed == false) {
				max_duck_size++;
				duck[max_duck_size].push_back(ch);
				isPushed = true;
			}
			
		}

        // u, a, c, k 는 모듈러 연산만 다르고 구조는 같다
		else if (ch == 'u') {
			for (int i = 1; i <= max_duck_size; i++) {
				if (isPushed) break;
				if (duck[i].size() % 5 == 1) {
					duck[i].push_back(ch);
					isPushed = true;
				}
			}
		}
		else if (ch == 'a') {
			for (int i = 1; i <= max_duck_size; i++) {
				if (isPushed) break;
				if (duck[i].size() % 5 == 2) {
					duck[i].push_back(ch);
					isPushed = true;
				}
			}
		}
		else if (ch == 'c') {
			for (int i = 1; i <= max_duck_size; i++) {
				if (isPushed) break;
				if (duck[i].size() % 5 == 3) {
					duck[i].push_back(ch);
					isPushed = true;
				}
			}
		}
		else if (ch == 'k') {
			for (int i = 1; i <= max_duck_size; i++) {
				if (isPushed) break;
				if (duck[i].size() % 5 == 4) {
					duck[i].push_back(ch);
					isPushed = true;
				}
			}
		}

		if (isPushed == false) {
			cout << -1;
			return 0;
		}
	}

	// 녹음을 다 돌렸으나 음성이 완성되지 않은 경우를 체크 ex) quackqua
	for (int i = 1; i <= max_duck_size; i++) {
		if (duck[i].size() % 5 != 0) {
			cout << -1;
			return 0;
		}
	}

	cout << max_duck_size;
	return 0;
}