[Python] 백준 2866 문자열 잘라내기

문제 링크 : https://www.acmicpc.net/problem/2866

2866번: 문자열 잘라내기

 

1. 접근 방법

전체 탐색을 하기에는 많은 것 같고, 탐색을 줄이며 해결하기 위해 이분 탐색을 선택했다.

각 문자열이 중복인지 확인하기 위해 집합을 사용했다.

 

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2800/2866.py

GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장소입니다.

📕코드 해설

1) 처음에는 문제를 이해하는데 시간이 걸렸다.

어느정도 이해하고, 각 배열에서 일반적으로 오른쪽으로 읽는 게 아니라, 위에서 아래로 읽어가며 중복된 문자열이 있는지 찾아야 했다.

다만, 문제는 최대 1,000 길이의 문자열 1,000개가 입력되므로 최악의 경우 1,000,000번 이상의 탐색이 필요하다.

 

2) 이분탐색

이 문제에서 원하는 출력은 새로 만들어질 문자열의 새로운 시작점을 찾는다고 생각해도 된다.

주어진 예시,

dobarz
adatak

를 생각한다면, 총 6개 문자열을 생각할 수 있다.

da, od, ba, at, ra, zk

그렇다면, 문자열 시작 위치를 각 인덱스를 따른다고 하면, 최소 인덱스는 0, 최대는 1로 두고 이분 탐색을 할 수 있다.

입력 조건에 따라 초기 문자열은 중복이 없으므로 정답은 0으로 두고 탐색을 한다. 이분 탐색의 구조는 어렵지 않게 이해할 수 있을 것 같아 설명은 생략합니다.

조금 번거롭기는 하지만, for문만 잘 사용하면 여기서도 문제를 해결할 수 있다. 그러나 나는 조금 더 빠르게 해결하기 위해 배열의 반전과 집합을 사용했다.

 

3) 배열 반전

strings = [input().strip() for _ in range(R)]
strings = list(zip(*strings))

문자열들을 strings로 입력을 받고, 두 번째 줄(코드에서 13번째 줄)을 활용하여 배열 반전을 한다. 우선 해당 결과로 다음과 같이 탐색할 수 있다.

문제의 예제 3을 활용했다.

기존 위에서 아래로 탐색하면, 완전 연관 없는 문자열이 된다. 하지만, 배열을 반전시켜 활용하면 더욱 편하게 문제를 해결할 수 있다. 예를 들어 가장 왼쪽 'mmmm'이라는 문자열을 추출하기 위해 for문이 필요하지만, 각 위치마다 해결하기 위해 for문이 하나 더 필요하다.

배열을 반전하면, 배열에 ['m', 'm', 'm', 'm'] 형태로 저장되고, 나는 ''. join()을 활용하여 하나의 for문으로 해결할 수 있었다. 그리고 join을 활용하여 문자열로 변환되면 집합에 있는지 확인하여 빠르게 문자열 중복 여부를 검증할 수 있다.

여기서 조금 독특한 구조가 사용되었는데, (코드 19~28줄)

for j in range(C):
    word = ''.join(strings[j][mid:])
    if word in words:
        break
    words.add(word)
else:
    ans = mid
    top = mid + 1
    continue
bottom = mid - 1

함수의 return을 활용하면 편하게 해결할 수 있지만, 함수 없이 최대한 간결하게 작성하려 했다.

설명을 하면 다음과 같다.

- for문을 돌며 mid위치부터 문자열을 생성했을 때 중복인지 확인한다.

    - 만약 중복이면(if word in words) for문이 종료되고, bottom = mid - 1 이 실행된다.

- 모든 for문을 실행하고 중복이 없으면 for-else가 실행된다.

    - 이때, continue를 사용하여 아래의 bottom = mid - 1이 실행되지 않도록 했다.

 

3. 생각 정리

모든 코드를 확인해보지는 못했지만, 많은 풀이가 전체 탐색이나 2개의 for문을 활용한다.

총 두 가지, 배열을 회전하여 빠르게 각 단계별 문자열을 찾는 과정과 집합을 활용한 중복 확인으로 빠르게 해결할 수 있었다. 조금 번거로운 과정이 있을 수 있었지만, 남들과 다르게 생각하여 해결하는 건 때대로 즐거운 일이다.