프로그래머스 - 롤케이크 자르기
오늘은 프로그래머스 2단계 롤케이크 자르기를 풀어보겠습니다.
문제 설명을 간단하게 하겠습니다.
※ 문제 설명을 아는 분들은 스킵하셔도 됩니다!
문제 설명
- 철수는 롤케이크를 남은 부분 없이 두 조각으로 잘라 동생과 공평하게 나누어 먹으려고 합니다.
- 롤케이크에는 여러가지 토핑이 올려져 있습니다.
-> 롤케이크에 올려져 있는 모든 토핑을 저장한 배열이 'topping'입니다.- 롤케이크를 두 조각으로 자를 때, 철수와 동생의 조각 케이크에는 각각 '토핑의 종류의 개수가 동일'해야 합니다.
-> '토핑의 개수'가 달라도 '토핑의 종류의 개수'가 같다면 됩니다.- 이와 같은 방법으로 철수와 동생이 '롤케이크를 공평하게 나누는 방법의 수'를 반환합니다.
문제의 핵심은 '롤케이크를 자를 때, 철수와 동생의 조각 케이크의 토핑의 종류의 개수가 동일해야 한다.' 입니다.
예시
입출력 예제 1번을 보며 설명하겠습니다.
-
주어진 토핑의 종류는 1, 2, 3, 4로 4가지 입니다.
-
철수의 조각 케이크에 [ 1, 2, 1, 3 ], 동생의 조각 케이크에 [ 1, 4, 1, 2 ]의 토핑이 있을 때, 각자의 조각 케이크에 토핑의 종류가 3개 씩 있으므로 공평하게 나누었습니다.
-
철수의 조각 케이크에 [ 1, 2, 1, 3, 1 ], 동생의 조각 케이크에 [ 4, 1, 2 ]의 토핑이 있을 때, 각자의 조각 케이크에 토핑의 종류가 3개 씩 있으므로 공평하게 나누었습니다.
-
더 이상 방법이 없으므로, 롤케이크를 공평하게 나누는 방법이 두 가지이므로 '2'를 반환합니다.
풀이
다른 분들의 코드를 보니 HashMap으로 많이 하셨더라구요. 프로그래머스에서 메모리 제한으로 실패하는 경우는 못봐서 배열로 메모리를 매우 크게 잡는 대신, 매우 쉽게 푸는 방법을 알려드리려고 합니다.
사실 난이도 차이도 크게 안나는 쉬운 문제라..
※ 제가 푼 방법보다 더 좋은 방법으로 풀 수 있기 때문에, 참고용으로만 봐주셨으면 좋겠습니다.
오늘은 더더욱 참고용!!
- 모든 토핑을 동생의 조각 케이크에 넣고, 토핑을 하나 씩 가져와 동생의 케이크에서는 토핑을 빼고, 철수의 케이크에 추가하는 방법을 사용할 겁니다.
-
롤케이크에 올라갈 수 있는 토핑의 종류에는 10,000가지가 있습니다.
- 길이가 10,001인 철수와 동생의 조각 케이크 배열을 각각 만듭니다.
- '조각 케이크 배열'의 index가 의미하는 것은 토핑의 종류이고, 해당 index의 값은 해당 토핑의 개수입니다.
-
철수와 동생의 조각 케이크에 있는 토핑의 종류의 개수를 담는 변수를 각각 만듭니다.
-
롤케이크에 있는 토핑을 모두 '동생의 조각 케이크 배열'에 넣습니다.
- 동생의 조각 케이크 배열[토핑의 종류] += 1
- 여기서 만약, 동생의 조각 케이크 배열에 '새로운 종류의 토핑'이 들어갈 경우,
2번에서 만든 동생의 조각 케이크에 있는 토핑의 개수의 종류에 1을 더합니다.
-
반복문을 반복하여 'topping[i]'의 값을 '철수의 조각 케이크 배열'에 추가하고, '동생의 조각 케이크 배열'에서 1을 감소시킵니다.
- '동생의 조각 케이크 배열[i] = 0'이라면 '동생의 토핑 종류의 개수'를 1 감소시킵니다.
- topping[i]를 '철수의 조각 케이크 배열'에 추가하기 전에,
'철수의 조각 케이크 배열[i] = 0'이라면 '철수의 토핑의 종류의 개수'를 1 증가시킵니다.
-
'철수의 토핑 종류의 개수'와 '동생의 토핑 종류의 개수'가 같다면, 방법의 수를 1 증가시킵니다.
-
'동생의 토핑 종류의 개수'보다 '철수의 토핑 종류의 개수'가 더 많다면, 반복문을 중단합니다.
-
'방법의 수'를 반환합니다.
코드
class Solution {
public int solution(int[] topping) {
// 동생과 철수의 조각 케이크 배열
int[] brotherArr = new int[10001];
int[] cheolSooArr = new int[10001];
// 동생과 철수의 토핑 종류의 개수
int brother = 0;
int cheolSoo = 0;
// 방법의 수
int answer = 0;
for(int i : topping)
{
// '새로운 토핑 종류'라면 '동생의 조각 케이크 토핑 종류'를 '1' 증가
if(brotherArr[i] == 0)
brother++;
// 동생 조각 케이크 배열[토핑 종류]의 값 '1' 증가
brotherArr[i]++;
}
// '동생의 토핑 종류'보다 '철수의 토핑 종류'가 많다면 반복문 종료
for(int i = 0; cheolSoo <= brother; i++)
{
int t = topping[i];
// 동생의 조각 케이크에서 해당 토핑의 빼기
brotherArr[t]--;
// 동생이 해당 토핑을 철수에게 전부 주었다면, '동생의 토핑 종류' '1' 김소
if(brotherArr[t] == 0)
brother--;
// 철수가 해당 토핑을 처음 얻었다면 '철수의 토핑 종류' '1' 증가
if(cheolSooArr[t] == 0)
cheolSoo++;
// 철수의 조각 케이크에서 해당 토핑 더하기
cheolSooArr[t]++;
// '동생의 토핑 종류'와 '철수의 토핑 종류'가 같다면 방법의 수 '1' 증가
if(brother == cheolSoo)
answer++;
}
return answer;
}
}테스트
topping을 만들어 주는 코드입니다. 해당 클래스를 이용해서 본인 코드와 정답 코드의 반환 값이 같은지 확인하시면 됩니다.
import java.util.Random;
class Source
{
Random random;
int[] topping;
Source()
{
random = new Random();
topping = new int[random.nextInt(1_000_000)+1];
setTopping();
}
public void setTopping()
{
for(int i = 0; i < topping.length; i++)
{
topping[i] = random.nextInt(10_000)+1;
}
}
}#썸네일 제작 : 미리 캔버스
