문제 URL : https://www.acmicpc.net/problem/17609
17609번: 회문
각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.
www.acmicpc.net
문제 접근법 :
팰린드롬인지 확인하는문제 입니다. 해당문자열이 팰린드롬인지 양끝에서 확인합니다.
왼쪽 인덱스를 L 오른쪽 인덱스를 R이라 할때 왼쪽과 오른쪽이 하나씩 같은지 확인해서 LR이 만나는 점까지 같은후
L>R 지점까지 도달하면 팰린드롬입니다.
그렇지만 그렇지않으면 팰린드롬이 아니겠지만 하나만 제거해서 팰린드롬인지 확인하면 되기때문에
왼쪽에서 제거해보구 팰린드롬인지 혹은 오른쪽에서 제거해보고 팰린드롬인지 확인하여 유사회문인지 체크합니다.
아니라면 아무것도 아니기때문에 2를 출력하면됩니다.
그렇기에 총 2번의 팰린드롬인지 확인하면 되는 문제입니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
string s;
void input() {
cin >> s;
}
//팰린드롬인지
bool same(int left, int right) {
while (left<=right&&s[left]==s[right]) {
left++;
right--;
}
return left > right;
}
//유사회문인지
bool similiar(int left, int right,int cnt=0) {
while ((left <= right) && (s[left] == s[right]||cnt==0)) {
if (s[left] != s[right]) {
//왼쪽 하나를 제거하거나 오른쪽을하나 제거해보기
return similiar(left + 1, right, 1) || similiar(left, right - 1, 1);
}
else {
left++;
right--;
}
}
return left>right;
}
int pelindrom() {
int res = 0;
int left = 0;
int right = s.size() - 1;
if (same(left, right))
return 0;
if (similiar(left, right))
return 1;
return 2;
}
void solve() {
cout << pelindrom() << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
int test;
cin >> test;
while (test--) {
input();
solve();
}
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등
어떠한 질문이든 좋으니 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 12904 A와 B (0) | 2021.07.15 |
|---|---|
| 백준 16934 게임 닉네임 (0) | 2021.07.11 |
| 백준 5582 공통 부분 문자열 (0) | 2021.07.05 |
| 백준 2531 회전 초밥 (0) | 2021.07.02 |
| 백준 20551 Sort 마스터 배지훈의 후계자 (0) | 2021.07.02 |
