Gidhub BE Developer

[BOJ] 10942. 팰린드롬?

2018-09-14
goodGid

Problem

Problem URL : 팰린드롬?

Screenshots of Problem Explain

[1] Answer Code (18. 01. 24)

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int arr[2001];
int d[2001][2001]; // d is DP

int solve(int st, int end){
    if( st > end ) return 1;
    if( d[st][end] != -1 ) return  d[st][end];
    if( arr[st] != arr[end]) return d[st][end] = 0;
    return d[st][end] = solve(st+1, end-1);
}

int main(){
    memset(d,-1,sizeof(d));
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        scanf("%d",&arr[i]);
    }
    
    int m;
    cin >> m;
    
    int st,end;
    while ( m--) {
        scanf("%d%d",&st,&end);
        printf("%d\n",solve(st, end));
    }
    return 0;
}

Review


[2] Answer Code (18. 09. 14)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <memory.h>
using namespace std;

string tmp, str;
int A[1000001 * 2];

void manachers(string S, int N){
    int r = 0, p = 0;
    for (int i = 0; i < N; i++){
        if (i <= r)
            A[i] = min(A[2 * p - i], r - i);
        else
            A[i] = 0;
        
        while (i - A[i] - 1 >= 0 && i + A[i] + 1 < N && S[i - A[i] - 1] == S[i + A[i] + 1])
            A[i]++;
        
        if (r < i + A[i]){
            r = i + A[i];
            p = i;
        }
    }
}

int main(){
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++){
        int val;
        scanf("%d", &val);
        
        /*
         tmp += val
         이렇게 하게되면
         val값이 1일 때
         tmp에는 \x01이 들어간다.
         그렇기 때문에 + '0'을 해줘서
         int형인 val값을 string처럼 바꾼다.
         */
        
        // [1] 또는 [2]
        // 둘 다 가능하다.
        tmp += val + '0'; // [1]
//        tmp.push_back(val + '0'); // [2]
    }
    int len = (int)tmp.size();
    str = tmp[0];
    
    for (int i = 1; i < len; i++){
        str += '#';
        str += tmp[i];
    }
    
    manachers(str, (int)str.size());
    
    int q;
    scanf("%d", &q);
    while (q--){
        int s, e;
        scanf("%d %d", &s, &e);
        s--; e--;
        s *= 2; // 중간에 += '#'을 해줬기 때문에 2배씩 증가
        e *= 2; 
        
        int r = A[(s + e) / 2];
        if ((s + e) / 2 + r >= e)
            printf("1\n");
        else
            printf("0\n");
    }
    
    return 0;
}


/*
1. Answer Code
*/
str = tmp[0];
    
    for (int i = 1; i < len; i++){
        str += '#';
        str += tmp[i];
    }
    str += '#';
    manachers(str, (int)str.size());
/*
1. Wrong Code
2. str에 tmp[0]값을 넣지 않고
3. for i의 시작을 0 부터 했다.
*/

//    str = tmp[0];
    for (int i = 0; i < len; i++){
        str += '#';
        str += tmp[i];
    }
    str += '#';
    manachers(str, (int)str.size());

/*
1. Answer Code
2. str에 tmp[0]값을 넣지 않고
3. for문 안에서
4. str += tmp[i];
5. str += '#'; 순서로 넣었다.
*/

int len = (int)tmp.size();
//    str = tmp[0];
    for (int i = 0; i < len; i++){
        str += tmp[i];
        str += '#';
    }
    str += '#';
    manachers(str, (int)str.size());

Review

  • str에 #을 더해주는 순서는 값을 먼저 넣고 #을 더해주면 맞는거같다.

  • 정답 코드 출처는 10942번 팰린드롬?이다.

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.
  • 최대 N값이 2000인줄 알고 int A[2001]로 잡으니까 런타임에러가 나왔다.
    값의 범위가 1 ~ 2000이지 N값은 최대 100,000이다.

  • 그리고 배열 선언은 중간 중간 #이 들어가기 때문에 100,000 * 2를 해줘야한다.

코드 설명 : 
int r = A[(s + e) / 2];
if ((s + e) / 2 + r >= e)

각 인덱스에 대해 r이 의미해주는 것은 각 인덱스에 대해 팰린드롬이 될 수 있는 최대 범위를 말해주고 있고
p는 그러한 r이 형성되고 있는 중심점을 나타내주고 있다.

다음과 같이 가정해보자.
s = 2
e = 4


value : a b a b a
index : 1 2 3 4 5
A     : 0 1 2 1 0


s + e / 2 = 3 이고
r = A[(s + e) / 2] = 2 될 것이다. // 자기 index를 제외하고 좌우로 몇개까지 가능한 값

그렇기 때문에

(s + e) / 2 + r 는 s와 e의 중앙값으로부터 좌우로 몇 개 까지 회문인지를 체크할 수 있다.

즉 (s + e) / 2 + r는 5가 되고 e는 4이기 때문에 

2 ~ 4 번째가 회문이냐를 질문에 대해서는 True가 된다.

// (s + e) / 2 + r에 의해 1~5까지가 회문인데 물어본 값은 2~4이기 때문이다.
// 또한 e값만 신경쓰면 되는 이유는 s+e/2 값(=중앙값)에서 부터 r값을 더한것이기 때문에
// 비교 값이 e 또는 s여도 중앙으로부터 값은 똑같기 때문이다.
// r = 2 이면 
// (s + e) / 2 + r 값이 >= e 랑 (s + e) / 2 - r <= s 같다.


만약 
(s + e) / 2 = 3이고 
(s + e) / 2 + r가 5인데
e값이 6이라면
s+1 부터 e(=5)는 회문이지만
s 부터 6까지는 회문이 아니라는 뜻이 된다.

// 이 예제는 틀릴 수 도 있다.
// 그냥 이런 느낌이구나를 이해시키기 위한 예제임을 강조한다.

Comments

Content