[SWEA][S/W 문제해결 기본][Python] 1216 회문 2

[문제]

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AV6kld8aisgDFASb&contestProbId=AV14Rq5aABUCFAYi&probBoxId=AV-4MojKLNADFATz&type=PROBLEM&problemBoxTitle=%5BD2%7ED3+%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4%5D+%EA%B8%B0%EC%B4%88+%EB%8B%A4%EC%A7%80%EA%B8%B0+Part4&problemBoxCnt=14

SW Expert Academy

 

[참고한 자료]

스스로 푼 코드는 내가 테스트케이스를 돌렸을 때는 정답이 옳게 나왔으나, Pass를 하지 못했다. 

다른 사람들이 푼 코드를 참고해도 이해가 되지 않았는데, 이 유튜브를 통해 이해를 할 수 있었다!

코드 자세한 설명은 영상에서 확인하길 바란다. 

 

https://youtu.be/nAA_3fbwsZw?si=lQM4ZkouprNn8M-2

 

[배운점]

arr2 = list(zip(*arr))
arr2 = [''.join(x) for x in zip(*arr)]

zip 함수 
*arr : arr 을 풀어서 각각의 행을 개별적 인자로 전달한다. 
zip(*arr) : asterisk(*)를 사용하여 인자를 언팩(unpack)하는 기법을 활용한다.
- 각 행의 동일한 위치에 있는 요소들을 묶어 튜플로 반환한다. 
list(zip(*arr)) : list() 함수를 사용하여 이를 리스트로 변환한다. 

ex) arr = [[1,2,3], [4,5,6]] >> [(1,4), (2,5), (3,6)]

[' '.join(x) for x in zip(*arr)] 실행 시 
ex) [14, 25, 36] 

>> 결과적으로, arr2는 arr을 전치하여 얻은 행렬의 각 열을 하나의 문자열로 이어붙인 리스트가 된다. 

 

[코드]

아이디어는 회문 최대 길이부터 하나씩 감소하며 확인하는 것이다. 열로 만들어지는 회문은 전치하여 행으로 변환해준다. 

1번 코드는 전체 회문을 같은지 확인하는 방법으로 시간복잡도가 높다. 

2번 코드는 회문 절반을 잘라서 같은지 확인하는 것이다.

 

[1번 코드]

#1번 방법
def is_pal(arr, length):
    for lst in arr:
        for i in range(N - length + 1):
            if lst[i:i + length] == lst[i:i + length][::-1]: #회문 전체 확인
                return True
    return False

for t in range(1, 11):
    tc = input()
    N = 100
    arr1 = [input() for _ in range(N)]
    arr2 = [''.join(x) for x in zip(*arr1)] #arr 열을 행으로 전치 

    for length in range(N, 1, -1):
        if is_pal(arr1, length) or is_pal(arr2, length):
            break

    print(f'#{tc} {length}')

 

[2번 코드]

#2번 방법
def is_pal_idx(arr, length):
    for lst in arr:
        for i in range(N-length+1):
            for j in range(length//2):  #A B / B A 회문을 반으로 나누어 같은지 확인
                if lst[i+j] != lst[i+length-1-j]:
                    break
            else:
                return True
    return False


for t in range(1, 11):
    tc = input()
    N = 100
    arr1 = [input() for _ in range(N)]
    arr2 = [''.join(x) for x in zip(*arr1)]

    for length in range(N, 1, -1):
        if is_pal_idx(arr1, length) or is_pal_idx(arr2, length):
            break

    print(f'#{tc} {length}')