BOJ 17609
ํ๋ฌธ ์ฑ๊ณต
1 ์ด (์ถ๊ฐ ์๊ฐ ์์) 512 MB 15091 4131 2961 28.246% ๋ฌธ์
ํ๋ฌธ(ๅๆ) ๋๋ ํฐ๋ฆฐ๋๋กฌ(palindrome)์ ์ ๋ค ๋ฐฉํฅ์ผ๋ก ๋ณผ ๋ ๊ฐ์ ์์์ ๋ฌธ์๋ก ๊ตฌ์ฑ๋ ๋ฌธ์์ด์ ๋งํ๋ค. ์๋ฅผ ๋ค์ด ‘abba’ ‘kayak’, ‘reviver’, ‘madam’์ ๋ชจ๋ ํ๋ฌธ์ด๋ค. ๋ง์ผ ๊ทธ ์์ฒด๋ ํ๋ฌธ์ด ์๋์ง๋ง ํ ๋ฌธ์๋ฅผ ์ญ์ ํ์ฌ ํ๋ฌธ์ผ๋ก ๋ง๋ค ์ ์๋ ๋ฌธ์์ด์ด๋ผ๋ฉด ์ฐ๋ฆฌ๋ ์ด๋ฐ ๋ฌธ์์ด์ “์ ์ฌํ๋ฌธ”(pseudo palindrome)์ด๋ผ๊ณ ๋ถ๋ฅธ๋ค. ์๋ฅผ ๋ค์ด ‘summuus’๋ 5๋ฒ์งธ๋ ํน์ 6๋ฒ์งธ ๋ฌธ์ ‘u’๋ฅผ ์ ๊ฑฐํ์ฌ ‘summus’์ธ ํ๋ฌธ์ด ๋๋ฏ๋ก ์ ์ฌํ๋ฌธ์ด๋ค.
์ฌ๋ฌ๋ถ์ ์ ์๋ ๋ฌธ์์ด์ ๋ถ์ํ์ฌ ๊ทธ๊ฒ์ด ๊ทธ ์์ฒด๋ก ํ๋ฌธ์ธ์ง, ๋๋ ํ ๋ฌธ์๋ฅผ ์ญ์ ํ๋ฉด ํ๋ฌธ์ด ๋๋ “์ ์ฌํ๋ฌธ”์ธ์ง, ์๋๋ฉด ํ๋ฌธ์ด๋ ์ ์ฌํ๋ฌธ๋ ์๋ ์ผ๋ฐ ๋ฌธ์์ด์ธ์ง๋ฅผ ํ๋จํด์ผ ํ๋ค. ๋ง์ผ ๋ฌธ์์ด ๊ทธ ์์ฒด๋ก ํ๋ฌธ์ด๋ฉด 0, ์ ์ฌํ๋ฌธ์ด๋ฉด 1, ๊ทธ ์ธ๋ 2๋ฅผ ์ถ๋ ฅํด์ผ ํ๋ค.
์ ๋ ฅ
์ ๋ ฅ์ ์ฒซ ์ค์๋ ์ฃผ์ด์ง๋ ๋ฌธ์์ด์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ ์ ์ T(1 ≤ T ≤ 30)๊ฐ ์ฃผ์ด์ง๋ค. ๋ค์ ์ค๋ถํฐ T๊ฐ์ ์ค์ ๊ฑธ์ณ ํ ์ค์ ํ๋์ ๋ฌธ์์ด์ด ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค. ์ฃผ์ด์ง๋ ๋ฌธ์์ด์ ๊ธธ์ด๋ 3 ์ด์ 100,000 ์ดํ์ด๊ณ , ์๋ฌธ ์ํ๋ฒณ ์๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์๋ค.
์ถ๋ ฅ
๊ฐ ๋ฌธ์์ด์ด ํ๋ฌธ์ธ์ง, ์ ์ฌ ํ๋ฌธ์ธ์ง, ๋ ๋ชจ๋ ํด๋น๋์ง ์๋์ง๋ฅผ ํ๋จํ์ฌ ํ๋ฌธ์ด๋ฉด 0, ์ ์ฌ ํ๋ฌธ์ด๋ฉด 1, ๋ ๋ชจ๋ ์๋๋ฉด 2๋ฅผ ์์๋๋ก ํ ์ค์ ํ๋์ฉ ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ 1 ๋ณต์ฌ
7 abba summuus xabba xabbay comcom comwwmoc comwwtmoc
์์ ์ถ๋ ฅ 1 ๋ณต์ฌ
0 1 1 2 2 0 1โ
์์ธ์ผ์ด์ค๋ฅผ ๋๋ฐ๋ก ์ฒ๋ฆฌํ์ง ์์ 10๋ฒ์ด๋ ํ๋ฆฐ ํ๊ฐ ์๋ฉ๋๋ ๋ฌธ์ ์ด๋ค.
๋ฌธ์ ๋ ๊ฐ๋จํ๋ค, ๋ฌธ์์ด์ ์์์ ์ ์ฒซ๋ฒ์งธ ํฌ์ธํฐ, ๋์ ์ ๋๋ฒ์งธ ํฌ์ธํฐ๋ก ์ก์ ์ฒซ๋ฒ์งธ ํฌ์ธํฐ <= ๋๋ฒ์งธ ํฌ์ธํฐ ๊ฐ ์ฐธ์ผ ๋์ ๊ณ์ ํ์ธํด์ฃผ๋ฉด ๋๋ค.
๋ค๋ง ์ฌ๊ธฐ์ ์ ์ฌํ๋ฌธ์ด๋ผ๋ ๊ฒ์ ํ๋ณํด์ฃผ์ด์ผ ํ๋๋ฐ, ์ด๊ฒ์ ๋ฌธ์์ด์์ ํ๊ฐ์ง ๋ฌธ์๋ฅผ ์ ๊ฑฐํ๋ฉด ํ๋ฌธ์ด ๋๋ ๋ฌธ์์ด์ด๋ค.
์ด๋ ์ฒซ๋ฒ์งธ ํฌ์ธํฐ + 1 == ๋๋ฒ์งธ ํฌ์ธํฐ, ์ฒซ๋ฒ์งธ ํฌ์ธํฐ == ๋๋ฒ์งธ ํฌ์ธํฐ - 1 ์ธ ๊ฒฝ์ฐ์๋ง ์ฑ๋ฆฝํ ์ ์๋ค.
๋ง์ผ ์ด๊ฒ์ด ์ฑ๋ฆฝํ์ง ์์ผ๋ฉด ์ ์ฌํ๋ฌธ๋, ํ๋ฌธ๋ ์๋๊ฒ์ด๋ค.
๋๋ ์ด ๋ฌธ์ ๋ฅผ ํ๋ ์์ฐจ์ ์ผ๋ก ์กฐ๊ฑด๋ฌธ์ ์จ return์์ผ์ฃผ์ด ์ฒซ๋ฒ์งธ ์กฐ๊ฑด์ ํด๋นํ์ง ์๋๋ฐ ๋๋ฒ์งธ ์กฐ๊ฑด์ ํด๋นํ๋ ๊ฒฝ์ฐ๋ฅผ ์ก์๋ด์ง ๋ชปํ์๋ค.
์๊ฐ๋ณต์ก๋๋ ๊ณ์ฐํ๊ธฐ ์ข ํ๋ค์๋ค.
#include <iostream>
#include <string>
using namespace std;
string s;
int T;
int func(int st, int last, int ans){
while(st <= last){
if(s[st] == s[last]){
st += 1;
last -= 1;
continue;
}
if(ans == 1){
return 2;
}
int case1 = func(st+1, last, 1);
int case2 = func(st, last-1, 1);
return min(case1, case2);
}
return ans;
}
int main(){
cin>>T;
while(T--){
int ans = 0;
cin>>s;
int st = 0, last=s.size()-1;
cout<<func(st, last, 0)<<'\n';
}
}
์ฝ๋๋ฅผ ๋ณด๋ฉด intํ func๋ฅผ ํ๋ ๋ง๋ค์ด return๊ฐ์ด ๊ณง๋ฐ๋ก ์ ๋ต์ด ๋๊ฒ ํ์๋ค.
string์ด ๊ทธ๋ฅ ํ๋ฌธ์ผ ๊ฒฝ์ฐ๋ 1/2N(size of string) ์ด ๊ฑธ๋ฆฌ๊ฒ ๋๋๋ฐ,
์ฌ๊ธฐ์ ์ฌ๊ท๊ฐ ๋์๊ฐ๋ฉด์ ์ผ๋จ ํ๋ฌธ์ด ์๋๋ฉด Nํ์์ด ๊ฑธ๋ฆฌ๊ฒ ๋๋ค ( st+1ํ func, last -1ํ func (1/2N * 2))
ํ์ง๋ง ans == 1์ผ๋๋ฅผ ์กฐ๊ฑด์ผ๋ก ๊ฑธ์ด, ์ด ๋ฌธ์ ๋ O(N)์ผ๋ก ํ ์ ์๊ฒ ๋ง๋ค์๋ค.