[PS] [Baekjoon] 2866. 문자열 자르기

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

 

언어 : 파이썬 (Python 3)

시작 : 2025.01.11 13:00

종료 : 2025.01.11 13:40

티어 : Gold V

비고 : 2010/2011 COCI Contest #3 4번

 

태그 :

이분 탐색

문제 해석

 

길이가 $C$인 문자열이 $R$개 주어진다.

문자열을 세로로 읽으면 $C$개의 문자열이 나온다.

 

예시를 들자면,

2 6

dobarz

adatak 에 대해

"da", "od", "ba", "at", "ra", "zk" 문자열이 나온다.

 

이렇게 구한 문자열들이 서로 겹치지 않으면 맨 윗줄을 지우고 count를 1 더한다.

겹친다면 count를 출력한다.

 

유의할 점은,

입력으로 주어지는 문자열을 세로로 읽으면 절대 겹치지 않는다.

맨 윗 줄을 한 번 지우고 겹치는지 안 겹치는지 체크하면 된다.

(설명이 이상한데 주어진 3가지 예제 입력을 보면 이해가 빠를 것이다...)

풀이

 

처음에는 그냥 단순히 위에서부터 하나씩 지워가며 시뮬레이션을 돌려봤다.

aaa

bbb

ccc

면 aaa 지우고 문자열 3개 만들고 각자 set에 넣고 테스트... 뭐 이런 식.

 

그게 풀이 1이고 당연히 시간 초과로 실패했다.

 

실질적으로 $R$이나 $C$나 1000을 넘지 않기 때문에,

문자열을 더하는 로직은 대략 $1000*(1000+999+998+...+1)$번 수행된다.

그리고 이는 대략 5억이므로 1초의 타임 리밋에 걸릴 것.

 

어찌보면 당연한 얘기지만 1000이라는 작은 숫자에 현혹되어 아슬아슬 통과될 거라 생각했다.

 

 

그래서 태그를 슬쩍 봤는데 이분 탐색이라는 태그가 보인다. 아하.

 

뇌에 시뮬레이션을 굴려보면 이런 로직이 될 것이다.

 

1) R = 100, C = 100이라 가정한다.

2) count 시작은 0과 100 사이인 50으로 시작. 위의 50줄을 지운다.

3-1) 만약 겹치는 게 없다면 위 50줄은 지워도 상관없다. 다음 검사는 (100+50) // 2 = 75줄을 지우고 검사한다.

3-2) 겹치는 게 있다면 위에 50줄을 지우면 안 된다는 얘기. 20줄만 지우든 30줄만 지우든, 아무튼 50줄보다 적게 지워야 비로소 겹치지 않는 경우가 발생한다. 따라서 다음 검사는 (0+50) // 2 = 25줄을 지우고 검사.

4) 이런 식으로 반복하다 더 이상 검사할 게 없다면 count를 출력.

 

 

3-2)를 좀 더 자세히 설명하자면,

0 abcde

1 aaaaa

2 aaaaa

3 aaaaa

4 aaaaa

 

다음 예시에서 count 시작은 2행이다. (4 + 0) // 2 = 2.

2행까지 지우고 3행, 4행으로 문자열을 만들면 aa 문자열이 겹친다.

그러면 2행 이전부터 겹침이 발생했다는 의미이므로, (0 + 2) // 2 = 1행을 다시 검사한다.

 

 

코드

 

풀이 1) 시간 초과

import sys
input = sys.stdin.readline

R, C = map(int, input().split())
S = [list(input().rstrip()) for _ in range(R)]



count = 1

while count < R:
    contains = set()
    for x in range(C):
        temp = ''
        for y in range(count, R):
            temp += S[y][x]

        if temp not in contains:
            contains.add(temp)
        else:
            break
    else:
        count += 1
        continue

    break

print(count - 1)

 

풀이 2) 성공

import sys
input = sys.stdin.readline

R, C = map(int, input().split())
S = [list(input().rstrip()) for _ in range(R)]



_min, _max = 0, R-1
count = (_min + _max) // 2

while _min <= _max:
    contains = set()
    for x in range(C):
        temp = ''
        for y in range(count, R):
            temp += S[y][x]

        if temp not in contains:
            contains.add(temp)
        else:
            _max = count - 1
            break
    else:
        _min = count + 1

    count = (_min + _max) // 2

print(count)