휴가 중에 잠시 짬을 내서 풀어보는 리트코드 75 문제… 19일째 연속 포스팅인데 내일이 고비가 될 것 같다. 더 이상은 문제를 봐도 감이 오지 않기 때문에..😅 슬라이딩 윈도 3 문제를 풀어봤는데, 두 번째, 세 번째 문제는 거의 같은 문제라고 봐도 될 거 같았다.
1456. Maximum Number of Vowels in a Substring of Given Length
주어진 문자열 s와 정수 k가 있을 때, 길이가 k인 s의 부분 문자열 중 모음 개수를 가장 많이 가지는 경우를 구하라.
Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.
내가 문제를 풀었던 아이디어는 먼저 길이가 k인 부분 문자열(0, k-1)을 첫 번째 문자부터 만든다. 그리고 k개 문자열의 첫 번째 문자를 삭제하면서 모음인지 확인하고, 모음이면 카운트를 줄인다. 그리고 다음 부분 문자열에 추가될 문자가 모음인지 확인하고, 모음이면 카운트를 증가한다. 이런 식으로 길이가 k인 부분 문자열을 유지하면서 모음이 가장 많이 나오는 경우를 max에 저장하면 된다.
class Solution {
public int maxVowels(String s, int k) {
int cnt=0;
for(int i=0; i<k; i++) {
char c = s.charAt(i);
if (isVowel(c)) {
cnt++;
}
}
int max=cnt;
for(int i=1,j=k; j<s.length(); i++,j++) {
char cAtI = s.charAt(i-1), cAtJ = s.charAt(j);
if (isVowel(cAtI)) {
cnt--;
}
if (isVowel(cAtJ)) {
cnt++;
}
max = Math.max(max, cnt);
}
return max;
}
private boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
}시간복잡도는 처음 반복문에서 k만큼 돌고 다음 반복문에서 n-k만큼 돌기 때문에 O(n)이 된다. 공간 복잡도는 O(1)
1004. Max Consecutive Ones III
주어진 이진 배열 nums와 정수 k가 있을 때, 많아야 k개의 0을 1로 뒤집을 수 있을 때 연속적으로 오는 1의 최대 길이를 구하라.
Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.
값이 1인 경우 queue에 추가하고, 0인 경우 flip 횟수를 기록하여 k번 이하로 flip 한 경우만 queue에 추가한다. 만약 flip 횟수가 k와 같아지면 더 이상 0을 추가할 수 없기 때문에 queue에서 0이 나올 때까지 queue의 원소를 빼고, 현재 위치의 0을 추가한다.
class Solution {
public int longestOnes(int[] nums, int k) {
int max=0, flip=0;
Queue<Integer> q = new LinkedList<>();
for(int i=0; i<nums.length; i++) {
if (nums[i] == 1) {
q.offer(nums[i]);
} else if (flip + 1 <= k) {
q.offer(nums[i]);
flip++;
} else if (!q.isEmpty()) {
int val = q.poll();
// val == 1
while(val == 1 && !q.isEmpty()) {
val = q.poll();
}
if (val == 0) {
q.offer(nums[i]);
}
}
max = Math.max(max, q.size());
}
return max;
}
}시간 복잡도는 [1, 1, 1, 1, 0], k=0 일 때 queue의 1을 모두 뺄 수 있는데 그래도 최대 O(2n) 만큼 루프를 순회할 것이라 시간 복잡도는 O(n)이 될 것 같다. 그리고 공간 복잡도는 queue를 사용하기 때문에 O(n)이다. 내가 제출한 솔루션보다 빠른 솔루션이 매우 많이 때문에, 최적의 솔루션이 어떤 것인지 다시 확인이 필요할 것 같다.
1493. Longest Subarray of 1's After Deleting One Element
주어진 이진 배열 nums가 있을 때, 그중에서 한 개 원소를 제거해야 한다. 이때 1만 가지는 부분 배열 중 가장 길이가 긴 값을 구하라.
Given a binary array nums, you should delete one element from it.
Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.
이 문제는 Max Consecutive Ones III 문제에서 k=1로 고정한 것과 같은 문제이다. flip을 한 번 해서 구할 수 있는 가장 긴 1의 부분 배열 길이를 구했을 때, 반드시 한 개 원소를 제거해야 하므로 그 값에서 -1을 해주면 된다. 문제가 유사하기 때문에 코드도 위의 것과 거의 같다.
class Solution {
public int longestSubarray(int[] nums) {
int max=0, flip=0;
Queue<Integer> q = new LinkedList<>();
for(int i=0; i<nums.length; i++) {
if (nums[i] == 1) {
q.offer(nums[i]);
} else if (flip == 0) {
q.offer(nums[i]);
flip++;
} else if (!q.isEmpty()) {
int val = q.poll();
while(val == 1 && !q.isEmpty()) {
val = q.poll();
}
if (val == 0) {
q.offer(nums[i]);
}
}
max = Math.max(max, q.size());
}
return max-1;
}
}시간 복잡도, 공간 복잡도도 동일하다.
