[Python]백준_25643 : 문자열 탑 쌓기

출처

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

---

문제

인경이는 $N$개의 문자열을 쌓아서 문자열 탑을 완성하려고 한다. 탑을 완성하기 위해서는 모든 문자열을 아래에서부터 순서대로 쌓아 올려야 한다.

인경이는 문자열 탑의 꼭대기에 다음 순서의 문자열을 쌓을 수 있다. 단, 탑을 튼튼하게 만들기 위해서 탑의 꼭대기에 위치한 문자열과 새로 쌓으려는 문자열이 둘이 겹치는 부분이 완전히 동일하게 쌓아야 한다. 가장 첫 문자열인 경우는 바닥에 아무렇게나 쌓을 수 있다.

예를 들어, abc 위에 cab 를 쌓는다고 할 때, 일부가 겹치게 쌓는 경우의 수는 위와 같이 $5$개가 있다. 그 중에서 abc와 cab가 겹치는 부분이 완전히 동일한 경우만 쌓을 수 있다.

인경이가 문자열을 잘 쌓는다면 $N$개의 문자열을 순서대로 쌓아서 문자열 탑을 완성하는 것이 가능할까?

---

입력

첫째 줄에 주어지는 문자열의 개수 $N(1\le N \le 100)$과 문자열의 길이 $M(1\le M \le 100)$이 주어진다.

둘째 줄부터 $N$개의 줄에 $s_1, s_2, ... ,s_N$이 주어진다. $s_i$는 $i$번째 문자열을 의미한다. 주어지는 모든 문자열은 길이가 $M$이며 알파벳 소문자로만 이루어져 있다.

---

출력

모든 문자열을 순서대로 쌓아서 탑을 완성할 수 있다면 1 을 그렇지 않다면 0 을 출력한다.

---

예제 입출력

---

알고리즘 분류

• 문자열
• 브루트포스 알고리즘

---

➡️코드(⭕)

n, m = map(int, input().split())

str = []

for _ in range(n):
    str.append(input())

for i in range(n-1):
    str1 = str[i]
    str2 = str[i+1]

    check = False

    for j in range(1, m+1):
        if str1[m-j:] == str2[:j]:
            check = True
            break

        if str1[:j] == str2[m-j:]:
            check = True
            break

    if check == False:
        print(0)
        exit(0)

print(1)

---

➡️코드 분석

1. 문자열의 개수 n과 문자열의 길이 m을 입력받는다.

2. str 리스트에 n개의 문자열을 입력받아 넣어준다.

3. i는 0부터 n-2까지 반복하여 str1에는 str의 첫 번째 요소, str2에는 str의 두 번째 요소 … 을 각각 넣어준다.

4. 문자열 탑을 쌓을 수 있는지 체크하는 check 변수의 초깃값을 False로 설정한다.

5. 그 다음 for문은 str1과 str2의 요소를 각각 끝과 처음부터 비교한 후 모든 문자열을 비교했으면 다시 각각 처음과 끝부터 비교하는 과정이다.

6. 문자열의 길이만큼 반복하고 난 뒤의 check가 여전히 False라면 현재의 str1과 str2는 겹치는 부분이 없다는 것이므로 0을 출력하고 프로그램을 종료한다.

7. 모든 str1과 str2의 check가 False가 된 적이 없다면 1을 출력한다.

---

<코드 분석 5번에 대한 설명>

j는 1부터 m까지 반복하는데,
예를 들어, m=3이고 str1 = ’acb’와 str2 = ’bac’를 비교하려고 한다.

그럼 j=1일 때,

str1[3-1:] == str2[:1] → ‘b’ == ‘b’로 str1의 끝 문자와 str2의 처음 문자를 비교한다.

str1[:1] == str2[3-1:] → ‘a’ == ‘c’로 str1의 처음 문자와 str의 끝 문자를 비교한다.

j=2일 때,

str1[3-2:] == str2[:2] → ‘cb’ == ‘ba’로 str1의 끝 두 문자와 str2의 처음 두 문자를 비교한다.

str1[:2] == str2[3-2:] → ‘ac’ == ‘ac’로 str1의 처음 두 문자와 str2의 끝 두 문자를 비교한다.

j=3일 때,

str1[3-3:] == str2[:3] → ‘acb’ == ‘bac’로 str1과 str2의 모든 문자를 비교한다.

밑의 if문도 마찬가지로 모든 문자를 비교한다.

따라서 식을 만들어보면,

• 끝에서 부터 시작해서 처음 문자까지 하나씩 늘려가며 비교해 주려면

  배열[배열 길이 - (1부터 배열 길이까지):]

  str1[3-(1, 2, 3):] → b / cb / acb

  str2[3-(1, 2, 3):] → c / ac / bac
  

• 처음부터 끝 문자까지 하나씩 늘려가며 비교해 주려면

  배열[:(1부터 배열 길이까지)]

  str2[:(1, 2, 3)] → b / ba / bac

  str1[:(1, 2, 3)] → a / ac / acb

---

➡️end

코드는 검색을 통해 다른 분의 것을 참고하였다. 처음에 이해가 안되서 코드 분석을 열심히 하다보니 정말 힘들었지만 완전히 이해가 되었다!