[탐색 및 시뮬레이션] 파이썬 알고리즘 문제 2-1 "회문 문자열 검사"

회문 문자열 검사

[시간복잡도]

O(n)

 

: for문으로 코드를 돌리는 것이 제일 중요한 포인트이다. 

해당 문자열을 반복해서 코드를 동작시키는 것이 핵심이다.

[공간복잡도]

O(1)

 

:  고정공간으로 사용하는 것은 n / 가변공간으로 사용하는 것은 string / string_cnt / check 를 사용한다.

 

Problem

회문 문자열 검사 N개의 문자열 데이터를 입력받아 앞에서 읽을 때나 뒤에서 읽을 때나 같은 경우(회문 문자열) 이면 YES를 출력하고 회문 문자열이 아니면 NO를 출력하는 프로그램을 작성한다.

 

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

 

▣ 입력설명

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

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

 

▣ 출력설명

 

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

 

▣ 입력예제

 

5

level

moon

abcba

soon

gooG

 

▣ 출력예제

 

#1 YES

#2 NO

#3 YES

#4 NO

#5 YES

 

💯 Solution ①

 

import sys
sys.stdin=open("input.txt","rt")
 
n=int(input())
 
for i in range(n):
    string=input().lower()
    if string == string[::-1]:
        check="YES"
    else:
        check="NO"
    print("#%d %s" %(i+1, check))

 

- for 문을 통해서 위에서 보여지는 갯수만큼 반복문을 돈다.

- 대문자/소문자 구분을 하면 안되기 때문에 다 소문자화시킨다. => lower()

- string 과 string[::-1] 이 똑같다면, 해당 문자열은 "회문 문자열"에 해당한다.

- 똑같다면, check 변수에 "YES" 를 담고, 다르다면, check 변수에 "NO"를 담는다.

- 출력양식에 맞춰서 출력을 한다.

 

💯 Solution ②

: Tutor님의 Code

 

 

① for 문을 사용해서 작성

 

: 여기서 제일 포인트는,

 

(1) for j in range(size//2) : size로 반복을 하는 것이 아니라, size//2로 해서 반복문을 최소화한다는 것

(2) if s[j] != s[-1-j] 를 통해서, 제일 앞부터 제일 뒤까지 비교하는 if문을 만든다. 

 

코드를 설명해야하는 자리에세는 해당코드가 더 좋은 코드임.

 

import sys
sys.stdin=open("input.txt","r")
n=int(input())
for i in range(n):
    s=input()
    s=s.upper()
    size=len(s)
    # size를 다 볼 필요가 없음 절반만 보면 된다! 5개일 경우 2번만 비교하면 됨
    for j in range(size//2):
        # ex) level => s[j]=l (앞쪽) , s[-1-j]=l (뒤쪽)
        if s[j]!=s[-1-j]:
            print("#%d NO" %(i+1))
            break
    # for문을 정상적으로 끝낸다면, else문을 탄다.
    else:
        print("#%d YES" %(i+1))

 

② 문자열 슬라이싱을 이용한 방법

 

: 나의 코드와 비슷한 형태

import sys
sys.stdin=open("input.txt","r")
n=int(input())
for i in range(n):
    s=input()
    s=s.upper()
    if s==s[::-1]:
        print("#%d YES" %(i+1))
    else:
        print("#%d NO" %(i+1))
 

 

📚 참고