백준 20528번 문제 링크
문제 이름 : 끝말잇기
주 언어 : Python
태그 : 문자열 / 애드 혹
solved.ac 등급 : Bronze II (2023/05/17 확인)
문제 보기
문제 :
욱제는 준원이랑 끝말잇기를 하고 있다. 준원이가 시작하자마자 '스트론튬'을 외쳐서 욱제는 피가 거꾸로 솟았다~ 솟으면 백두산~ 백두산은 높아~ 높으면 비행기~ 비행기는 빨라~ 빠르면 기차~ 기차에 타고 내릴 때에는 코로나 바이러스 감염증 예방을 위하여 마스크를 착용하여 주시길 당부 드립니다.
준원이와의 끝말잇기 대결에서 패배한 욱제는 새로운 게임을 제안했다. 바로 팰린드롬 문자열만 사용할 수 있는 팰린드롬 끝말잇기이다! 욱제와 준원이는 총 $N$개의 팰린드롬 문자열 $S_1, \cdots, S_N$을 알고 있다. 이 둘이 알고 있는 팰린드롬 문자열을 남김 없이 모두 사용했을 때, 끝말잇기를 할 수 있는지 알아보자. 문자열을 사용하는 순서는 상관 없다.
"리효리", "찰진 의사의 진찰", "탄도유도탄"과 같이 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 팰린드롬 문자열이라고 부른다. 다시 말해, 길이 $M$짜리 문자열 $T$에 대해, $T[i] = T[M-i+1]$ ($1 \le i \le M$)이면 $T$는 팰린드롬 문자열이다.
$N$개의 팰린드롬 문자열 $P_1, \cdots, P_N$에 대해, $P_i$의 마지막 문자와 $P_{i+1}$의 첫 문자가 같으면 끝말잇기를 할 수 있다고 정의한다. ($1 \le i < N$)
입력 :
첫째 줄에 문자열의 개수 $N$이 주어진다.
둘째 줄에 $N$개의 팰린드롬 문자열 $S_1, \cdots, S_N$이 하나의 공백을 사이에 두고 주어진다.
출력 :
주어진 팰린드롬 문자열을 모두 사용했을 때 끝말잇기를 할 수 있으면 1, 그렇지 않다면 0을 출력한다.
만약 aba, ababa가 있다면 a끼리 만날 수 있습니다.
각 문자열이 모두 팰린드롬이므로, "A"로 시작한 것은 "A"로 끝나게 됩니다.
따라서 첫번째 문자열이 "A"로 시작하면, "A"로 끝나고, 다음 문자열도 "A"로 시작해야하고, 그렇게 되면 "A"로 끝나고...
따라서 모든 문자열의 첫번째 글자가 모두 동일해야한다는 것을 알 수 있습니다.
이제 "모든 문자열의 첫 글자가 동일해야한다"를 어떻게 구현할 지만 생각하면 됩니다.
1번 문자열의 0번째 글자와 2번 문자열의 0번째 글자가 동일하고, 1번 문자열의 0번째 글자와 3번 문자열의 0번째 글자가 동일하고, ...를 만족 시키면 모든 문자열의 각 0번째 문자가 동일하다는 것을 알 수 있습니다.
혹은 파이썬의 자료형 중 중복을 허용하지 않는 set 자료형을 사용하여, 모든 문자열의 0번째 글자를 넣고 길이가 1이라면 1을 출력하는 방식도 가능합니다.
-번째 푼 문제 (2022/--/--)