10096 세 친구

문제링크

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

문제

풀이

  1. n%2==0 이라면 NOT POSSIBLE

  2. n이 홀수라면 문자열 s의 길이 l = n/2

  3. 문자열을 나누어서 비교한다

    1. fir = 0 ~ (l-1) , sec = l ~ (n-1)
    2. fir = 0 ~ l , sec = (l+1) ~ (n-1)

  4. 두가지 경우에 대해

    1. 두가지 경우 모두 한자리씩 다른 경우

      • fir==sec 인 경우 해당 문자열을 출력
      • fir!=sec 인 경우 NOT UNIQUE
    2. 첫 번째 경우만 한 자리가 다른 경우

      • fir을 출력(길이가 n인 문자열)
    3. 두 번째 경우만 한 자리가 다른 경우

      • sec을 출력(길이가 n인 문자열)
    4. 두 가지 경우 모두 두 자리 이상 다른 경우

      • NOT POSSIBLE 출력

코드

#include <iostream>
#include <string>
using namespace std;
string s;
int n,cnt1,cnt2;
int main() {
	cin >> n >> s;
	if (n % 2 == 0) {
		cout << "NOT POSSIBLE";
		return 0;
	}
	n /= 2;

	int idx1 = 0, idx2 = n;
	while(idx1<n && idx2<s.size()) {
		if (s[idx1] != s[idx2]) {
			cnt1++;
			idx2++;
			continue;
		}
		idx1++; idx2++;
	}
	if (cnt1 == 0) cnt1++;

	idx1 = 0, idx2 = n + 1;
	while(idx1<n+1 && idx2<s.size()) {
		if (s[idx1] != s[idx2]) {
			cnt2++;
			idx1++;
			continue;
		}
		idx1++; idx2++;
	}
	if (cnt2 == 0) cnt2++;

	string fir, sec;
	fir = s.substr(0, n);
	sec = s.substr(n + 1, n);
	if (cnt1 == 1 && cnt2 == 1) {
		if (fir == sec) cout << fir;
		else cout << "NOT UNIQUE";
	}
	else if (cnt1==1) cout << fir;
	else if (cnt2==1) cout << sec;
	else cout << "NOT POSSIBLE";
}

후기

쉬운듯 어려웠다.

좋은 웹페이지 즐겨찾기