코로나로 카페도 폐쇄되고 아이둘을 데리고 나갈만한 곳이 없다.
겨울동안 주말에만 잠깐 쉬어가는 나의 텐트 2동 설치 완료.
벌써 90일 캠핑이 끝났구나~
사이즈가 1인경우
사이즈가 2이고 left = 0, right =1 인경우
사이즈가 3이고 left = 0 right =2 인경우
String s = "abac";
boolean[][] table = new boolean[s.length()][s.length()];
for(int i=0; i<s.length(); i++){
table[i][i] = true;
}
for(int size=2; size<s.length(); size++){
for(int left=0; left<s.length(); left++){
int right= left+size-1;
if(right >= s.length()){
continue;
}
if( size == 2){
table[left][right] = s.charAt(left) == s.charAt(right);
}else{
table[left][right] = s.charAt(left) == s.charAt(right) && table[left+1][right-1];
}
}
}
https://leetcode.com/problems/distribute-candies/
처음 생각해낸 방법은
두개의 priority qeue 를 생성해서 하나는 asc, 하는 desc 로 생성
sister 가 asc에서 한개씩 빼고, brother가 desc에서 큰 순으로 하나씩 빼다보면 최대 개수가 나올것 같다고 생각이 들었음.
코딩하기 귀찮아서 다른 방법 생각해보니 유니크한 사탕의 종류의 개수에 따라서 간단히 풀수 있었음.
O(N)
종류개수 > length/2 return length/2, else 종류개수
Runtime: 14 ms, faster than 96.34% of Java online submissions for Distribute Candies.
class Solution {
public int distributeCandies(int[] candies) {
int [] map = new int[200001];
int kinds = 0;
for(int i=0; i<candies.length; i++){
if(map[candies[i]+100000] == 0){
kinds ++;
}
map[candies[i]+100000]++;
}
int maxLen = candies.length/2 ;
return kinds <= maxLen ? kinds : maxLen;
}
}