문제풀이 3일 차. 아직은 할만하지만 작심삼일의 그 삼일째다. 평소에 코틀린으로 대부분 개발하지만 코딩테스트는 자바를 사용한다. 자바로 된 코드는 대부분의 개발자가 읽을 수 있고, 함수 네이밍 컨벤션도 익숙해서 자동 완성이 없어도 잘 쓰는 편이다. 코틀린은 함수형이고 stdlib를 사용하면 메서드 하나로 풀 수 있는 문제들도 가끔씩 있다. 그 간결함이 오히려 개발자의 코드 구현 능력을 가릴 수 있는 것 같다. 오늘은 Array/String 2문제, Prefix Sum 1문제를 풀어봤다.
1431. Kids With the Greatest Number of Candies
n명의 아이들이 가진 캔디 수를 저장한 배열이 있고, extraCandies를 줬을 때 아이들 중에서 캔디를 가장 많이 가질 수 있다면 true, 아니라면 false를 저장한 배열을 리턴한다.
There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the ith kid has, and an integer extraCandies, denoting the number of extra candies that you have.
Return a boolean array result of length n, where result[i] is true if, after giving the ith kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.
Note that multiple kids can have the greatest number of candies.
먼저 가장 많은 캔디 수를 찾아서 max에 저장하고, 각 아이들의 캔디 수 + extraCandies가 max보다 크거나 같은지 확인한다.
class Solution {
public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
int max = getMax(candies);
List<Boolean> ret = new ArrayList<>();
for(int i=0; i<candies.length; i++) {
ret.add(max <= candies[i] + extraCandies);
}
return ret;
}
private int getMax(int[] candies) {
int max = candies[0];
for(int i=1; i<candies.length; i++) {
max = Math.max(max, candies[i]);
}
return max;
}
}시간 복잡도는 배열을 두 번 순회하므로 O(n), 공간 복잡도는 불린 값을 저장한 리스트가 필요해서 O(n)이다.
605. Can Place Flowers
flowerbed가 있고, 0은 빈 자리를, 1은 꽃이 있는 자리를 나타낸다. 꽃은 빈자리에만 꽂을 수 있고 양 옆에는 꽃이 없어야 한다. 이때 n 개의 꽃을 심을 수 있다면 true를 리턴하고, 없다면 false를 리턴한다.
You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.
Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.
flowerbed를 돌면서 심으면 안되는 경우는 모두 패스하고, flowerbed[i]=1 할당하고(꽃을 심은 뒤), n을 1씩 빼준다. 그리고 n이 0 이하라면 심을 수 있다는 뜻이므로 n <= 0을 불린 값으로 리턴한다.
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
for(int i=0; i<flowerbed.length; i++) {
if (flowerbed[i] == 1) {
continue;
}
if (i-1 >=0 && flowerbed[i-1] == 1) {
continue;
}
if (i+1 < flowerbed.length && flowerbed[i+1] == 1) {
continue;
}
flowerbed[i] = 1;
n--;
}
return n <= 0;
}
}시간복잡도 O(m), 공간복잡도 O(1)
724. Find Pivot Index
pivot Index를 기준으로 왼쪽 부분 배열, 오른쪽 부분 배열 각각의 합이 같아지는 pivot Index를 찾고, 없으면 -1을 리턴한다.
Given an array of integers nums, calculate the pivot index of this array.
The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.
If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.
Return the leftmost pivot index. If no such index exists, return -1.
투포인터 패턴과 비슷하다고 생각해서 lsum(왼쪽 부분 배열 합), rsum(오른쪽 부분 배열 합)을 두고 인덱스를 이동하면서 부분 배열의 합을 비교하고자 했다. leftmost pivot index를 찾는 문제기 때문에 pivot index가 0일 때의 부분합으로 초기값을 잡고, pivot index의 이동에 따라 부분합을 적절히 계산해 줬다.
class Solution {
public int pivotIndex(int[] nums) {
int lsum=0;
int rsum=0;
for(int i=1; i<nums.length; i++) {
rsum += nums[i];
}
int idx=0;
do {
if (lsum == rsum) {
return idx;
}
lsum += nums[idx];
rsum = idx < nums.length -1 ? rsum - nums[idx+1] : 0;
idx++;
} while(idx < nums.length);
return -1;
}
}idx가 오른쪽 끝(nums.length -1)으로 갔을 때 rsum 계산에서 OutOfBound 예외가 발생되지 않도록 처리한다. 그러면 pivot index가 존재하는 경우는 do-while 문 안에서 처리가 가능하다. 그래서 do-while 문을 나오면 -1을 리턴한다.
시간 복잡도는 처음 rsum을 계산할 때 배열을 한 번 순회하고, 그다음 lsum을 계산하면서 배열을 한 번 더 순회하기 때문에 O(n), 공간 복잡도는 O(1)이다.
이제 내일부터는 미디엄 난이도를 하나씩 껴서 문제를 풀어봐야겠다.
