롤케이크 위에 올려져 있는 토핑의 종류를 담고 있는 배열
롤케이크를 공평하게 자르는 방법의 수
1 ≤ topping의 길이 ≤ 1,000,000
1 ≤ topping의 원소 ≤ 10,000
Input으로 들어온 배열인 topping을 자른다.
[1, 2, 1, 3, 1, 4, 1, 2] 형태로 들어온 케이크가 있으면, 0번과 1번 사이를 기준으로 자르게 되면
[1], [2, 1, 3, 1, 4, 1, 2] 형태로 잘리게 된다.
이때 왼쪽(철수) 는 토핑이 1종류 (1) 이다.
오른쪽(동생) 은 토핑이 4종류 (1,2,3,4) 이다
케이크의 크기와 무관하게 둘의 토핑의 종류가 같으면 공평하게 자른 것이다.
Set 을 이용해서 했다.
public static int solution(int[] topping){
// 처음에 young 에 모두 추가
// i번째 껄 old 에 추가
// i번째 토핑이 i번째 이후에 등장하면 그대로 두고
// 등장하지 않으면 young 에서 해당 토핑도 빼줌
Set<Integer> old = new HashSet<>();
Set<Integer> young = new HashSet<>();
for(int top : topping){
young.add(top);
}
int youngSize=young.size();
int oldSize=0;
int count=0;
// i 번째 토핑을 왼쪽에 더하고 오른쪽에선 뺌
for(int i=0;i<topping.length;i++){
//System.out.println(old+" "+ young);
int top = topping[i];
if(old.add(top)){
oldSize+=1;
}
boolean flag = false;
for(int j=i+1;j<topping.length;j++){
if(topping[j]==top){
flag=true;
break;
}
}
if(!flag){
young.remove(top);
youngSize-=1;
}
if(oldSize==youngSize){
count++;
}
}
return count;
}
동적 프로그래밍
1번으로 직접 풀어보고, 실행 시간이 너무 길어서 풀이를 보았다. 오른쪽(동생)에게 모든 토핑이 있는 상태에서 한개씩 떼어서 주기 때문에 DP 로 풀이가 가능하다.
우선 토핑의 원소는 최대 1만 이므로 길이 10001 짜리 정수 배열 right , left 를 만든다.
right[i] 는 동생이 가진 토핑 ' i ' 의 갯수를 나타낸다.
ex) right[2] = 3 이라면, 2라는 토핑을 3개 가지고 있는 것이다.
1. 우선 모든 토핑을 동생이 가지고 있으니, right 배열을 업데이트한다.
2. 오른쪽(동생) 이 갖고 있는 토핑의 갯수를 업데이트한다.
3. 토핑 배열을 기준으로 시작한다.
# 1. 토핑이 i 라 하면, right[i] 를 조회한다.
## right[i] 가 0이면, 동생이 해당 토핑을 더 이상 갖고있지 않음
### 동생이 갖고있는 토핑 갯수가 하나 줄어든다.
# 2. 왼쪽(철수) 가 갖고 있는 토핑 정보인 left[i]를 조회
## 2-1. left[i]가 0이면 i 토핑을 철수가 갖고있지 않다.
####### 철수가 갖고있는 토핑 종류가 1 증가하고, left[i] 를 1 증가시킨다.
## 2-2. left[i] 가 0이 아니면 해당 토핑의 갯수만 1 증가.
# 3. 철수와 동생이 갖고있는 토핑 종류가 같으면 카운트를 증가시킨다.
public static int solution(int[] topping) {
int answer = 0;
// topping 의 원소는 10000 이하 이므로 배열의 길이는 10001
int[] left = new int[10001];
int[] right = new int[10001];
// 왼쪽의 토핑 갯수
int leftTopping = 0;
// 오른쪽의 토핑 갯수
int rightTopping = 0;
// i 번 토핑이 나타난 횟수
for(int i : topping){
right[i]++;
}
// 오른쪽에 모든 토핑 있다고 가정
for(int i : right){
if(i>0){
rightTopping+=1;
}
}
// 어차피 왼쪽(철수)에게만 토핑이 추가됨
// 토핑이 i면, 오른쪽에 있는 토핑 정보에서 i번째 인덱스를 감소시켜줌 (토핑 갯수 하나 줄어듬)
// 감소시킬 때, right[i] 가 0이면 오른쪽에도 i 토핑이 없는 것. -> right 가 갖고있는 토핑 종류가 하나 줄어듬
// left[i] 가 0이였으면, left 에 해당 토핑이 없었다는 것임. 따라서 토핑 갯수 1개 늘어남
// left[i] 에 i 토핑이 1개 추가됨
// left 토핑 갯수 == right 토핑 갯수 이면 카운트 증가가
for(int i : topping) {
right[i]--;
if (right[i] == 0) {
rightTopping--;
}
if (left[i] == 0) {
leftTopping++;
}
left[i]++;
if (rightTopping == leftTopping) {
answer++;
}
}
return answer;
}
완전 탐색 풀이 실행시간
DP 풀이 실행시간
차이가 너무크다. 멍충멍충