소요 시간 : 1시간
문제를 읽고 문제의 풀이를 찾아 정리하는데 40분 정도 걸렸습니다. 정리가 되니
코드 작성은 오래 걸리지 않았습니다.
일단
제한사항부터가 백만입니다. 이중 for문은 사실 아예 안된다고 생각하고 접근했습니다.’
제가 생각한 문제의 포인트는 첫번째 무조건 두 조각으로 잘라야 한다는 점, 두번째로는 가짓수 였습니다.
아이디어는 이렇습니다.
인덱스 별로 가짓수를 저장하는 배열을 2개 생성합니다.
A 라는 인덱스는 topping list의 맨 처음부터 시작합니다.
B 라는 인덱스는 topping list 의 맨 마지막 부터 시작합니다.
HashMap을 통해 가짓수를 배열에 담습니다. (코드를 보시거나 아래 풀이를 보시면 이해가 되실 겁니다.)
A,B 중 A 인덱스만 for문을 돌리고 a[i] == b[i+1] 이 같으면 answer의 값을 +1 해줍니다.
왜 a[i] == b[i+1] 냐면 절반을 나눌 때 A 케이크의 끝 인덱스가 I 라면 B는 I+1 인덱스이며 가짓수가 같다면
곧 둘다 토핑을 똑같은 종류로 먹을 수 있다는 점입니다. 풀이와 코드 올리겠습니다.
package Question;
import java.util.HashMap;
/**
* 프로그래머스 롤케이크 자르기
* 아이디어
* 1. 인덱스별로 가지수를 저장하는 배열 2개를 만들어준다.
* 2. a 배열은 맨 처음 0번 인덱스 부터 시작한다.
* 3. b 배열은 topping list 의 길이-1 인덱스 즉 맨 마지막 인덱스 부터 시작해서 가지수를 저장한다.
* 4. 시간복잡도는 3번만 for문을 돌리면 되어서 3 * n 이며 상수를 제외하니 빅오는 O(n) 이 된다.
* */
public class CuttingRollCake {
public static void main(String[] args) {
}
public static int solution(int[] topping) {
int answer = 0;
int[] a = new int[topping.length];
int[] b = new int[topping.length];
// 가지수 측정을 위한 HashMap을 하나 만들자.
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < topping.length; i++) {
if(hashMap.isEmpty() || !hashMap.containsKey(topping[i])){
hashMap.put(topping[i], topping[i]);
}
// 가지수 만큼 반복
a[i] = hashMap.size();
}
hashMap = new HashMap<>();
for (int i = topping.length-1; i > 0; i--) {
if(hashMap.isEmpty() || !hashMap.containsKey(topping[i])){
hashMap.put(topping[i], topping[i]);
}
// 가지수 만큼 반복
b[i] = hashMap.size();
}
for (int i = 0; i < a.length-1; i++) {
if(a[i] == b[i+1]) answer++;
}
return answer;
}
}
