ALGORITHM/BOJ

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

yegyeom 2021. 11. 18. 03:55

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

 

2866번: 문자열 잘라내기

첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자

www.acmicpc.net

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

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

 

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

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

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


[소스코드]


더보기

2021-11-16

Gold 5

알고리즘 분류

- 문자열

- 정렬

- 이분 탐색

'ALGORITHM > BOJ' 카테고리의 다른 글

[BOJ] 1920번 수 찾기 (C++)  (0) 2021.12.16
[BOJ] 12904번 A와 B (C++)  (0) 2021.11.24
[BOJ] 16234번 인구 이동 (C++)  (0) 2021.11.18
[BOJ] 20055번 컨베이어 벨트 위의 로봇 (C++)  (0) 2021.10.22
[BOJ] 3055번 탈출 (C++)  (0) 2021.10.14