[SWEA] 1216. [S/W 문제해결 기본] 3일차 - 회문2 (Python/D3)

---

[문제 링크] 👇

SW Expert Academy

 

---

풀이

회문 길이 계산

큰 길이부터 줄여가면서 문자열을 추출하고 회문 여부를 검사해 첫 번째 회문을 찾으면 해당 길이를 반환한다.

 

 

행 열 변환 방법 - zip()

new_board = [list(i) for i in zip(*board)]

 

 

Solution

def palindrome(board):
    length, max_len = 0, 0
    for i in range(100):
        for j in range(100):
            for k in range(100):
                word_slice = board[i][j:j + k]

                if word_slice == word_slice[::-1]:
                    length = len(word_slice)

                if max_len < length:
                    max_len = length
    return max_len

for _ in range(10):
    test_case = int(input())
    board = [input().strip() for _ in range(100)]
    row_len = palindrome(board)
    #행 열 변환
    new_board = [list(i) for i in zip(*board)]
    col_len = palindrome(new_board)
    if row_len > col_len:
        result = row_len
    else:
        result = col_len

    print(f"#{test_case} {result}")

 

위 코드의 구조는 맞는 편이지만, 현재 코드에서 몇 가지 성능 문제와 잠재적 오류가 발생할 수 있다. 코드가 100x100 배열을 대상으로 모든 부분 문자열을 검사하려고 하기 때문에, 최악의 경우 상당히 느려질 수 있다. 다음은 문제를 최적화하고 안정적으로 수정하기 위한 몇 가지 개선 사항이다.

 

개선 사항

• 불필요한 반복문 제거
  • for k in range(100):는 board[i][j:j + k]로 계속해서 부분 문자열을 추출하지만, 이 방식을 유지하면 모든 부분 문자열을 매번 다시 검사하므로 효율성이 떨어집니다.
  • 대신, 길이가 큰 부분 문자열부터 검사하여 처음으로 회문을 발견하면 그 길이가 최대 길이가 됩니다. 이를 위해 for k in range(100, 0, -1)로 수정하여 큰 길이부터 줄여가며 회문을 찾으면, 첫 회문을 찾을 때 바로 그 길이가 최댓값이 됩니다.
• length 변수의 불필요한 업데이트
  • length는 max_len이 갱신될 때만 필요하기 때문에, 조건문을 간소화하여 코드 가독성을 높일 수 있습니다.
• 사소한 논리 개선
  • 결과를 row_len과 col_len 중에서 더 큰 값으로 바로 할당하도록 변경할 수 있습니다.

 

최적화된 코드

def palindrome(board):
    max_len = 0
    for i in range(100):
        for j in range(100):
            for k in range(100, 0, -1): #큰 길이부터 시작하여 검사
                if j + k <= 100:
                    word_slice = board[i][j:j + k]

                    if word_slice == word_slice[::-1]: # 회문 확인
                        max_len = max(max_len, k) # 최대 길이 갱신
                        break # 최대 길이 찾았으므로 더 짧은 길이는 검사하지 않음
    return max_len

for _ in range(10):
    test_case = int(input())
    board = [input().strip() for _ in range(100)]
    row_len = palindrome(board)
    #행 열 변환
    new_board = [list(i) for i in zip(*board)]
    col_len = palindrome(new_board)
    result = max(row_len, col_len)
    print(f"#{test_case} {result}")

 

 

👩‍💻 회고

저번에 회문 1 문제처럼 또 제대로 해결 못할까봐 걱정했는데 갑자기 문득 행 열을 변환하는 메서드가 있지 않을까 하고 찾아봤는데 정말 있었다. 덕분에 어렵지 않게 해결했다.!! 

고려해야했던 건 회문의 길이가 정해져있지 않아서 일일이 길이를 조정해가며 모두 검사 했어야 했다는 점이다. 3중 for문까지 돌려서 시간복잡도가 커졌지만 코드를 최적화하니깐 기존보다 절반이나 작아졌다. 앞으론 시간복잡도도 고려해가면서 코드를 짜는 것이 좋겠다.

 

---