[백준] 20528 - 끝말잇기: Good Bye, BOJ 2020! A

Good Bye, BOJ 2020! - A번

 

문제 ( www.acmicpc.net/problem/20528 )

욱제는 준원이랑 끝말잇기를 하고 있다. 준원이가 시작하자마자 '스트론튬'을 외쳐서 욱제는 피가 거꾸로 솟았다~ 솟으면 백두산~ 백두산은 높아~ 높으면 비행기~ 비행기는 빨라~ 빠르면 기차~ 기차에 타고 내릴 때에는 코로나 바이러스 감염증 예방을 위하여 마스크를 착용하여 주시길 당부 드립니다.

준원이와의 끝말잇기 대결에서 패배한 욱제는 새로운 게임을 제안했다. 바로 팰린드롬 문자열만 사용할 수 있는 팰린드롬 끝말잇기이다! 욱제와 준원이는 총 N개의 팰린드롬 문자열 S1,⋯,SN을 알고 있다. 이 둘이 알고 있는 팰린드롬 문자열을 남김 없이 모두 사용했을 때, 끝말잇기를 할 수 있는지 알아보자. 문자열을 사용하는 순서는 상관 없다.

"리효리", "찰진 의사의 진찰", "탄도유도탄"과 같이 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 팰린드롬 문자열이라고 부른다. 다시 말해, 길이 M짜리 문자열 T에 대해, T[i]=T[M−i+1] (1≤ i ≤M)이면 T는 팰린드롬 문자열이다.

N개의 팰린드롬 문자열 P1,⋯,PN에 대해, Pi의 마지막 문자와 Pi+1의 첫 문자가 같으면 끝말잇기를 할 수 있다고 정의한다. (1≤i<N)

 

입력 

첫째 줄에 문자열의 개수 N이 주어진다.

둘째 줄에 N개의 팰린드롬 문자열 S1,⋯,SN이 하나의 공백을 사이에 두고 주어진다.

 

출력

주어진 팰린드롬 문자열을 모두 사용했을 때 끝말잇기를 할 수 있으면 1, 그렇지 않다면 0을 출력한다.

 

예제

3

pqqp pqpqp pbbbp

1

 

3

aba c dd

0

 

---

Good Bye, BOJ 2020 풀이에서 알려주신 방법들

---

나의 코드

import sys

N = int(sys.stdin.readline())
strs = map(str, sys.stdin.readline().strip().split(" "))
strSet = set()

for str in strs:
    strSet.add(str[0])
    strSet.add(str[len(str)-1])

print(1 if len(strSet) == 1 else 0)

• 각 문자열들의 첫 문자와 마지막 문자를  set 에 추가하고, set의 size가 1인지 판단한다.

💫 BoJ 당시에는 permutation으로 접근하는 바람에 시간 초과가 발생하여 성공하지 못했다.