백준/해시

[백준] C++ 2866번 문자열 잘라내기

2zreal 2024. 10. 6. 18:06

위 예제와 같은 경우에는 가장 위에 행을 지우면 a d a t a k 이렇게 a가 중복되어서 count가 0이 된다.

 

문제해결방법

1. 행과 열을 바꿔서 string에 저장한다.

2. 열을 하나씩 지워주면서 단어를 수집하는데 이 단어를 HashSet에 저장한다.

3. 만약 HashSet에 이미 존재한다면 count를 출력하고 종료한다.

 

substr를 사용하기 위해 행과 열을 바꿔서 string에 저장함.

#include <iostream>
#include <unordered_set>
using namespace std;
string s[1001];
int main(void)
{
	int R, C = 0;
	cin >> R >> C;
	for (int i = 0; i < R; i++)//행과 열을 바꿈
	{
		char temp = ' ';
		for (int j = 0; j < C; j++)
		{
			cin >> temp;
			s[j] = s[j] + temp;
		}
	}
	int count = 0;


	for (int i = 1; i < C; i++)
	{
		unordered_set<string> hashSet;//이걸 지역변수로 선언해서 메모리 초과를 방지.
		for (int j = 0; j < C; j++)
		{
			string temp = "";

			temp = s[j].substr(i, R);
			//cout << temp<<"\n";
			if (hashSet.find(temp) == hashSet.end())//HashSet에 존재하는가??
			{
				hashSet.insert(temp);
			}
			else
			{
				cout << count;
				return 0;
			}
		}
		count++;
	}
	return 0;
}

'백준 > 해시' 카테고리의 다른 글

[백준] C++ 1354번 무한 수열2  (1) 2024.10.03
[백준] C++ 1351번 무한수열  (0) 2024.10.02
[백준] C++ 2910번 빈도정렬  (0) 2024.10.01
[백준] C++ 13414 수강신청  (0) 2024.10.01
[백준] C++ 1302번 베스트셀러  (0) 2024.10.01