[프로그래머스/Java] 안티세포 - Lv 4 문제 풀이

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

프로그래머스

 

프로그래머스에서는 가끔씩 월간 코드 챌린지라는 대회를 한다.

지금까지 총 3회를 했는데, 이 문제는 그 중 마지막인 월간 코드 챌린지 시즌 3에 출제된 문제이다.

 

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

 

문제 전문 ↓

문제 설명

당신에게 자연수로 이루어진 길이가 n인 배열 b가 주어집니다. 초기에는 모든 수들이 "안티 세포" 안에 들어있습니다. 일반적인 세포는 분열을 하지만, 이 안티 세포는 반대로 여러 안티 세포가 모여 합성을 합니다. 당신은 다음과 같은 과정을 통해 인접한 두 안티 세포를 합치거나 또는 그대로 두려고 합니다.

1. i=0로 설정하고, 빈 배열 c를 하나 만듭니다.
2. i가 n이라면 과정을 종료합니다.
3. b[i]를 포함하는 안티 세포를 X, 그리고 X 바로 왼쪽에 있는 안티 세포를 Y라고 정의합니다. 만약 Y가 존재하고 X의 모든 숫자의 합과 Y의 모든 숫자의 합이 같다면, 당신은 이 두 안티 세포를 합치거나 합치지 않는 행동 중에서 하나를 선택할 수 있습니다.
   
   1. 만약 X와 Y를 합친다면, 둘을 합치고, c의 맨 뒤에 i를 추가한 뒤 다시 3번 과정으로 돌아갑니다.
   2. 만약 X와 Y를 합치지 않는다면(또는 Y가 존재하지 않는다면), i를 1 증가시키고 2번 과정으로 돌아갑니다.

예를 들어, 다음은 b = [1,1,1,1]일 때 위와 같은 과정을 거치는 것을 나타낸 것입니다.

i	안티 세포	c	비고
0	(1)(1)(1)(1)	[]	초기 상태입니다.
1	(1)(1)(1)(1)	[]	i=0 일 때는 Y가 존재하지 않으므로 i를 1 증가시켰습니다.
1	(1,1)(1)(1)	[1]	b[1]을 포함하는 안티 세포(X)와 그 왼쪽의 안티 세포(Y)를 합쳤습니다. 따라서 c에 i=1이 추가됩니다.
2	(1,1)(1)(1)	[1]	b[1]을 포함하는 안티 세포(X) 왼쪽의 안티 세포 Y가 존재하지 않으므로 i를 1 증가시켰습니다.
3	(1,1)(1)(1)	[1]	X의 모든 수의 합은 1이고, Y의 모든 수의 합은 2이므로, 둘은 합칠 수 없습니다. 따라서 i을 1 증가시켰습니다.
3	(1,1)(1,1)	[1,3]	b[3]을 포함하는 안티 세포(X)와 그 왼쪽의 안티 세포(Y)를 합쳤습니다. 따라서 c에 i=3이 추가됩니다.
4	(1,1)(1,1)	[1,3]	b[3]을 포함하는 안티 세포(X)와 그 왼쪽의 안티 세포(Y)를 합칠 수 있었지만 그러지 않았습니다. 따라서 i를 1 증가시켰습니다.

이 경우 c = [1,3]이 됩니다. 물론 이는 c를 만들 수 있는 하나의 경우일 뿐이며, 당신의 선택에 따라 [], [1], [3], [1,3], [2], [1,3,3]으로 c배열을 다양하게 만들 수 있습니다. 당신이 어떤 선택을 하더라도 유한한 횟수 안에 c 배열을 만들 수 있음은 증명될 수 있습니다.

당신은 b가 주어졌을 때 만들 수 있는 서로 다른 배열 c의 개수가 몇 개인지 알고 싶습니다.

정수로 이루어진 배열 a와 s가 매개변수로 주어집니다. a는 여러 개의 b 배열을 순서대로 이어 붙인 배열이며, s는 각 b 배열의 길이가 순서대로 담긴 배열입니다. 각 b 배열에 대해 문제의 답을 109 + 7로 나눈 나머지를 구하여 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

예를 들어, a = [1,2,3,4,5,6,7,8,9], s = [2,3,4] 라면, 다음 3가지 b 배열에 대해서 답을 구해야 합니다.

• b = [1,2] (s[0] = 2 이므로, a의 첫 2개 원소가 b 배열을 이룹니다.)
• b = [3,4,5] (s[1] = 3 이므로, a의 그다음 3개 원소가 b 배열을 이룹니다.)
• b = [6,7,8,9] (s[2] = 4 이므로, a의 그다음 4개 원소가 b 배열을 이룹니다.)

제한사항

• 1 ≤ a의 길이 ≤ 200,000
  
  • 1 ≤ a의 모든 수 ≤ 109
• 1 ≤ s의 길이 ≤ a의 길이
  
  • 1 ≤ s의 모든 수 ≤ a의 길이
  • s의 모든 수의 합 = a의 길이

입출력 예

a	s	result
[1,1,1,1,1,1,2,5,8,2,1,1,4,8,8,8,12,6,6]	[4,3,1,5,6]	[6,3,1,5,9]

입출력 예 설명

입출력 예 #1

다음 5개의 b 배열에 대한 답을 구해야 합니다.

b	답
[1,1,1,1]	6
[1,1,2]	3
[5]	1
[8,2,1,1,4]	5
[8,8,8,12,6,6]	9

따라서, [6,3,1,5,9]를 return 해야 합니다.

문제 풀이

입출력을 다루는 것은 따로 다루지 않고, 안티 세포 배열 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를 만드는 경우의 수 X 안티 세포 직전 원소로 합 n/2를 만드는 경우의 수

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

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

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

 

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

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

b[0] = 1	b[1] = 1	b[2] = 1	b[3] = 1
합: 1 경우의 수: 1 시작 인덱스: 0	합: 1 경우의 수: 1 시작 인덱스: 1	합: 1 경우의 수: 2 시작 인덱스: 2	합: 1 경우의 수: 3 시작 인덱스: 3
	합: 2 경우의 수: 1 시작 인덱스: 0	합: 2 경우의 수: 1 시작 인덱스: 1	합: 2 경우의 수: 2 시작 인덱스: 2
			합: 4 경우의 수: 1 시작 인덱스: 0

전체 코드

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

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;
  }
}

최적화

위 코드는 O(n log(max(b))의 시간 복잡도를 갖습니다.

그런데 같은 시간 복잡도를 갖는다고 하더라도 조금 더 최적화를 해줄 수 있습니다.

1. 원소 합 미리 구해놓기

[1, 1, 1, 1] 예시에서 합 1을 만드는 경우의 수를 알기 위해서는 직전 원소로 만들 수 있는 모든 경우의 수를 순회하며 더해 주어야 했습니다.

이렇게 합을 구하는 과정을 직전 원소로 만들 수 있는 경우의 수를 구할 때 미리 구해 놓으면 별도의 추가적인 원소 순회 없이 바로 참조할 수 있습니다.

 

이는 합을 구하는 시간 복잡도를 O(log(max(b))에서 O(1)로 바꾸는 의미 있는 최적화이지만,

한 원소 당 한 번씩 수행되며, 어차피 합의 개수가 log(max(b))이기 때문에 전체 시간 복잡도는 O(n log(max(b))로 동일합니다.

2. Map 대신 배열 사용하기

b[i]로 만들 수 있는 합은 b[i], 2 * b[i], 2² * b[i], 2⁴ * b[i], ... 와 같이 2ⁿ * b[i]가 됩니다.

따라서 Map 대신 n을 인덱스로 하는 배열을 이용할 수 있습니다.

 

다만 HashMap과 배열은 원소의 참조, 추가, 삭제 등의 연산에 대해서 동일한 시간 복잡도를 가지고 있기 때문에

메서드 호출에 대한 오버헤드 외에 큰 성능 향상은 기대하기 어렵습니다.