코드 포스(Code Force) 393 - A. NineTeen

문제 유형: 수학

문제 URL: http://codeforces.com/contest/393/problem/A

  이 문제는 특정한 문자열이 주어졌을 때 그 문자열의 문자들을 재정렬해서 "nineteen"이라는 문자열을 몇 개나 만들 수 있는지 물어보는 문제입니다. 예를 들어 문자열 "xiineteenppnnnewtnee"이 주어졌을 때 이를 "xnineteenppnineteenw"와 같이 재정렬한다면 "nineteen" 문자열이 두 번 나오게 되는 것입니다. 따라서 위 경우 최대 2개 만들 수 있으므로 정답은 2입니다.

  또한 "nineteen"이라는 문자열의 개수를 셀 때는 전체 문자열을 앞에서부터 한 자씩 읽어 확인하므로 문자를 읽다가 건너 뛸 수 없습니다. 또한 문자 n은 끝과 시작이 이어질 수 있습니다. 예를 들어 "nineteenineteen"과 같이 나열하면 n의 개수가 5개여도 "nineteen"을 2번 찾을 수 있습니다.

  이 문제는 단순히 n, i, e, t 문자의 개수를 세서 풀 수 있습니다. "nineteen"은 n 3개, i 1개, e 3개, t 1개로 이루어집니다. 따라서 만들 수 있는 "nineteen"의 최대 개수를 구하기 위해서는 각 문자를 몇 개씩 가지고 있느냐를 기준으로 개수를 찾을 수 있을 것입니다. 특히 n은 끝과 시작이 이어질 수 있기 때문에 사실상 n은 2개만 있어도 하나의 "nineteen"을 구성할 수 있다고 고려해야 합니다.

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>
#include <stdio.h>
#include <limits.h>

using namespace std;

int main(void) {
	int nC = 0;
	int iC = 0;
	int eC = 0;
	int tC = 0;
	string input;
	cin >> input;
	for(int i = 0; i < input.size(); i++) {
		if(input[i] == 'n') nC++;
		else if(input[i] == 'i') iC++;
		else if(input[i] == 'e') eC++;
		else if(input[i] == 't') tC++;
	}
	int res = INT_MAX;
	if(nC > 3) {
		// n은 끝과 시작이 이어질 수 있습니다. 
		res = min(res, (nC - 1) / 2);
	}
	else {
		res = min(res, nC / 3);
	}
	res = min(res, iC);
	res = min(res, tC);
	res = min(res, eC / 3);
	cout << res;
	return 0;
}