https://www.codetree.ai/training-field/search/problems/alphabet-X-2?&utm_source=clipboard&utm_medium=text

---

풀이

'푸는 방법'은 오래 걸리지 않았는데, '푸는 조건'을 구상하는데 오래 걸렸다.

푸는 방법은 간단했다.

1. String으로 문자열을 받는다.
2. 받은 문자열을 알파벳순서로 놓는다.
3. 각자 알파벳의 시작점과 끝점을 놓는다. 구조체를 사용한다.
4. 'A'부터 'Z'까지 하나씩 비교하면서 각 직선에서 조건을 찾아 어중간한 것을 찾는다.

처음 볼 때까지만 해도 간단히 풀 수 있을 것이라는 기대에 굉장히 싱글벙글 했었다.

#include <iostream>
using namespace std;

string str;
int i, j, cnt;

// 구조체
struct alp {
	int startPos, endPos;
};

// 구조체 초기화
alp alpArr[26];

// 한번 알아봤던 것인지 확인하는 배열
int check[26];

int main()
{
	//freopen("input.txt", "r", stdin);

	cin >> str;

	// 각 알파벳의 시작지점과 끝나는 지점을 구한다.
	for (i = 0; i < 52; i++) {
		int num = str[i] - 'A';

		if (check[num] == 0) {
			alpArr[num].startPos = i;
			for (j = i + 1; j < 52; j++) {
				if (str[i] == str[j])
					alpArr[num].endPos = j;
			}
			check[num] = 1;
		}
	}

	// 하나씩 비교하면서 대응되는 알파벳이 완벽하게 겹치는지 어중간하게 겹치는지 구한다.
	for (i = 0; i < 25; i++) {
		for (j = i + 1; j < 26; j++) {
			// 비교 끝점 < 기준 시작점
			if (alpArr[j].endPos < alpArr[i].startPos) continue;
			// 비교 시작점 > 기준 끝점
			else if (alpArr[j].startPos > alpArr[i].endPos) continue;
			// 기준의 시작점 < 비교 시작점과 끝점 < 기준의 끝점
			else if (alpArr[j].startPos > alpArr[i].startPos && alpArr[j].endPos < alpArr[i].endPos) continue;
			// 나머지를 카운트
			else {
				cnt++;
			}
		}
	}

	cout << cnt;
	
	return 0;
}

해당 코드를 빠르게 만들고 정답을 축하하려는 찰나...

테스트 케이스에서 오류가 떴다.

흐음... 왜 이런 일이 일어나는 걸까?

음?! 변수가 잘못된 것일까?

FAIL

아하! 문자열 때문이구나! char로 받았어야 했어!

FAIL

오호라...! 반복문이 잘못되었던 것이구나!!

FAIL

결국 어중간한 것을 골라내는 조건이 잘못되었다는 것을 알아채기까지 너무 오랜시간이 걸려버렸다...

그리고 수 많은 시도 끝에 정답을 맞추고야 만 것이다.

---

코드

코드는 다음과 같다.

#include <iostream>
using namespace std;

string str;
int i, j, cnt;

// 구조체
struct alp {
	int start, end;
};

// 구조체 초기화
alp segments[26];

// 한번 알아봤던 것인지 확인하는 배열
int check[26];

int main()
{
	freopen("input.txt", "r", stdin);

	cin >> str;

	// 각 알파벳의 시작지점과 끝나는 지점을 구한다.
	for (i = 0; i < 52; i++) {
		int num = str[i] - 'A';

		if (check[num] == 0) {
			segments[num].start = i;
			for (j = i + 1; j < 52; j++) {
				if (str[i] == str[j])
					segments[num].end = j;
			}
			check[num] = 1;
		}
	}

	// 하나씩 비교하면서 대응되는 알파벳이 완벽하게 겹치는지 어중간하게 겹치는지 구한다.
    for (int i = 0; i < 26; i++) {
        for (int j = i + 1; j < 26; j++) {
            // 선분 i와 j가 겹치는지 확인
            if (segments[i].end < segments[j].start || segments[j].end < segments[i].start) {
                continue; // 겹치지 않음
            }
            // 어중간하게 겹치는지 확인
            if (segments[i].start < segments[j].start && segments[i].end > segments[j].end) {
                continue; // 완전히 포함
            }
            if (segments[j].start < segments[i].start && segments[j].end > segments[i].end) {
                continue; // 완전히 포함
            }
            // 어중간하게 겹치는 경우
            cnt++;
        }
	}

	cout << cnt;
	
	return 0;
}

갯수를 생각할 때는 다음의 경우를 생각해 볼 수 있다.

1. 선분끼리 겹치지 않는 경우
2. 선분끼리 완전히 겹치는 경우
3. 선분끼리 어중간하게 겹치는 경우

여기서 선분끼리 겹치지 않는 경우는 다음과 같다.

1. 비교하는 선분이 기준의 선분보다 좌측에 있는 경우(작은 경우)
2. 비교하는 선분이 기준의 선분보다 우측에 있는 경우(큰 경우)

그리고 완전히 겹치는 경우는 다음과 같다.

비교하는 선분이 기준의 선분의 안쪽에 있다. (품어지고 있다.)

그리고 이러한 경우를 제외한 나머지 경우는 어중간한 경우가 될 수 있다.

여기서 내가 간과한 부분은 비교하는 선분과 기준의 선분이 바뀔 수 있다는 것이다.

예를 들어, A-A 선분과 B-B 선분에서 A(B())가 될 수도 있지만, B(A())가 될 수도 있다. 이 경우를 생각해서 두 가지 경우 전부 제외했어야 했지만, 한쪽만 제외했기 때문에 오류가 발생했던 것.

문제를 찾고 난 뒤에는 엄청난 탈력감이 들었다. 고작 경우의 수 하나 때문에 내 몇 시간이...

그래도... 뭐...

맞췄으니 됐다! 다음에는 주의하도록 하자!

---