현이의 개발 이야기

안티세포 - Lv 4 문제 풀이

프로그래머스 2024. 06. 22. 03:39

https://school.programmers.co.kr/learn/courses/30/lessons/86054

프로그래머스에서는 가끔씩 월간 코드 챌린지라는 대회를 한다.
지금까지 총 3회를 했는데, 이 문제는 그 중 마지막인 월간 코드 챌린지 시즌 3에 출제된 문제이다.

DP인 것 같다는 생각이 들긴 했지만 조금 특이한 형태의 DP라 시간이 좀 걸렸다. 시간 복잡도를 활용해 풀이에 접근하는 방식을 한 번 살펴보도록 하자.

문제 풀이

입출력을 다루는 것은 따로 다루지 않고, 안티 세포 배열 b에 대해서 만들 수 있는 서로 다른 배열 c의 개수를 구하는 것만 다루겠습니다.

c를 구해야 할까? 문제 단순화 하기

이 문제의 핵심은 c를 과연 구해야 하는지 여부를 파악하는 데 있습니다.

예를 들어서, 문제에서 주어진 안티 세포인 (1)(1)(1)(1)이 있습니다.
이 안티 세포를 (1, 1)(1, 1)과 같은 형태로 합치는 c는 몇 개가 존재할까요?
[1, 3] 하나밖에 없습니다.

또, (1)(1)(1, 1)을 만들기 위한 c는 몇 개일까요?
[3] 하나입니다.

감이 오시나요?
안티 세포가 합쳐질 수 있는 모든 경우의 수에 대해서,
해당 경우의 수를 만들어낼 수 있는 c는 유일합니다.

반대로, 서로 다른 배열 c는 다르게 합쳐진 안티 세포 결과를 만들어 내게 됩니다.

이는 다음의 두 특성 때문에 성립하게 됩니다.

세포가 합쳐질 때, 두 세포는 같은 값을 가지고 있다.
b의 인덱스 i는 항상 증가하는 방향으로 이동한다.

이에 따라, 세포가 합쳐질 때, c에 기록되는 i는 합쳐지는 세포의 마지막 인덱스가 되게 됩니다.
즉 같은 형태의 합쳐진 세포를 만들기 위해서 해당 세포 내의 다른 인덱스가 기록되는 일이 없다는 뜻이고,
결과 모양이 같으면 c 또한 같다는 결론에 이르르게 됩니다.

이 내용을 파악했다면, 문제를 단순화할 수 있습니다.
이제 문제는 가능한 c의 개수를 구하는 것이 아니라, 안티 세포가 합쳐질 수 있는 경우의 수를 구하는 문제가 됩니다.

시간 복잡도로 해법 추정하기

문제에서 a의 길이가 최대 200,000이므로, b의 길이의 최대도 200,000이 됩니다.
b의 길이를 N이라고 합시다.

배열의 원소를 적어도 한 번씩은 방문해야 하기에, O(N)은 필연적으로 소요됩니다.
이제 원소를 방문할 때마다 얼마만큼의 시간 복잡도를 소요할 수 있는지를 생각해 봅시다.

N의 최대가 200,000인만큼 한 연산에 O(N)이 걸리게 된다면 전체 시간 복잡도가 O(N²)이 되어 시간 초과입니다.
한 번의 연산 당 가능한 시간 복잡도는 O(logN) 혹은 O(1)이 됩니다.

O(logN) 가능성 살펴보기

저번 포스트, 행렬과 연산 - Lv 4 문제 풀이에서 언급했듯이, O(logN)은 특별한 시간 복잡도입니다.
이 문제에 이를 적용할만한 내용이 있을까요?

행렬과 연산 문제와는 달리, 이번 문제에는 그런 내용이 있습니다.
바로 "같은 값을 가지고 있는 안티 세포만 합쳐질 수 있다"라는 점 때문입니다.

안티 세포가 여러 번 합쳐지는 경우를 생각해 봅시다.
처음엔 1 두 개가 합쳐져 2가 만들어집니다.
그 다음엔 2 두 개가 합쳐저 4가 만들어집니다.
그 다음엔 4 두 개가 합쳐저 8이 만들어집니다.
그 다음엔 8 두 개가 합쳐저 16이 만들어집니다.

이처럼 합쳐지는 안티 세포의 숫자는 계속 두 배씩 커지게 됩니다.
다음과 같은 배열을 생각해 봅시다.
[64, 32, 16, 8, 4, 2, 1, 1]

가장 오른쪽에 있는 1을 가능한 만큼 합치는 경우에 모든 원소가 합쳐집니다.
이는 O(N)번이라고 할 수 있을 것입니다.
그러면 연산에는 최대 O(N)이 걸리는 것이 아닐까요?

문제의 조건 중 원소의 값은 10^9보다 작거나 같다는 점이 있습니다.
안티 세포가 합쳐질 수 있는 가장 큰 수는 10^9인 것입니다.
그리고 이를 만들기 위해서는 최대 log_2(10^9)인 약 30번의 합 밖에 소요되지 않습니다.
즉, log는 배열의 길이에 적용되는 것이 아니라, 배열 원소의 값에 적용되는 것이었던 것을 알 수 있습니다.

10^9는 배열 b의 최댓값이므로 log_2(max(b))라고 표기할 수 있습니다.
따라서 전체 시간 복잡도는 O(n log(max(b))가 됩니다.
이는 n과 max(b)의 최댓값을 넣어보면 약 600만의 수치로 계산되어, 충분한 시간 복잡도입니다.

원소 당 연산 생각하기

위에서 log의 가능성을 확인하였습니다.
log가 배열 원소의 값에 적용이 된다는 것은, 해당 원소가 합쳐질 수 있는 횟수가 최대 log(max(b)) 번이라는 의미입니다.

연산의 시간 복잡도를 O(log(max(b))로 유지하기 위해서는 세포를 합쳐서 원하는 합을 만드는 경우의 수를 구하는 시간 복잡도는 상수 시간이어야 합니다. 그래야 이를 log(max(b)) 번 반복해도 전체 시간 복잡도가 O(log(max(b))가 되기 때문입니다.

즉, 각 원소 별로 만들 수 있는 합에 대해서, 각 경우의 수를 가지고 있어야 합니다.
예를 들어 [1, 1, 1, 1]의 경우에는 다음과 같은 데이터를 생성해낼 수 있어야 합니다.

b[0] = 1	b[1] = 1	b[2] = 1	b[3] = 1
합:1, 경우의 수: 1	합:1, 경우의 수: 1	합:1, 경우의 수: 2	합:1, 경우의 수: 3
	합:2, 경우의 수: 1	합:2, 경우의 수: 1	합:2, 경우의 수: 2
			합:4, 경우의 수: 1

경우의 수 구하기

각 합을 만들어내는 경우의 수를 구하기 위해, 우선 위의 표를 어떻게 만들 수 있는지 합 별로 하나씩 살펴봅시다.

1. 합 1을 만드는 경우

이 경우는 해당 원소만으로 안티 세포의 합을 만들어낼 수 있습니다.
따라서 직전 원소로 만들 수 있는 모든 경우의 수가 해당 원소로 합 1을 만드는 경우의 수가 됩니다.

예를 들어, 위 표에서 마지막 1로 합 1을 만드는 경우의 수를 구하기 위해서는 직전 1인 세 번째 1로 만들 수 있는 모든 경우의 수를 더해주면 됩니다.

2. 합 2를 만드는 경우

이 경우도 위와 비슷하게 처리할 수 있습니다.
합을 2를 만들기 위해선 직전 안티 세포와 합쳐야 합니다.
이 때 경우의 수는 합쳐진 안티 세포들을 제외하고, 그 앞에 있는 안티 세포로 만들 수 있는 경우의 수가 됩니다.

예를 들어, 마지막 1로 합 2를 만드는 경우의 수는 직전에 있는 1로 1을 만드는 경우의 수와 같습니다.

3. 합 4를 만드는 경우

합 4를 만들기 위해서는 합 2를 두 개 합쳐야 합니다.
따라서 이 경우의 수는 현재 검사하는 원소로 2를 만들 수 있는 경우의 수와,
이 안티 세포 직전의 원소를 포함해 2를 만들 수 있는 경우의 수를 곱한 것이 됩니다.

예를 들어, 마지막 1로 합 4를 만드는 경우는,
마지막 1로 합 2를 만드는 경우의 수인 1과
여기에 포함되지 않으면서, 직전 원소인 두 번째 1로 합 2를 만드는 경우의 수인 1을 곱하여
1이 그 경우의 수가 됩니다.

논리 일반화하기

여기까지 왔으면 합 2, 4를 만들어낸 논리를 다음과 같이 일반화 할 수 있습니다.
합 1을 만드는 경우의 수는 쉽게 구할 수 있으므로 제외합니다.

합 n을 만드는 경우의 수 =
    해당 원소로 합 n/2를 만드는 경우의 수 *
    안티 세포 직전 원소로 합 n/2를 만드는 경우의 수

합쳐진 안티 세포 직전 원소 구하기

해당 원소로 합 n/2를 만드는 경우의 수는 재귀적으로 쉽게 구할 수 있습니다.

그런데 안티 세포 직전 원소는 어떻게 구할 수 있을까요?

이를 구하기 위해서는 원소별로 합과 경우의 수 외에 안티 세포의 시작 인덱스를 함께 넣어주면 됩니다.

즉, 이제 다음과 같이 데이터를 만들어 주면 됩니다.

전체 코드

위 내용을 종합하면, 다음과 같이 문제를 풀 수 있습니다.

import java.util.*;

public class Solution {
  private static final int DIV = 1_000_000_007;

  private static int sum(int a, int b) {
    long sum = (long) a + b;
    return (int) (sum % DIV);
  }

  private static class Count {
    final long sum;
    final int count;
    final int offset;

    public Count(long sum, int count, int offset) {
      this.sum = sum;
      this.count = count;
      this.offset = offset;
    }
  }

  private int solve(int[] b) {
    List<Map<Long, Count>> counts = new ArrayList<>(b.length);
    for (int i = 0; i < b.length; i++) {
      Map<Long, Count> map = new HashMap<>();
      counts.add(map);

      long targetSum = b[i];
      if (i == 0) {
        map.put(targetSum, new Count(targetSum, 1, i));
      } else {
        map.put(
            targetSum,
            new Count(
                targetSum,
                counts.get(i - 1).values().stream()
                    .mapToInt(c -> c.count)
                    .reduce(Solution::sum)
                    .orElse(0),
                i));
      }

      while (true) {
        targetSum *= 2;
        Count lastCount = map.get(targetSum / 2);

        int prevOffset = lastCount.offset - 1;
        if (prevOffset < 0) break;

        Map<Long, Count> prevMap = counts.get(prevOffset);
        if (!prevMap.containsKey(targetSum / 2)) break;

        Count count = prevMap.get(targetSum / 2);
        map.put(targetSum, new Count(targetSum, count.count, count.offset));
      }
    }

    return counts.get(counts.size() - 1).values().stream()
        .mapToInt(c -> c.count)
        .reduce(Solution::sum)
        .orElse(0);
  }

  public int[] solution(int[] a, int[] s) {
    int[] answer = new int[s.length];
    int offset = 0;
    for (int i = 0; i < answer.length; i++) {
      answer[i] = solve(Arrays.copyOfRange(a, offset, offset + s[i]));
      offset += s[i];
    }
    return answer;
  }
}

로그인이 필요합니다.

로그인