[파이썬] 4861. 회문

swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

ABBA처럼 어느 방향에서 읽어도 같은 문자열을 회문이라 한다. NxN 크기의 글자판에서 길이가 M인 회문을 찾아 출력하는 프로그램을 만드시오.

회문은 1개가 존재하는데, 가로 뿐만 아니라 세로로 찾아질 수도 있다.
 

예를 들어 N=10, M=10 일 때, 다음과 같이 회문을 찾을 수 있다.
 

G	O	F	F	A	K	W	F	S	M
O	Y	E	C	R	S	L	D	L	Q
U	J	A	J	Q	V	S	Y	Y	C
J	A	E	Z	N	N	Z	E	A	J
W	J	A	K	C	G	S	G	C	F
Q	K	U	D	G	A	T	D	Q	L
O	K	G	P	F	P	Y	R	K	Q
T	D	C	X	B	M	Q	T	I	O
U	N	A	D	R	P	N	E	T	Z
Z	A	T	W	D	E	K	D	Q	F

  

[입력]
 

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

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

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

 

[출력]
 

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

입력

출력

3 10 10 GOFFAKWFSM OYECRSLDLQ UJAJQVSYYC JAEZNNZEAJ WJAKCGSGCF QKUDGATDQL OKGPFPYRKQ TDCXBMQTIO UNADRPNETZ ZATWDEKDQF 10 10 WPMACSIBIK STWASDCOBQ AMOUENCSOG XTIIGBLRCZ WXVSWXYYVU CJVAHRZZEM NDIEBIIMTX UOOGPQCBIW OWWATKUEUY FTMERSSANL 20 13 ECFQBKSYBBOSZQSFBXKI VBOAIDLYEXYMNGLLIOPP AIZMTVJBZAWSJEIGAKWB CABLQKMRFNBINNZSOGNT NQLMHYUMBOCSZWIOBINM QJZQPSOMNQELBPLVXNRN RHMDWPBHDAMWROUFTPYH FNERUGIFZNLJSSATGFHF TUIAXPMHFKDLQLNYQBPW OPIRADJURRDLTDKZGOGA JHYXHBQTLMMHOOOHMMLT XXCNJGTXXKUCVOUYNXZR RMWTQQFHZUIGCJBASNOX CVODFKWMJSGMFTCSLLWO EJISQCXLNQHEIXXZSGKG KGVFJLNNBTVXJLFXPOZA YUNDJDSSOPRVSLLHGKGZ OZVTWRYWRFIAIPEYRFFG ERAPUWPSHHKSWCTBAPXR FIKQJTQDYLGMMWMEGRUZ

#1 JAEZNNZEAJ #2 MWOIVVIOWM #3 TLMMHOOOHMMLT

 

🔑 나의 풀이

 

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N, M=map(int, input().split())		# N= 글자 수 = 줄, M=회문의 길이
    lst=list()
    
    # 가로로 저장
    for i in range(N):
        lst.append(''.join(input()))
	
    # 세로로 저장
    c_lst=list()
    for c in range(N):			# 행
        copy=''
        for r in range(N):		# 열
            copy+=lst[r][c]		# 열 순회
        c_lst.append(copy)
     
    all_lst=lst+c_lst
    for x in all_lst:	# 가로, 세로 방향으로 모두 탐색
        i=0
        for y in range(N-M+1):
            if x[i:i+M] == x[i:i+M][::-1]:		# 회문이면 출력
                print(f"#{test_case} {x[i:i+M]}")
                break
            i+=1

 

가로, 세로 방향으로 문자열을 저장.

M의 길이만큼 리스트를 슬라이싱하고 회문이면 출력한다.

[::-1]은 리스트를 거꾸로 뒤집는다.

print(f"#{test_case} {''.join(lst[i])}")

print(f'#{test_case} {''.join(lst[i])}')는 잘못됨.

헐.. 지금까지 가로 또는 세로길이만큼 회문이 있는줄 알았는데 테스트케이스 3번은 예외네..

긴 문장 속에 숨어있네.

문제를 잘못 읽어서 글자 수가 N, 줄이 M인줄;

다시 코드를 짜서 완성 ㅎㅎ

 

👓 다른사람 풀이

 

T = int(input())

for t_idx in range(1, T+1):
    N, M = list(map(int, input().split()))		# N= 글자 수 = 줄, M=회문의 길이

    row_list = []
    for _ in range(N):
        row_list.append(input())
    
    col_list = []
    for c_idx in range(N):
        tmp = ''
        for r_idx in range(N):
            tmp += row_list[r_idx][c_idx]
        col_list.append(tmp)

    total_list = row_list + col_list
    for row in total_list:
        for idx in range(N):
            if M+idx > N:
                break
            s = row[idx:M+idx]
            if s == s[::-1]:
                print(f'#{t_idx} {s}')
                break

 

나랑 알고리즘이 같다.

N번 반복하면서 회문의 길이M+인덱스idx가 N보다 크면 break한다.

s에 회문의 길이만큼 값을 넣고 뒤집은 값s[::-1]과 비교해서 true면 출력하고 반복문을 끝낸다. 

 

def solution(input_list, m):
    n = len(input_list)
    count = n - m + 1
    for i in range(n):
        for c in range(count):
            j = 0
            while j < (m // 2):
                if input_list[i][c+j] != input_list[i][m+c-j-1]:
                    break
                j += 1
            if j == (m // 2):
                return "".join(input_list[i][c:c+m])

    for i in range(n):
        for c in range(count):
            j = 0
            result = []
            while j < (m // 2):
                if input_list[c+j][i] != input_list[m+c-j-1][i]:
                    break
                result.append(input_list[c+j][i])
                j += 1
            if j == m // 2:
                if m % 2:
                    middle = [input_list[c+j][i]]
                    result += middle + result[::-1]
                else:
                    result += result[::-1]
                return "".join(result)

def main():
    test_cases = int(input())
    for test_case in range(test_cases):
        input_list = []
        n, m = map(int, input().split())
        for _ in range(n):
            input_list.append(input())
        print(f"#{test_case + 1} {solution(input_list, m)}")


if __name__ == '__main__':
    main()

 

좀 복잡해보인다.