2866. [Python]문자열 잘라내기

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 256MB
• 정렬

 

3. 파이썬 코드

 

import sys

input = sys.stdin.readline
# 행, 열 길이
R, C = map(int,input().split())
# 문자열 받아옴
words = [ list(map(str,input().strip())) for _ in range(R) ]
# 문자 역순으로 저장
new_words = []
# 아래서부터 문자열을 저장
for j in range(C):
    ans = ""
    for i in range(R-1,-1,-1):
        ans += words[i][j]
    new_words.append(ans)
# 문자열 정렬
new_words.sort()
# 최종 최대 공통되는 부분 길이 체크
max_index = 0
# 행 길이 만큼 반복
for i in range(1,C):
    # 초기 인덱스값 설정
    index = 0
    # 0번 인덱스부터 앞뒤 비교해가며 값이 같은경우
    if new_words[i-1][index] == new_words[i][index]:
        # 어디까지 공통된 부분인지 체크하는 while 선언
        while new_words[i-1][index] == new_words[i][index]:
            # index 값 1 씩 증가
            index += 1
        # 최고 index 값 갱신
        if max_index < index:
            max_index = index
# 아래서부터 max_index 값을 찾았기 때문에 열의 길이에서 max_index 값에 인덱스 값계산을 한 1을 더해서 정답 출력
print(R - max_index - 1)

 

4. 문제를 풀고난 후 생각

 

• 문자열을 입력받은 후 아래서 부터 새로운 문자열을 만들어낸다.
  • 예시로

    3 4
    alfa
    beta
    zeta​

  • 위와 같은 입력이 들어올 경우 'aaa', 'ttf', 'eel', 'zba' 문자를 만들어서 리스트에 저장한 후 정렬을 진행하여 비슷한 문자끼리 묶어준다.
  • 이후 반복문을 진행하여 앞뒤를 비교해가며 시작 문자가 같은 경우 index 값을 증가시켜가면서 계속 비교해간다.
• 이런 방식으로 index 값이 max_index 와 비교해서 더 큰 경우 새로운 값을 갱신해주면 최대 공통되는 부분을 파악할 수 있다.
• 파악하고 난 후 정답의 경우 index 로 접근했기 때문에 +1 을 해주면 되므로 max_index + 1 한 값을 기존의 열의 개수에서 제거해주면 된다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 정렬