회문(回文, palindrome) 알고리즘 구현 by Python

 

[문제]  회문(回文, palindrome)은 어떤 방향으로 읽어도 같은 문자열을 말한다. 예를 들면 “여보 안경 안 보여”, “다 큰 도라지라도 큰다.”, “아들딸이 다 컸다 이 딸들아”은 잘 알려진 회문이다. 이번에는 영문 소문자 문자열만 다룬다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체로는 회문이 아니지만 한 문자를 제거하여 회문으로 만들 수 있으면 이런 문자열을 “유사회문”(quasi palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하면 회문 ‘summus’이 되므로 이것은 유사회문이다. 여러분은 제시된 문자열이 그 자체로 회문인지, 또는 “유사회문”인지, 아니면 그 외 일반 문자열인지를 판단해야 한다. 

     

[입출력]  입력파일 palin.inp의 첫줄에는 정수 ,  이 주어진다.  그 다음 이러지는 N개의 각 줄에는  소문자로 구성된 문자열이 하나씩 주어진다.  여러분은 이 문자열이 그 자체로 회문인지, 또는 ‘유사회문’인지,  또는 회문도 유사회문도 아닌지를 판명하여 그 결과를 1, 2, 3으로 구분하여 출력파일 palin.out에 순서대로 출력해야 한다. 입력 문자열의 길이 의 범위는  이다. 

 

[예제]

palin.inp	palin.out
4 bookoob summuus ixiyi oooooooooo	1 // 회문 2 // 유사회문 3 // 회문이 아님 1 // 회문
7 cocococ cocoococ compupmocc veryvery veryxyrev verymxyrev vemryxmyrev	1 1 2 3 1 2 3

             

 

[제한조건]   프로그램 이름은 palin.{c, cpp, java, py}이다. 최대 허용 제출횟수는 15회, 각 데이터 당 제한시간은 1초이다. 과제 마감시간은 3월 8일(월요일) 저녁 10시이며, 제출은 5일 금요일부터 가능하다. ESPA에 연습용 데이터와 정답이 공개될 예정이므로 이것을 이용해서 입출력 등을 확인할 수 있다.     

            수강생들간 토론은 권장되지만 다른 사람의 코드를 무단으로 사용하면 관련된 학생들의 점수는 모두 '0'점 처리된다. 만일 다시 반복될 경우에는 F로 처리되며 관련된 학생들은 모두 학칙에 의하여 처벌을 받는다. 프로그램 표절 기준은 수업 시간에 설명된다. 그리고 과제나 강의에 대한 변경 사항이 있을 수 있으므로 매일 강의 사이트를 살펴보기를 권한다. 강의 참고자료는 일주일 전에 ESPA 자료실에 공개될 예정이므로 미리 출력하여 준비해야 한다. 

 

가장 베스트한 아래 코드와 같이 재귀함수를 통한 회문 판별이 베스트지만, 이렇게 저렇게 다른방법으로 구해보았다.

def palindrome(string: str) -> bool:
    if len(string) == 1 or len(string) == 0:
        return True
    
    if string[0] == string[-1]:
        return palindrome(string[1:-1])
    else:
        return False

 

알고리즘 연습 방법

1. 연습장과 펜을 준비하자.

2. 알고리즘 문제를 읽고 분석한 후에,

3. 간단하게 테스트용으로 매우 간단한 경우부터 복잡한 경우 순서대로 생각해보면서, 연습장과 펜을 이용하여 알고리즘을 생각해본다.

4. 가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어본다.

5. 코드화하기 위해, 데이터 구조 또는 사용할 변수를 정리하고,

6. 각 문장을 코드 레벨로 적는다.

7. 데이터 구조 또는 사용할 변수가 코드에 따라 어떻게 변하는지를 손으로 적으면서, 임의 데이터로 코드가 정상 동작하는지를 연습장과 펜으로 검증한다.

 

위 방법으로 앞으로 공부하면서 푼 알고리즘문제들을 나열해보자...!

 

시작해보즈아...

 

첫번째, 문자열의 대칭되는 기준점에서 좌측 우측을 나누어 회문인지 아닌지 판별하자.

 

두번째, 판별중 회문조건에 충족하지 못한다면, 문자열이 유사회문인지, 회문이 아닌지 판별하자.

 

큰 틀에서의 생각은 첫번째, 두번째와 같다. 5분정도 생각했을때 빈틈이 없어보인다!

 

우선, 입력파일을 알맞게 받아보자.

def takefile():
    f = open("./palin2.inp")
    inpFile = f.readlines()
    f.close()
    for i in range(len(inpFile)):
        if i == 0:
            pass
        else:
            inpFile[i] = inpFile[i].rstrip('\n') # 개행문자 제거
    del inpFile[0]
    return inpFile # string값만 있는 list로 return

inp 파일의 string들을 입맛에 맞게 바꾸어 주고,

 

 

아래 코드와 같이  문자열의 알파뱃들의 리스트에서 기준의 왼쪽 오른쪽을 반복문을 돌며 비교하고,

불일치 할경우 유사회문 판별 함수로 보낸다.

def isPalin(inpFile):
    ans = []
    for i in range(len(inpFile)): # string의 개수만큼 전체 반복
        inpString = list(inpFile[i]) # 각각의 string을 알파뱃하나씩 list로 치환
        for j in range(len(inpString) // 2): # string의 기준점을 기준으로 앞뒤 비교를 위해
            if inpString[j] == inpString[len(inpString) - 1 - j]: # 기준점 기준 앞뒤 비교 일치 경우
                if j == len(inpString) // 2 - 1: # string의 알파뱃 갯수만큼 반복문 돌았음을 판별
                    ans.append('1') # 회문 결정
            elif inpString[j] != inpString[len(inpString) - 1 - j]: # 기준점 기준 앞뒤 비교 불일치 경우 
                ans.append(isSimilarParlin(inpString, j)) # 유사회문, 회문아님 판별함수 실행
                break
    return ans

 

 

유사회문 판별 함수를 살펴보면,

아래와 같이 알파뱃배열 앞쪽 또는 뒷쪽의 문자열의 배열 원소 중 하나 건너뛸경우, 2가지로 나누어 유사회문, 회문아님을 나뉜다. 

def isSimilarParlin(inpString, index):
    if inpString[index+1] == inpString[len(inpString) - 1 - index]: # 알파뱃배열 앞쪽의 문자열중 하나 건너뛸경우
        for i in range(index, len(inpString) // 2): # 처음부터가 아닌 파라미터로 받은 인덱스부터 검사
            if inpString[i+1] == inpString[len(inpString) - 1 - i]:
                if i == len(inpString) // 2 - 1:
                    return '2'
            else:
                return '3'
    elif inpString[index] == inpString[len(inpString) - 2 - index]: # 알파뱃배열 뒷쪽의 문자열중 하나 건너뛸경우
        for i in range(index, len(inpString) // 2): # 처음부터가 아닌 파라미터로 받은 인덱스부터 검사
            if inpString[i] == inpString[len(inpString) - 2 - i]:
                if i == len(inpString)// 2 - 1:
                    return '2'
            else:
                return '3'
    else:
        return '3'

 

작성한 함수를 실행해보자.

ans = isPalin(takefile())
print(ans)
print("time :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간

 

위 문제중 문자열이 7개가 있는 예제를 기준으로 정상 작동함을 알 수 있다...

정상작동

이번문제에서 가장 까다로웠던 부분은 바로 '유사회문' 판단이였다. 

기준점 기준 좌측, 우측 중 하나의 알파뱃을 '제외'하고 회문이 된다면 유사회문이 되는데,

결국 불일치하는 부분을 한번뛰어넘고, 좌측또는 우측과 비교함으로써 유사회문을 판별하면 문제는 해결된다. (이생각을 하기 힘들었음 ㅜ)

 

 

개략적인 timeComplexity를 계산해보면, 앞선 문자열의 갯수는 상수이기에 논외하고, 결국 문자열의 알파뱃 갯수로 결정 되는데,

결국 문자열의 갯수 N으로 시간복잡도가 계산된다. ====> O(N)

 

코드가 조금 지저분해 보이고, 시간복잡도가 최선이 아닌거같은 느낌이 for문에서 강력히 나지만 ㅜㅜ

한문제 한문제 풀며 개선해 나가야겠다..