-
[BOJ] 2866번 문자열 잘라내기 (C++)Algorithm 2021. 12. 14. 01:15
- 1차 접근
가장 처음 떠올린 방법은 명세를 그대로 따라 구현을 하는 것이였다.
1. 현재 제거될 행을 제거한다.
2. 행을 제거한 테이블에 중복이 있다면 종료하고 정답을 출력한다.
안될 것 같다는 약간의 의심과 함께 위 로직을 구현해보면 시간초과가 발생한다.
최악의 경우 O(R*C)의 복잡도를 가진다.
- 2차 접근
다음 떠올린 방법은 이분탐색을 활용하는 것이다.
이분탐색을 활용하면 로직이 다음과 같이 개선된다.
1. 이분탐색을 통해 중복 검사를 할 행(mid)을 정한다.
2. 해당 행에 중복 문자열이 있는지 검사한다.
2-1. 중복 문자열이 있다면 end 값을 mid-1로 설정한다.
2-2. 중복 문자열이 없다면 start 값을 mid+1로 설정하고, 정답값을 업데이트한다.
3. 이분탐색이 끝나면 정답을 출력한다.
개선 후에 통과를 받을 수 있었고 시간복잡도는 O(logR*C)로 개선이 가능하다.
- 실수
너무나도 기본적인 실수를 했다.
정답값 배열을 0으로 초기화하지 않아 한 번 틀렸다.
- 코드
#include <iostream> #include <string> #include <vector> #include <set> using namespace std; int R, C; vector<string> list; bool check(int row) { set<string> s; for(int i = 0; i < C; i++) { string str; for(int j = row; j < R; j++) str += list[j][i]; if(s.find(str) != s.end()) return false; s.insert(str); } return true; } int main() { int start, end, mid, ans = 0; string str; cin >> R >> C; for(int i = 0; i < R; i++) { cin >> str; list.push_back(str); } start = 0; end = R - 1; while (start <= end) { mid = (start + end) / 2; if(check(mid)) { start = mid + 1; if(ans < mid) ans = mid; } else end = mid - 1; } cout << ans << '\n'; return 0; }
'Algorithm' 카테고리의 다른 글
[BOJ] 3917번 백조의 호수 (C++) (0) 2021.12.24 [BOJ] 1082번 방 번호 (C++) (0) 2021.12.21 [BOJ] 14500번 테트로미노 (C++) (1) 2021.09.13