참고
문제해설
NOTE
•
입력 값 ⇒ 정수 배열의 어린이 등급
•
출력 값 ⇒ 모든 어린이에게 줄 수 있는 사탕의 최소개수
•
각 어린이는 최소 하나의 사탕을 가져야 하며, 높은 평가를 받은 어린이는 이웃보다 더 많이 받아야한다.
문제 로직고민
NOTE
•
가장 간단한 방법은 순차적으로 사탕의 개수를 맞춰나가는 것이다.
◦
배열을 순회하면서 다음 어린아이가 나보다 등급이 높으면 1을 증가시킨다.
◦
만약 다음 어린아이가 나보다 등급이 낮거나 같으면 1개만 준다.
◦
하지만 만약 내가 1이라면? ⇒ idx를 역순회하며 감소하는 값이 나오기전까지 +1해야한다.
◦
단 증가하는 경우에도 사탕의 개수가 차이가나면 +1을 생략해야 한다.
작성코드
NOTE
class Solution {
public int candy(int[] ratings) {
int result = 1;
int[] candy = new int[ratings.length];
candy[0] = 1;
for(int i = 1; i < ratings.length; i++){
candy[i] = 1;
// 다음 어린아이가 더 등급이 높다 => 1개더줌
if(ratings[i-1] < ratings[i]){
candy[i] = candy[i-1] + 1;
}
// 다음 어린아이가 더 등급이 낮거나 같다 => 1개만줌 (왤케 인성질같지?)
if(ratings[i-1] >= ratings[i]){
// 1개만 주려니 이전 어린아이가 등급이 더 높은데 1개임
if(candy[i-1] == 1){
// 등급과 캔디를 고려해서 이전 캔디를 수정함
for(int j = 0; i-j-1 >= 0; j++){
if(ratings[i-j-1] > ratings[i-j] && candy[i-j-1] <= candy[i-j]){
candy[i-j-1] += 1;
result++;
}
else break;
}
}
}
result += candy[i];
System.out.println(candy[i]);
}
return result;
}
}
Java
복사
정답코드
NOTE
class Solution {
public int candy(int[] ratings) {
int[] cendies = new int[ratings.length];
// 모든 캔디를 1로 초기화
for(int i=0; i<cendies.length; ++i){
cendies[i]=1;
}
// 다음 어린이이가 등급이 높으면 이전 어린이의 캔디보다 1개더 준다.
for(int i=1; i<cendies.length; ++i){
if(ratings[i]>ratings[i-1]){
cendies[i]=cendies[i-1]+1;
}
}
// 내가 다음 어린이보다 등급이 높고, 캔디가 적다면?
// 그 아이의 캔디보다 1개더 가진다.
for(int i=cendies.length-2; i>=0; --i){
if(ratings[i]>ratings[i+1] && cendies[i]<cendies[i+1]+1){
cendies[i]=cendies[i+1]+1;
}
}
int sum=0;
for(int i=0; i<cendies.length; ++i){
sum+=cendies[i];
}
return sum;
}
}
Java
복사
실행시간을 가장 적게 사용하는 코드
•
로직은 내가 조금더 복잡하지만 그렇게 큰 차이가 나지 않는것같다.
•
해당 코드가 9ms이고 내 코드가 599ms인데 아무래도 2번째 if로직에서 시간이 너무 걸렸던거 같다.
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] lr = new int[n];
int[] rl = new int[n];
for(int i=0;i<n;i++)
{
rl[i]=1;
lr[i]=1;
}
for(int i=1;i<n;i++)
{
if(ratings[i-1]<ratings[i])
lr[i]=lr[i-1]+1;
}
for(int i=n-2;i>=0;i--)
{
if(ratings[i+1]<ratings[i])
rl[i]=rl[i+1]+1;
}
int total = 0;
for(int i=0;i<n;i++)
{
total+=Math.max(rl[i],lr[i]);
}
System.gc();
return total;
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
메모리의 경우 3MB만 차이가나서 크게 참고할게 없는것같다.