[G5] 백준 2866번 문자열 잘라내기 C++ 해시 맵, 매개 변수 탐색

리뷰

 

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

행을 위에서 부터 한 줄씩 제거하며 같은 열에 있는 문자열의 중복이 없는 최대로 삭제가 가능한 행의 개수를 구하는 문제

 

 

전역 변수

• n, m : 테이블의 세로/가로 길이를 저장할 변수
• ans : 정답을 저장할 변수
• lst : 테이블 정보를 저장할 문자열 배열

 

함수

없음

 

 

문제풀이

1. n, m값을 입력 받고, n개의 문자열을 lst배열에 입력 받아준다.
2. 변수 l을 0으로, r을 n - 1로 초기화 하고, l이 r미만인 경우 true로 while루프를 실행해 준다.
3. 매 루프마다 변수 mid에 l + r을 2로 나눈 몫을 저장해 주고, string, bool타입 해시맵 v를 초기화 해준다.
4. 변수 flag를 true로 초기화 하고, 변수 s에 mid행 부터 마지막 행 까지 각 열의 문자를 더해준다.
5. 만약 v에 s가 존재하면 flag를 false로 변환 후 break처리해 준다, 아니라면 해시맵에 s를 true로 추가해 준다.
6. 위 로직을 실행하고 난 뒤 flag가 true라면 ans와 mid를 비교해 더 큰 값을 저장해 주고, l을 mid + 1로 저장한다.
7. 아니라면 r을 mid - 1로 저장한다.
8. 모든 탐색을 마친 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 선형 탐색 대비 이분 탐색을 적용하면 시간 복잡도를 많이 줄일 수 있다.
• 어쩌면 선형 탐색으로는 풀이가 불가능한 문제일수도? 안돌려 봐서 모르겠다.

 

정답 코드

#include<iostream>
#include<unordered_map>
using namespace std;

int n, m, ans;
string lst[1000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> lst[i];

	int l = 0, r = n - 1;
	while (l <= r) {
		int mid = (l + r) / 2;
		unordered_map<string, bool> v;

		bool flag = true;
		for (int j = 0; j < m; ++j) {
			string s = "";
			for (int i = mid; i < n; ++i) {
				s += lst[i][j];
			}
			if (v[s]) {
				flag = false;
				break;
			}
			else v[s] = true;
		}

		if (flag) {
			ans = max(ans, mid);
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	cout << ans;
}