[백준]10942 - 팰린드롬?

핵심 아이디어

1. 구간 [a, b]를 골라 만든 수가 팰린드롬수라고 할 때, 구간[a, b] 내에 (a + b) / 2 == (a' + b') / 2를 만족하는 임의의 두 숫자 a', b'로 만들어진 구간 [a', b'] (이때 a' <= b')를 골라 만든 수 역시 팰린드롬수이다.
2. 구간 [a, b]를 골라 만든 수가 팰린드롬수가 아닐 때, 구간[a, b] 밖에 (a + b) / 2 == (a' + b') / 2를 만족하는 임의의 두 숫자 a', b'로 만들어진 구간 [a', b'] (이때 a' <= b')를 골라 만든 수 역시 팰린드롬수가 아니다.

구현

구간의 양 끝의 합을 2로 나눈 중앙값을 키로 가지는 2개의 딕셔너리를 만든다.

딕셔너리 PL은 키값이 중앙값인 팰린드롬수를 만족하는 가장 큰 구간을 저장한다.

딕셔너리 NPL은 키값이 중앙값인 팰린드롬수를 만족하지 않는 가장 작은 구간을 저장한다.

 

using StreamWriter sw = new(Console.OpenStandardOutput());
var read = () => Console.ReadLine().Split().Select(int.Parse).ToArray();

int S, E, N, M, ANS = 0;
N = read()[0];
var seq = read();
M = read()[0];
Dictionary<double, (int a, int b)> PL = new(), NPL = new();
var getAxis = (int a, int b) => (a + b) * 0.5;

for (int i = 0; i < M; i++)
{
    var input = read();
    S = --input[0]; E = --input[1];

    var axis = getAxis(S, E);

    //중앙값을 만족하는 팰린드롬수 내에 구간
    if (PL.ContainsKey(axis) && PL[axis].a <= S && PL[axis].b >= E)
    {
        ANS = 1;
    }
    //중앙값을 만족하는 팰린드롬수 외에 구간
    else if (NPL.ContainsKey(axis) && NPL[axis].a >= S && NPL[axis].b <= E)
    {
        ANS = 0;
    }
    //앞서 구한 구간으로 팰린드롬수를 판별 못하므로 새로 갱신한다.
    else if (isPalindrome(S, E))
    {
        if (!PL.TryAdd(axis, (S, E)))
            PL[axis] = (S, E);
        ANS = 1;
    }
    else
    {
        if (!NPL.TryAdd(axis, (S, E)))
            NPL[axis] = (S, E);
        ANS = 0;
    }

    sw.WriteLine(ANS);
}

bool isPalindrome(int s, int e)
{
    var axis = getAxis(s, e);
    while (s <= e)
    {
        //앞서 구한 구간을 재활용함
        if (PL.ContainsKey(axis) && PL[axis].a <= s && PL[axis].b >= e)
            return true;
        else if ((NPL.ContainsKey(axis) && NPL[axis].a >= s && NPL[axis].b <= e) || seq[s++] != seq[e--])
            return false;
    }
    return true;
}

 

비고

테스트 케이스가 100,000이고 각 숫자의 범위가 1 ~ 2000인 것으로 잘못봐서 2차 배열을 못써서 (int[100_000, 100_000] 하면 메모리 약 3.7GB 나옴...) 이렇게 풀었다...