Today's Algoritm : 파이썬 알고리즘-11 (탐색)회문 문자열 검사

파이썬 알고리즘에 대해서 정리해볼 예정이다. 기본부터 탄탄히 만들어가보려고 적어가는 과정.

알고리즘을 짜는데는 오래 걸리는데 막상 코드를 짜면 이렇게 짧은가 싶다.

문제 출처는 아래 벨로그에서!

파이썬 알고리즘-11 (탐색)회문 문자열 검사

---

1. 문제

N개의 문자열 데이터를 입력받아 앞에서 읽을 때나 뒤에서 읽을 때나 같은 경우(회문 문자열)

이면 YES를 출력하고 회문 문자열이 아니면 NO를 출력하는 프로그램을 작성한다.

단 회문을 검사할 때 대소문자를 구분하지 않습니다.

​

▣ 입력설명

첫 줄에 정수 N(1<=N<=20)이 주어지고, 그 다음 줄부터 N개의 단어가 입력된다.

각 단어의 길이는 100을 넘지 않는다.

​

▣ 출력설명

각 줄에 해당 문자열의 결과를 YES 또는 NO로 출력한다.

​

▣ 입력예제 1

5

level

moon

abcba

soon

gooG

​

▣ 출력예제 1

#1 YES

#2 NO

#3 YES

#4 NO

#5 YES

---

2. 생각 과정

여기서 회문 문자열이란, 앞으로 읽으나 뒤로 읽으나 같은 문장이 나올때 회문 문자열이라고 한다!

문자열을 받아서 처음부터 대조하는 것은 시간 낭비가 아닐까 생각을 해보았다. 그래서 문자열의 중간을 찾은 후에 중간까지 1번 인덱스와 N번을 비교, 같다면 2번째 인덱스와 N-1번째 인덱스를 비교, 비교, 비교... 해서 문자열의 중간까지 간다면 Yes를 출력하도록 코드를 짜보면 어떨까 생각했다!

​

여기서 유의해서 봐야할 점은 대소문자를 구분하지 않는다는 것이다! 이건 검색해봐야겠다.

Python에서 대소 문자를 구분하지 않는 문자열 비교

 

찾아보니 파이썬 스러운 방법은 약 3가지의 방법이 존재했다.

1. lower() 함수로 소문자로 만든 후 대조

2. upper() 함수로 대문자로 만든 후 대조

3. casefold() 함수로 대조

가장 무난한 것은 1번과 2번이라고 생각했다.

​

간단하게 의사코드로 정리해보면

1. N개의 개수 입력 받기

2. 문자열 하나 입력받기 -> 소문자로 변환하기

2-1) len()로 길이 확인 후 문자열의 중간 찾기

2-2) for 문으로 반복하며 0~문자열 중간까지 반복하며 1번째와 N번째 ... 비교

2-3) 어느 하나라도 같지 않다면 바로 NO를 출력하고 break

2-4) 문자열 중간까지 대조해서 동일하다면 YES 출력하기

그럼 코드를 한번 짜보겠다!

​

3. 내 코드

n = int(input())

for test_case in range(1, n+1):
    my_str = input().lower()  // 소문자로 만들기
    length = int(len(my_str))  // 문자열 길이 저장
    mid = int(length / 2) if length % 2 == 0 else int(length / 2) + 1  // 문자열 중간 인덱스 확인

    for i in range(1, mid):  // 문자열 중간 인덱스까지 확인하여 작동시간 줄이기
        if my_str[i - 1] != my_str[length - i]:
            print("#{0} NO".format(test_case))
            break
        elif my_str[i - 1] == my_str[length - i]:
            if mid - 1 == i:
                print("#{0} YES".format(test_case))
            else:
                continue

​

4. 풀이 코드

# 일반적 풀이 

n=int(input())
for i in range(1, n+1):
    str=input()
    str=str.upper()
    for j in range(len(str)//2):
        if str[j]!=str[-1-j]:
            print("#%d NO" %i)
            break
        else:
            print("#%d YES" %i)
# 파이썬

n=int(input())
for i in range(n):
    str=input()
    str=str.upper()
    if str==str[::-1]:
        print("#%d YES" %i)
    else:
        print("#%d NO" %i)

---

5. 배운점

- 불필요하게 사용한 변수들이 많았다.

- 중간지점을 변수로 지정하는 것보다는 len()를 불러오는게 빠른건가 싶다

- 뒤에서 탐색할 때는 [-1 -i]로 탐색하는 것이 가독성이 높다

- 리스트 원소를 한번에 뒤집어주려면 [ : : -1]로 사용 가능하다.

- // 연산자는 나누기를 한 후 정수 부분만 사용한다

​

참고하면 좋을 글 : C언어로 회문체크

https://steemit.com/kr-dev/@codingman/c6--1557274467068