첫날이니 문제 패턴들 별로 리마인드 하는 느낌으로 풀어봤다. 풀어본 문제인데 풀 때마다 새로운 느낌은 왜인지 🤣
그렇지만 한번 더 풀어보니 내가 어떤 패턴에 약한지 조금 알게 되었다. Two pointers 패턴의 문제인지 파악하거나 코드를 짜는데 익숙하지 않은 것 같아서 연습을 더 해보려고 한다.
Array/String > 1768. Merge Strings Alternately
먼저 문제를 읽어보자. 주어진 두 문자열 word1, word2를 합치는데 문자가 번갈아가면서 나오도록 해야한다. 그리고 시작은 word1부터 한다. 그리고 둘 중 하나의 문자열이 더 길다면 머지된 문자열 뒤에 나머지를 붙인다.
You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.
Return the merged string.
문제가 직관적이라서 바로 구현에 들어간다. 1번 반복문에서 문자열을 번갈아가면서 머지하고, 2번, 3번 반복문은 한쪽 문자열이 더 길어서 남은 경우 뒤에 붙여주게 된다. 1번 반복문을 탈출했을 때 2번, 3번 반복문은 둘 중 하나만 돌기 때문에 순서는 중요하지 않다.
class Solution {
public String mergeAlternately(String word1, String word2) {
StringBuilder sb = new StringBuilder();
int i1=0, i2=0;
while (i1 < word1.length() && i2 <word2.length()) { // 1
sb.append(word1.charAt(i1));
sb.append(word2.charAt(i2));
i1++;
i2++;
}
while (i1 < word1.length()) { // 2
sb.append(word1.charAt(i1));
i1++;
}
while (i2 < word2.length()) { // 3
sb.append(word2.charAt(i2));
i2++;
}
return sb.toString();
}
}솔루션의 시간 복잡도를 계산하면 word1의 길이를 m, word2의 길이를 n이라고 했을 때 두 문자열 모두 순회를 해야 하기 때문에 O(m + n)이다. 공간 복잡도는 두 문자열을 합치기 때문에 마찬가지로 O(m + n)이다. (아직은 여유 있게 계산하는데 과연?!)
Two pointers > 283. Move Zeroes
문제는 간결하지만 내가 약한 투포인터 문제다.
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
주어진 숫자 배열에서 0을 모두 뒤로 옮기는데 기존 0이 아닌 숫자들의 순서는 유지해야한다. 그리고 in-place - 기존 배열을 사용해서 옮겨야 한다.
이 문제를 바꿔서 말하면 0이 아닌 숫자를 모두 앞으로 옮기면, 나머지는 0으로 채워도 상관없다는 뜻이다. 그래서 첫 반복문에서 0이 아닌 값들을 채우고, 두 번째 반복문에서 index 'zero'부터 끝까지 0으로 채워준다.
'zero'를 0부터 시작하면 0이 아닌 값을 만날 때마다 앞에서부터 덮어쓰기 때문에 유실될 염려는 없다.
class Solution {
public void moveZeroes(int[] nums) {
int zero = 0;
for(int i=0; i<nums.length; i++) {
if (nums[i] != 0) {
nums[zero] = nums[i];
zero++;
}
}
for(; zero<nums.length; zero++) {
nums[zero] = 0;
}
}
}시간 복잡도는 nums 배열의 길이를 n이고, 0인 원소가 k개 있다고 할 때, O(n + n-k) = O(n)이다. 공간 복잡도는 in-place라서 O(1)이다.
Sliding window > 643. Maximum Average Subarray I
슬라이딩 윈도우 문제. 워밍업으로 좋다
You are given an integer array nums consisting of n elements, and an integer k.
Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.
연속된(contiguous) k개의 원소로 구성된 부분 배열(subarray) 중 최대 평균값을 구하는 문제다. 평균값은 k로 나누면 구할 수 있는 거니까 결국 k개 원소를 가지는 부분 배열 중 최댓값을 찾아야 한다. 0번째 원소부터 k-1까지 합을 구하고, 왼쪽으로는 원소를 빼고, 오른쪽으로는 더하면 (연속된) 부분 배열을 움직이면서 값을 구할 수 있다.
class Solution {
public double findMaxAverage(int[] nums, int k) {
double sum = 0.0;
for(int i=0; i<k; i++) {
sum += nums[i];
}
double max = sum;
for(int i=0; i+k<nums.length; i++) {
double next = sum - nums[i] + nums[i+k];
if (max < next) {
max = next;
}
sum = next;
}
return max / k;
}
}0부터 k-1까지 합을 구하는데 O(k), 부분합을 이동하는데 O(n-k)라서 결국 시간복잡도는 O(n)이다. 공간복잡도는 상수개 변수만 선언했기 때문에 O(1)이다.
문제 난이도가 Easy인 것들만 풀었는데도 말로 설명하려니 시간이 많이 걸리는 것 같다. 앞으로 점점 더 힘들어지겠지만 포기하지 말자.
