[맛있는물회] <SWEA알고리즘> 4861번 "회문"

문제 조건

---

 

Input

---

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50

다음 줄부터 테스트케이스의 첫 줄에 N과 M이 주어진다. 10≤N≤100, 5≤M≤N

다음 줄부터 N개의 글자를 가진 N개의 줄이 주어진다.

 

Output

---

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

생각한 아이디어

---

상당히 고전한 문제이다. 

처음에는 문제를 제대로 안읽어서 N * M의 문자열인 줄 알아서 잘못접근했고, 두번째는 무조건 회문이 0 - N 의 범위인 줄 알았는데 중간에 있을 수도 있었다.. ㅎㅎㅎ

상당히 힘들었다.

그리고 파이썬의 문자열 Reverse 바로 시키는 [::-1]의 방법을 몰랐기 때문에 푼 과정에서 오류가 있었나 보다. 내가 푼 방식으론 Test case 9개만 맞다고 나와서 틀렸었다.

파이썬의 Reverse함수를 사용해보니 답이 맞다고 나왔다. 파이썬은 아주 간단하지만 강한 언어인 듯하다.

 

가로 부분은 아주 간단하게 입력받을 때 마다 범위를 지정해서 Reverse한 값과 비교해주며 진행한다.

세로 부분은 한 단계를 더 거쳐야해서 조금 복잡했다.

가로 부분의 문자열을 바탕으로 세로 방향의 문자를 만든다. 이 문자를 다시 세로 문자열 리스트에 하나씩 추가하며 가로 방식과 동일하게 Reverse와 비교하며 진행하는 방식을 사용했다.

 

소스코드

T = int(input())
for TC in range(1, T+1):
    arr = list()
    N, M = map(int,input().split())

    for i in range (N):#가로
        string = str(input())
        arr.append(string)
        for j in range(0,N-M+1):
            end = M+j
            if string[j:end] == string[j:end][::-1]:
                ans = string[j:end]
    #세로
    vertArr = list()

    for j in range(0,N):
        vertStr = str()
        vert = list()
        for i in range(0,N):
            vert.append(arr[i][j])
        vertStr = ''.join(vert)
        vertArr.append(vertStr)
        for k in range(0,N-M+2):
            end = M+k
            if vertStr[k:end] == vertStr[k:end][::-1] :
                ans = vertStr[k:end]
    
    print("#%d %s" %(TC,ans))

 

*파이썬 문법 정리

- Array[::-1]로 아주 간단하게 문자열(리스트)의 Reverse를 알 수 있다. 또한 범위를 넣고 싶다면 Array[3:6][::-1]로 하면 3:6의 범위를 Reverse시켜서 나타낼 수 있다.