[C++] 15904번: UCPC는 무엇의 약자일까?

링크

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

15904번: UCPC는 무엇의 약자일까?

문제

UCPC는 '전국 대학생 프로그래밍 대회 동아리 연합 여름 대회'의 줄임말로 알려져있다. 하지만 이 줄임말이 정확히 어떻게 구성되었는지는 아무도 모른다. UCPC 2018을 준비하던 ntopia는 여러 사람들에게 UCPC가 정확히 무엇의 줄임말인지 물어보았지만, 아무도 정확한 답을 제시해주지 못했다. ntopia가 들은 몇 가지 답을 아래에 적어보았다.

• Union of Computer Programming Contest club contest
• Union of Computer Programming contest Club contest
• Union of Computer Programming contest club Contest
• Union of Collegiate Programming Contest club contest
• Union of Collegiate Programming contest Club contest
• Union of Collegiate Programming contest club Contest
• University Computer Programming Contest
• University Computer Programming Club contest
• University Computer Programming club Contest
• University Collegiate Programming Contest
• University CPC
• ...

ntopia는 이렇게 다양한 답을 듣고는 UCPC가 무엇의 약자인지는 아무도 모른다고 결론내렸다. 적당히 슥삭해서 UCPC를 남길 수 있으면 모두 UCPC의 약자인 것이다!

문자열이 주어지면 이 문자열을 적절히 축약해서 "UCPC"로 만들 수 있는지 확인하는 프로그램을 만들어보자.

축약이라는 것은 문자열에서 임의의 문자들을 제거하는 행동을 뜻한다. 예를 들면, "apple"에서 a와 e를 지워 "ppl"로 만들 수 있고, "University Computer Programming Contest"에서 공백과 소문자를 모두 지워 "UCPC"로 만들 수 있다.

문자열을 비교할 때는 대소문자를 구분해 정확히 비교한다. 예를 들어 "UCPC"와 "UCpC"는 다른 문자열이다. 따라서 "University Computer programming Contest"를 "UCPC"로 축약할 수 있는 방법은 없다.

그나저나 UCPC는 정말 무엇의 약자였을까? 정확히 아시는 분은 제보 부탁드립니다.

입출력 예제

입력

첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 경우도 없다.

출력

첫 번째 줄에 입력으로 주어진 문자열을 적절히 축약해 "UCPC"로 만들 수 있으면 "I love UCPC"를 출력하고, 만들 수 없으면 "I hate UCPC"를 출력한다.

예제 입력 1 복사

Union of Computer Programming Contest club contest

예제 출력 1 복사

I love UCPC

예제 입력 2 복사

University Computer Programming

예제 출력 2 복사

I hate UCPC

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int main(void)
{
	string str = "";
	string result = "";

	bool visit_U = false;
	bool visit_C = false;
	bool visit_P = false;
	bool visit_lastC = false;

	getline(cin, str); // 공백포함 입력
	for (auto temp : str)
	{
		if (temp == 'U')
		{
			if (!visit_U && !visit_C && !visit_P && !visit_lastC)
			{
				result += temp;
				visit_U = true;
			}
		}
		else if (temp == 'C')
		{
			if (visit_U && !visit_C && !visit_P && !visit_lastC)
			{
				result += temp;
				visit_C = true;
			}
			else if (visit_U && visit_C && visit_P && !visit_lastC)
			{
				result += temp;
				visit_lastC = true;
			}
		}
		else if (temp == 'P')
		{
			if (visit_U && visit_C && !visit_P && !visit_lastC)
			{
				result += temp;
				visit_P = true;
			}
		}
	}

	if (result == "UCPC") cout << "I love UCPC";
	else cout << "I hate UCPC";

	return 0;
}

풀이

• 그리디 알고리즘을 사용하였다.
• 처음에는 대문자만 간추려서 UCPC가 되면 통과인줄 알았는데 알고보니 UUUUCPPPPUUUUC
  처럼 그냥 문자열에 U , C , P , C 가 아무튼 순서대로 나온다면 통과되는 문제였다.
• UCPC에 해당하는 bool변수 4개를 만들어서 앞의 단어가 먼저 나와야 뒤에 단어의 방문을 체크하도록 하였다.
  이로 인하여 순서대로 문자가 나오는 경우를 체크 할 수 있다.