알고리즘/BOJ
[BOJ 17609, Python 3] 회문
70825
2021. 8. 8. 15:08
반응형
https://www.acmicpc.net/problem/17609
17609번: 회문
각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.
www.acmicpc.net
풀이
회문에서 삭제할 곳을 찾는 방법은 양끝부터 확인하는 for문을 만들어서 확인해보면 삭제해야할 부분에서 에러가 나올겁니다. 만약 나오지 않으면 0을 출력하면 됩니다.
삭제해야하는 글자는 왼쪽에서 시작하는 글자, 오른쪽에서 시작하는 글자 둘 중 하나이기 때문에 왼쪽 인덱스의 글자를 삭제해보고 돌려보고, 오른쪽 인덱스의 글자를 삭제해서 돌려보고 확인해보고 둘 중 하나라도 회문이 만들어지면 1을 출력, 아니면 2를 출력하면 됩니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
for _ in range(int(input())):
s = [*input()]
idx = -1
for i in range(len(s)//2):
if s[i] != s[-1-i]:
idx = i
break
if idx == -1:
print(0)
continue
flag = [True, True]
for i, (x, y) in enumerate([(idx + 1, len(s) - 1 - idx), (idx, len(s) - 2 - idx)]):
while x <= y:
if s[x] != s[y]:
flag[i] = False
break
x += 1; y -= 1
if flag[0] or flag[1]: print(1)
else: print(2)
|
cs |
반응형