https://www.acmicpc.net/problem/2866
2866번: 문자열 잘라내기
문제 R개의 행과 C개의 열로 이루어진 테이블이 입력으로 들어오게 됩니다. 이 테이블의 원소는 알파벳 소문자로 주어집니다. 각 테이블의 열을 위에서 아래로 읽어서 하나의 문자열을 만들 수 있습니다. 예제 입력에서 dobarz adatak 이 주어지는 경우 "da", "od", "ba", "at", "ra", "zk"와 같이 6개의 문자열들이 만들어지게 됩니다. 만약 가장 위의 행을 지워도 테이블의 열을 읽어서 문자열이 중복되지 않는다면, 가장 위의 행을
www.acmicpc.net
테이블의 행을 i-1번째까지 지운 상태에서 i번째행부터의 문자열을 검사한다고 했을 때, 동일한 문자열이 있다면 그 이후 문자열들도 중복이다. 예를 들어, abc와 abc가 중복이면 이후인 bc와 bc, c와 c가 중복이기 때문이다.
반대로 중복이 아니라면 i-1번째 행까지 지웠을 때에도 중복이 아니다. 그 이전에 중복이면 위와 같은 이유로 현재도 중복일 것이기 때문이다.
이분 탐색으로 mid번째 행부터 시작하는 문자열(mid-1번째까지는 지워진 상태)을 검사하여 동일한 문자열이 발생한다면 mid 이전의 행을 탐색하고, 만약 동일한 문자열이 발생하지 않는다면 더 큰 값을 찾기 위해 mid이후의 행을 지웠을 때의 문자열들을 검사해서 정답을 구할 수 있다. 중복이 발생하지 않은 행 중 최댓값이 count값으로 정답이 된다.
문자열의 중복을 검사할 때에는 set을 이용하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include <iostream>
#include <string>
#include <set>
using namespace std;
int r, c;
int ans;
char table[1000][1000];
bool check(int start, int end) {
set<string> s;
for (int j = 0; j < c; j++) {
string tmp;
//start행부터 마지막행까지 읽어서 문자열을 만든다.
for (int i = start; i <= end; i++) tmp += table[i][j];
//set에 문자열이 존재한다면 바로 false를 리턴한다.
if (s.find(tmp) == s.end())
s.insert(tmp);
else
return false;
}
return true;
}
void binarySearch(int left, int right, int end) {
if (left > right) return;
int mid = (left + right) / 2;
//mid번째 행부터 마지막 행까지의 문자열을 검사
bool flag = check(mid, end);
if (flag) {
//동일한 문자열이 발생하지 않았다면 mid이후 부분을 검사
//중복이 발생하지 않은 행 중 최댓값이 정답
if (ans < mid) ans = mid;
binarySearch(mid + 1, right, end);
}
else {
//동일한 문자열이 발생했다면 mid 이전 부분을 검사
binarySearch(left, mid - 1, end);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> table[i][j];
}
}
ans = 0;
//처음에 주어지는 테이블에는 열을 읽어서 문자열을 만들 때, 동일한 문자열이 존재하지 않음이 보장되므로 1번째 행부터 검사
binarySearch(1, r - 1, r - 1);
cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 2174. 로봇 시뮬레이션 (0) | 2020.04.28 |
|---|---|
| [BOJ] 10711. 모래성 (0) | 2020.04.27 |
| [BOJ] 5427. 불 (0) | 2020.04.19 |
| [BOJ] 18809. Gaaaaaaaaaarden (0) | 2020.03.23 |
| [BOJ] 18808. 스티커 붙이기 (0) | 2020.03.23 |