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

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

2866번: 문자열 잘라내기

---

---

문제 분석

R개의 행과 C개의 열로 이루어진 테이블에서 열을 기준으로 단어를 만들어 총 R의 길이를 갖는 C개의 단어를 만든 후 단어들의 중복 여부를 확인한다.

 

처음에는 동일한 문자열이 존재하지 않는 입력이 주어지고 다음 연산부터는 가장 위의 행을 지운, 즉 단어의 첫 번째 문자를 없앤 단어들의 중복 여부를 판단한다.

단어들 중 중복이 없다면 count를 1 증가, 중복이 있다면 반복을 멈추고 count를 출력 후 프로그램 종료

 

리스트와 셋을 사용하여 단어를 저장하고 셋으로 중복을 제거해 길이를 비교해주면 되겠다고 생각했다.

반복을 돌면서 단어의 첫 번째 문자를 지워야 하기 때문에 list의 pop() 혹은 deque의 popleft()를 생각했었지만 셋으로 변환하기에 복잡함이 있어 문자열 슬라이싱으로 구현하기로 했다.

 

문자열 슬라이싱을 하기 위해서는 우선 단어를 뒤집어야겠다고 판단했고

입력을 받은 뒤 다시 반복문을 실행하여 리스트에 단어를 뒤에서부터 누적해 C개의 단어 문자열을 리스트 안에 넣고자 했다.

 

temp = []
arr = ["" for _ in range(c)]

for _ in range(r):
    temp.append(list(input()))

for i in range(r - 1, -1, -1):
    for j in range(c):
        arr[j] += temp[i][j]

우선 temp라는 리스트에 R개의 행의 문자열을 모두 리스트로 변환하여 2차원 리스트 형태로 만든다.

 

그 후 temp를 역순으로 돌면서 C개의 단어를 각 빈 문자열에 추가하며 단어를 완성시킨다.

이렇게 코드를 진행하면 예제에서 입력받은 문자열들을 C개의 거꾸로 된 문자열들이 arr에 저장된다.

예제 입력 1 => arr 출력

그 후 가장 위의 행을 지우는 과정에서는 모든 행이 지워지는 R번을 반복하고,

단어의 맨 뒤를 지우는 [:-1]을 이용하여 원래 지우고자 했던 맨 첫 문자를 지우는 연산을 반복한다.

 

for i in range(r):
    for j in range(c):
        arr[j] = arr[j][:-1]

 

이때 가장 중요한 셋을 사용하여 단어들의 중복 여부를 판단하기 위해 R번 반복의 시작에서 셋을 정의한 뒤 슬라이싱 후 셋에 문자열들을 추가한다.

그 후 원래 저장된 문자열들의 리스트와 셋의 길이를 비교하여

길이가 같다면 중복이 없다는 것이므로 count를 늘렸고, 길이가 같지 않다면 종료 후 count를 출력하는 분기를 진행한다.

 

for i in range(r):
    set_arr = set()

    for j in range(c):
        arr[j] = arr[j][:-1]

        set_arr.add(arr[j])

    if len(set_arr) == len(arr):
        cnt += 1
    else:
        break

print(cnt)

---

코드

r, c = map(int, input().split())

temp = []
arr = ["" for _ in range(c)]

for _ in range(r):
    temp.append(list(input()))

for i in range(r - 1, -1, -1):
    for j in range(c):
        arr[j] += temp[i][j]

cnt = 0

for i in range(r):
    set_arr = set()

    for j in range(c):
        arr[j] = arr[j][:-1]

        set_arr.add(arr[j])

    if len(set_arr) == len(arr):
        cnt += 1
    else:
        break

print(cnt)