[백준/C++] ChatGPT 만들기 (No. 31911)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 구현만 잘하면 되는 문제다.

 

각 문자별로 다음에 어떤 문자가 올지 정해지면 이를 이용해 사이클을 찾아 계산하면 된다.

 

먼저 크게 두가지 경우로 나눌 수 있다.

 

1. 문자를 반복하면 ']' 로 끝나는 경우

2. 문자를 반복하면 계속 사이클이 생성되는 경우

 

1번의 경우는 ]가 나오면 그 뒤에 모든 문자는 '.' 으로 채우면 된다.

 

2번의 경우는 사이클이 생성되면 문자 사이클을 찾은 다음 그 문자사이클을 반복하면 된다.

 

위를 구현하기 위해 문자의 뒤에 어떤 문자가 많이 왔는지 map을 이용해 개수를 셌다.

그리고 정렬을 이용해 특정 문자의 뒤에는 어떤 문자가 오는지 계산했다.

 

예를 들어 [abcdebcdebcde 로 계속 반복되는 문자가 있는 경우를 생각해보자

 

그러면 bcde가 반복되는 문자이므로 K가 매우 큰 수여도 쉽게 구할 수 있다.

 

만약 K가 100000000004일 경우 문자의 [abcde 에서 첫 [a를 빼면 bcde가 계속 반복된다.

 

그러므로 [a의 길이인 2를 뺀 100000000002를 구할 수 있고, 이를 사이클의 길이인 4로 나누면 2를 얻을 수 있다.

 

이후 K의 첫번째 수는 bcde의 2번째인 c부터 시작해 M개의 문자를 출력하면 된다는 사실을 알 수 있다.

 

 

[아이디어 정리]

1. map을 이용해 문자 뒤에 나오게 되는 문자를 계산한다.
2. 문자가 ]로 끝나는지, 사이클이 존재하는지 구분한다.
3. ]로 끝나면 ]이후의 문자는 전부 '.'이 나오므로 이를 이용해 문자를 출력한다.
4. 사이클이 존재하면 반복되는 문자열의 길이를 구하고 이를 %연산을 이용해 문자를 출력한다.

 

 

Code

 

 

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long N,K,M;
	map<char, map<char, long long>> m;
	cin >> N >> K >> M;
	string str;
	for (int i=0; i<N; i++)
	{
		cin >> str;
		long long ttt = str.size();
		for (int j=0; j<ttt-1; j++)
		{
			m[str[j]][str[j + 1]] += 1;
		}
	}
	map<char, map<char, long long >> ::iterator it;
	map<char, vector<pair<char, long long>>> m2;
	for (it = m.begin(); it != m.end(); it++)
	{
		vector<pair<char, long long>> tv(it->second.begin(), it->second.end());
		sort(tv.begin(), tv.end(), [](pair<char, long long>a, pair<char, long long>b) {
				if (a.second == b.second)
				{
					return a.first < b.first;
				}
				return a.second > b.second;
			});
		m2[it->first] = tv;
	}
	long long idx = 1;
	map<char, long long> midx;
	string ans = "[";
	midx['['] = idx;
	char c,prev;
	long long ridx;
	long long flag = 0;
	for (idx=2; idx<K+M; idx++)
	{
		prev = ans[idx - 2];
		if (prev==']'){
			midx[']'] = idx;
			ans += ']';
			flag = 1;
			break;
		}
		else 
		{
			vector<pair<char, long long>> tt = m2[prev];
			if (midx[tt[0].first]!=0)
			{
				ridx = idx;
				c = tt[0].first;
				flag = 2;
				break;
			}
			ans+=tt[0].first;
			midx[tt[0].first]=idx;
			prev = tt[0].first;
		}
	}
	string oS = "";
	if (flag==0)
	{
		cout << ans.substr(K - 1, M);
	}
	else if (flag==1)
	{
		if (ans.size()<K)
		{
			for (long long i=0 ;i<M; i++)
			{
				cout << ".";
			}
		}
		else
		{
			oS=ans.substr(K - 1, ans.size()-K);
			cout << oS;
			for (long long i=0; i<M-oS.size(); i++ )
			{
				cout << ".";
			}
		}
	}
	else
	{
		long long cy = ridx - midx[c]; //cycle %
		long long cmp = midx[c] - K; //몇칸인지
		string stt = ans.substr(midx[c]-1);
		if (K<midx[c])
		{
			if (K+M<midx[c])
			{
				cout << ans.substr(K - 1, M);
				M = 0;
			}
			else
			{
				cout<<ans.substr(K - 1, midx[c]-K);
				M -= midx[c] - K;
			}
			for (int i=0; i<M/cy; i++)
			{
				cout << stt;
			}
			cout << stt.substr(0, M % cy);
		}
		else
		{
			K -= ans.size()+1;
			long long na=K%cy;
			string fi = stt.substr(na);
			if (fi.size()>=M)
			{
				cout << fi.substr(0,M);
			}
			else
			{
				cout << fi;
				M -= fi.size();
				for (long long i = 0; i < M / cy; i++)
				{
					cout << stt;
				}
				cout << stt.substr(0, M % cy);
			}
		}
	}

	return 0;
}

---

 

좀 더 편하게 풀 수 있었을 것 같은데 코드가 길어지고 오래걸린 문제였다.

게임을 하면서 풀어서 그런가...?

 

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