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. 문제를 풀고난 후 생각

 

• 입력으로 들어온 문자열을 제일 끝 문자열부터 더해가며 저장한다.

alfa
beta
zeta

• 위의 예시의 경우 "aaa", "zba", "eel", "ttf" 의 문자를 새로운 리스트에 저장을 한다.
• 이후 정렬을 통해서 "aaa", "eel", "ttf", "zba" 로 정렬을 해준후 1번 인덱스 부터 비교를 시작한다.

• 위 두 문자를 비교해서 같은 경우 index 값을 1씩 증가시켜가며 다음 문자를 비교한다.

• 문자가 같다는 가정하에 다음 문자를 비교하는 방식을 예시를 들었다. 이렇게 비교해가며 다른 문자가 나온 경우 나왔을때 index 값을 비교해 최대 index를 저장해준다.
• index 값이 열의 끝까지 도달시킨 후 저장시킨 최대 인덱스 + 1 한 값을 행의 개수에서 제외시켜주면 된다.

 

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

 

• 정렬