algorithm

BOJ 17609

rkawk 2022. 9. 27. 22:38
๋”๋ณด๊ธฐ

ํšŒ๋ฌธ ์„ฑ๊ณต

 

 

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)์œผ๋กœ ํ’€ ์ˆ˜ ์žˆ๊ฒŒ ๋งŒ๋“ค์—ˆ๋‹ค.