BOJ_25643 : 문자열 탑 쌓기

👉 문제링크

25643번: 문자열 탑 쌓기

---

---

🔸 문제 분석 🔸

• 새로 들어온 문자열이 이전 문자열에 결합이 되는지 확인하며 전부 결함 가능하면 1, 아니라면 0을 출력한다.
  • 문자열 블록을 끼는 경우의 수는 3가지이다.
    1. 완전히 같은 문자열로 모든 칸을 끼움
    2. 새로 들어온 문자열 블록이 왼쪽으로 튀어나옴
    3. 새로 들어온 문자열 블록이 오른쪽으로 튀어나옴
  • 두 문자열 블록의 겹치는 부분의 길이를 1부터 m까지 키워가며 결합이 되는 순간이 올 때까지 계산한다.

🔸 코드 🔸

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

before = input()

for i in range(n-1):
    new = input()

    flag = True
    for j in range(1,m+1):
        if new[m-j:] == before[:j] or new[:j] == before[m-j:]:
            break
    else:
        flag = False

    if flag:
        before = new
    else:
        print(0)
        break
else:
    print(1)

🔸 코드 해석 🔸

• 이전 문자열 before와 새 문자열 new를 비교한다.
• j를 1부터 m까지 증가시키며 두 문자열이 결합이 가능한지 확인한다.
  • 가능한 경우가 나오면 break
  • 끝까지 가능한 경우가 안나오면 for-else문으로 들어가 flag를 False로 바꾼다.
• flag가 True인 경우엔 before에 new문자열을 저장하고 반복을 계속한다.
• flag가 False이면 0을 출력하고 종료한다.
• 모든 문자열을 검사했는데 flag가 False인 경우가 없었다면 1을 출력한다.

---

🔸 end 🔸

• 블록 그림설명이 장황해서 조금 겁을 먹었는데, 생각보다 간단한 알고리즘이었다.