구름톤 2주차 후기 -1

이번 문제는 난이도가 확 올라갔다. 

ㅠㅠㅠ... 중복 부분 문자열을 제거하고 사전 순으로 정렬하는 부분을 제대로 구현하지 않아 생긴 문제가 많았다. 

ㅠㅠ...,,

 

구현한 코드는 다음과 같다. 

 

눈여겨 볼 점:

중복을 피하기 위해 map 을 사용했는데 중요한 점은 map은 저장 순서가 유지되지 않고 어차피 사전순으로 정렬되면서 알아서 저장된다. 

그래서 iterator를 이용해서 점수를 차례대로 넣어주면 사전순이 구현된다. 

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;


int main() {
	int N;
	map<string, int> m;
	string str;
	cin >> N;
	cin >> str;
	//map 에 넣고 저장. 하고 없으면 점수 제거. 
	
	//str[0] -> 개수 1개, ... 개수 N -2 개
	// sort(str.begin(), str.end());
	// 
	int score = 1;
	for(int i = 0; i < N; i++){
		for(int j = 1; j <= N - 2 && i + j <= N; j++){
			string temp = "";
			temp = str.substr(i, j);
			if(m.find(temp) == m.end())
				m.insert(make_pair(temp, 0));
			else
				continue;
		}
	}
	

	map<string, int>::iterator it;
	for(it = m.begin(); it != m.end(); it++){
		it->second = score++;
	}
	
	
	//[0][1] [1][2] [3][1]
	long long max = -2147483648;
	long long sum;
	for(int x = 1; x < N ; x++){
		for(int y = 1; x + y < N && y <= N - 2; y++){
			sum = 0;
			string temp = str.substr(0, x);
			sum += m.find(temp)->second;
			
			temp = str.substr(x, y);
			sum += m.find(temp)->second;
			
			temp = str.substr(x+y, N-x-y);
			sum += m.find(temp)->second;
			
		// cout << x << " " << y << " " << sum << "\n";
			if(sum > max)
					max = sum;		
		}
	}
	cout << max <<"\n";
	
	return 0;
}

 

주위 다른 분이 DFS 로 만든 부분 문자열은 다음과 같다. (depth 3 부분을 주의깊게 보자. )

void dfs(int depth, string& input, vector<string>& sel, vector< vector<string> >& list, map<string, int>& myMap, int cur)
{
	if (depth == 3)
	{
		if (cur == input.length())
		{
			for (int i=0; i<3; ++i)
				myMap.insert(make_pair(sel[i], 0));
			list.push_back(sel);
		}
		return;
	}
​
	for (int i=cur; i<input.length(); ++i)
	{
		sel[depth].push_back(input[i]);
		dfs(depth + 1, input, sel, list, myMap, i + 1);
	}
	sel[depth].clear();
}