[BOJ] 2866번 문자열 잘라내기 (C++)

문제 (https://www.acmicpc.net/problem/2866)

2866번: 문자열 잘라내기

처음엔 시간 초과로 헤맸던 문제이다 ,,

문제에 "가장 처음에 주어지는 테이블에는 열을 읽어서 문자열을 만들 때, 동일한 문자열이 존재하지 않는 입력만 주어진다."도 못 읽어서 처음 주어졌을 때도 따로 체크하고 그랬다 허허 문제를 잘 읽자!!!!

 

0. 입력을 다 받은 후에, 마지막 행만 검사를 한다.

1. 마지막 행에서 중복되는 단어가 없으면 위에 어떤 단어가 붙어도 문자열들은 중복되지 않는다. ➡ r - 1 출력하고 끝

2. 마지막 행에서 중복되는 단어가 있으면 마지막 행부터 위의 행으로 올라가며 문자열을 검사한다. 중복되는 문자열이 존재하는지 검사하기 위해 set을 사용했다. set의 크기가 c와 같아지면 ➡ 그때의 행 번호를 출력하고 끝

---

[소스코드]

---

2021-11-16

Gold 5

알고리즘 분류

- 문자열

- 정렬

- 이분 탐색