[SWEA] #4672 수진이의 팰린드롬

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWRKNev6fqYDFAV8

계획

1. 처음에는 비트 연산을 이용해서 부분집합을 만들고 연속 여부를 flag 변수로 확인한 뒤, is_palindrome() 함수에서 해당 부분집합에 대해 요소들의 순서는 상관없이 팰린드롬인지 체크하려고 했는데 왠지 너무 복잡해지는 것 같아서 방법 변경
2. 문제를 다시 읽어본 뒤 부분 문자열, 즉 연속하는 것만 확인해야 하고 단어 W 그 자체에 대해서는 순서 변경이 가능함을 확인했음. 그래서 단어 길이만큼의 길이를 가진 reorganized 리스트를 만들어서 i번째에 'a'가 나왔으면 -1 - i 위치에 'a'를 넣어주도록 코드를 짰으나 오답(시간 초과X)이 떴음
3. 약 3시간을 봤는데 문제 감을 못잡고 있다는 생각에 다른 사람 풀이 참고 -> sorted() 함수를 이용해서 풀이

코드

T = int(input())
for tc in range(1, T+1):
    word = input()
    N = len(word)
    result = 0
    sorted_word = sorted(word)

    for i in range(N):
        for j in range(i + 1, N + 1):
            if sorted_word[i:j] == sorted_word[i:j][::-1]:
                result += 1

    print('#{} {}'.format(tc, result))

풀이 방법

sorted() 메서드를 이용하면 문자열 'abcabc'를 'aabbcc' 형태로 정렬할 수 있다. 이렇게 정렬해서 팰린드롬을 카운트 했을 때 팰린드롬의 최댓값을 찾을 수 있다. 처음에 나는 'abcabc'를 'abccba'로 바꿀 방법만 생각했었는데 이렇게 풀 경우 엣지 케이스가 생긴다.
ex) 만약 한 문자가 3번 이상 등장한다면 처음에는 'a@@@@@' 두 번째 등장했을 때에는 'a@@@@a' 세 번째 등장했을 때는 'aa@@@a'의 형태로 들어가게 되는데 이 경우 팰린드롬의 최댓값을 정확히 셀 수 없음