문제
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/86054#
주어진 수열의 왼쪽에서 오른쪽으로 하나 씩 보면서 숫자가 다르면 그냥 넘어가고, 같으면 넘어가거나 숫자를 합칠 수 있을 때, 경우의 수가 얼마나 나오냐 를 묻는 문제입니다.
풀이
1. 전개
1-1.
처음엔 세포가 합쳐지는 과정을 트리로 표현하며 풀어봤습니다.
세포 배열이 {1,1,1,1} 일때 전개를 그림으로 표현한 것입니다.
ex) (시작지점) -> 1 -> 2 -> 1는 세포가 (1)(1,1)(1)로 합쳐졌을 때.
(시작지점) -> 4는 세포가 (1,1,1,1)로 합쳐졌을 때.
시작지점인 루트로부터 잎 노드가 6개이니 나올 수 있는 경우의 수는 6입니다.
하지만 세포 수는 최대 20만이므로 이렇게 전개하니 노드의 수가 너무 많아져 시간/메모리 초과가 나게 되었습니다.
1-2.
(빨간색 숫자는 각 노드에 도달할 수 있는 경로의 수)
오버헤드를 줄이기 위해 트리 형태를 버리고 노드에 weight를 부여했습니다.
그래도 여전히 시간/메모리 초과가 났습니다.
1-3.
빨간색 박스로 레벨을 표현했고 빨간색 숫자는 해당 레벨에 도달할 수 있는 경로의 수입니다.
1-2에서 노드A가 노드B와 연결되어 있다면 노드B와 같은 레벨에 있는 다른 모든 노드도 노드A와 연결되어 있음을 알 수 있습니다.
이 구조대로 코드를 레벨 단위로 구현하니 그래프의 간선이 많이 줄어들어 조건을 충족할 수 있었습니다.
2. 구현
static List<Map<Long, Integer>> levels;각 레벨은 세포의 크기(1-3에서 검은색 숫자)를 key로 갖고, 그 노드와 연결된 레벨(화살표가 시작되는 빨간색 상자)의 인덱스를 value로 갖는 map으로 구현했습니다.
key가 long인 것에 유의. 이거 못찾아서 며칠 동안 못풀었음
//num : 살펴볼 세포 크기, here : 현재 level, par : here와 연결된 level
static long connect(long num, int here, int par){
Map<Long,Integer> level = levels.get(here);
if(!level.containsKey(num)){
level.put(num, par);
}
long ret = sum[par];
if(levels.get(par).containsKey(num)){
ret += connect(num * 2, here, levels.get(par).get(num));
ret %= MOD;
}
return ret;
}sum배열에 해당 레벨에 도달 가능한 경우의 수(1-3의 빨간 숫자)를 저장합니다.
시작 지점을 레벨0으로 두고 1부터 배열의 크기까지
sum[현재 레벨] = connect(살펴볼 세포 크기,현재 레벨,현재 레벨-1)를 호출하면 다음 작업이 실행됩니다:
- 리턴값에
sum[현재 레벨-1]을 더함. (바로 왼쪽 레벨과는 무조건 연결되어 있으므로) 현재 레벨-1레벨에 합쳐질 수 있는 같은 크기의 세포가 있는 지 확인.- 재귀적으로
connect(합쳐졌으니 두배가 된 세포 크기, 현재 레벨, 합쳐진 세포와 연결된 다른 레벨을 호출. sum[현재 레벨]에 리턴값(=현재 레벨에 도달할 수 있는 모든 경로의 수)을 저장
정답은 sum[마지막 레벨]이 됩니다.
전체 코드
자바
import java.util.*;
class Solution {
static List<Map<Long, Integer>> levels;
static long sum[];
static final int MOD = 1000000007;
public int[] solution(int[] a, int[] s) {
int[] answer = new int[s.length];
int idx = 0;
int start, end = 0;
for(int t = 0; t < s.length; t++){
int n = s[t];
start = end;
end = start + n;
sum = new long[n+1];
sum[0] = 1;
//세포 개수 + 1 만큼 level
//각 level에는 세포 크기가 key이고 세포 왼쪽 인덱스가 value인 맵
levels = new ArrayList<>();
for(int i = 0; i <= n; i++){
levels.add(new HashMap<>());
}
levels.get(0).put(new Long(-1),-1);
for(int i = 1; i <= n; i++){
sum[i] = connect(a[start + i - 1], i, i-1);
}
answer[t] = (int) ((sum[n])%MOD);
}
return answer;
}
//par level을 살펴보고 세포크기=num와 같은 세포 있으면 재귀적으로 호출. here = 현재 level
static long connect(long num, int here, int par){
Map<Long,Integer> level = levels.get(here);
if(!level.containsKey(num)){
level.put(num, par);
}
long ret = sum[par];
if(levels.get(par).containsKey(num)){
ret += connect(num * 2, here, levels.get(par).get(num));
ret %= MOD;
}
return ret;
}
}c++
#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
map<long long, int> levels[200001];
long long sum[200001];
int MOD = 1000000007;
long long connect(long long num, int here, int par){
if(levels[here].find(num) == levels[here].end()){
levels[here].insert({num, par});
}
long long ret = sum[par];
if(levels[par].find(num) != levels[par].end()){
ret += connect(num * 2, here, levels[par].find(num) -> second);
ret %= MOD;
}
return ret;
}
vector<int> solution(vector<int> a, vector<int> s) {
vector<int> answer;
int start, end = 0;
for(int t = 0; t < s.size(); t++){
int n = s[t];
start = end;
end = start + n;
levels[start].clear();
levels[start].insert({-1,-1});
sum[start] = 1;
for(int i = start + 1; i <= end; i++){
sum[i] = connect(a[i-1], i, i -1);
}
answer.push_back(sum[end]);
}
return answer;
}