티스토리 뷰
Algorithm/LeetCode
[LeetCode] 1493. Longest Subarray of 1's After Deleting One Element
Jaime.Lee 2023. 7. 29. 22:29Problem
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.
Example 1:
Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.
Example 2:
Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].
Example 3:
Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.
Constraints:
- 1 <= nums.length <= 10^5
- nums[i] is either 0 or 1.
Solution
0과 1로 이루어진 배열에서 하나를 제거해 가장 긴 1로 된 부분 배열의 길이를 구하는 문제입니다.
public class Solution {
public int longestSubarray(int[] nums) {
int start = 0, end = 0, zeroes = 0;
while (end < nums.length) {
if (nums[end] == 0) {
zeroes++;
}
end++;
if (zeroes > 1) {
if (nums[start] == 0) {
zeroes--;
}
start++;
}
}
return end - start - 1;
}
}
이전에 다뤘던 문제와 매우 유사합니다.
다른 점이 있다면 이전 문제는 k개의 0을 1로 치환할 수 있었던 반면, 이 문제는 1개의 원소를 반드시 삭제해야 합니다.
반대로 얘기하면 0 1개를 치환할 수 있다고 가정하고 결과에서 1을 빼주면(원소를 삭제하기 때문) 원하는 결과를 얻을 수 있습니다.
Test
package io.lcalmsky.leetcode.longest_subarray_of_1s_after_deleting_one_element;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertEquals;
class SolutionTest {
@Test
void testAll() {
assertAll(
() -> test(new int[]{1, 1, 0, 1}, 3),
() -> test(new int[]{0, 1, 1, 1, 0, 1, 1, 0, 1}, 5),
() -> test(new int[]{1, 1, 1}, 2)
);
}
private void test(int[] nums, int expected) {
// when
Solution solution = new Solution();
int actual = solution.longestSubarray(nums);
// then
assertEquals(expected, actual);
}
}
'Algorithm > LeetCode' 카테고리의 다른 글
[LeetCode] 2390. Removing Stars From a String (0) | 2023.07.31 |
---|---|
[LeetCode] 2352. Equal Row and Column Pairs (0) | 2023.07.30 |
[LeetCode] 1004. Max Consecutive Ones III (0) | 2023.07.28 |
[LeetCode] 1456. Maximum Number of Vowels in a Substring of Given Length (0) | 2023.07.27 |
[LeetCode] 155. Min Stack (0) | 2023.07.22 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- leetcode
- 스프링 부트 튜토리얼
- proto3
- gRPC
- 헥사고날 아키텍처
- 스프링 부트
- 스프링 데이터 jpa
- intellij
- Java
- r
- spring boot application
- 함께 자라기
- 스프링부트
- spring boot jwt
- Spring Data JPA
- Spring Boot JPA
- @ManyToOne
- 스프링 부트 회원 가입
- Spring Boot Tutorial
- JSON
- Linux
- JPA
- 스프링 부트 애플리케이션
- spring boot app
- Spring Boot
- 함께 자라기 후기
- QueryDSL
- 클린 아키텍처
- Jackson
- 알고리즘
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
글 보관함