백준 11478 c++ "서로 다른 부분 문자열의 개수" -PlusUltraCode-

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

 

[필자 사고]

부분 문자열의 갯수를 구해야 되는 문제이다.

시간복잡도를 계싼해 보면 n(n+1)/2 의 경우의 수가 나온다

현재 수는 1000에 해당되므로 1억이 넘지 않아 시간내에 문제를 풀 수 있다.

 

필자는 map을 이용하여 insert 삽입 과정을 log n 검색 작업을 log n 을 이용하여 문제를 해결했다.
아래는 자세한 코드 해설이다.

[코드 해설]

1. 입력 받기

• 사용자로부터 문자열을 입력받습니다.
• 입력은 전역 변수 str에 저장됩니다.

---

2. 게임 시작(Game_Start 함수)

• 이 함수에서는 문자열 str의 모든 연속된 부분 문자열을 생성합니다.
• 바깥쪽 반복문 i는 부분 문자열의 시작 위치를 나타냅니다.
• 안쪽 반복문 k는 끝 위치를 확장해가며 부분 문자열을 만듭니다.
• 만들어진 부분 문자열은 strTank라는 변수에 저장되고, 이 문자열을 map 자료구조 myMap에 삽입합니다.
  • map은 중복된 키를 허용하지 않기 때문에, 중복된 부분 문자열은 하나만 저장됩니다.

[소스 코드]

#include <iostream>
#include <cstring>
#include <vector>
#include <map>
using namespace std;

map<string, int> myMap;
string str;

void Input() {
	cin >> str;
	
}

void Game_Start() {
	for (int i = 0; i < str.size(); i++) {
		string strTank = "";
		for (int k = i; k < str.size(); k++) {
			strTank += str[k];
			myMap.insert({ strTank,1 });
		}
	}
	cout << myMap.size();
}

int main(void) {
	Input();
	Game_Start();
}