[NeetCode-LeetCode] Consecutive Sequence - Medium
접근
- TreeSet
- stream
풀이
배열의 원소 내에 연속된 수열이 존재하는지 찾고 존재한다면 수열의 길이가 최대 길이가 몇 인지 반환하는 문제이다. 우선 배열은 정렬되지 않고 원소의 중복이 존재하는 형태로 주어지는 것 같다. 그렇기 때문에 편하게 해결하기 위해선 중복과 정렬을 수행해주어야 하는데 중복과 정렬이라고 하니 TreeSet이 생각이 나 사용해 봤다.
TreeSet은 Set과 같이 중복된 원소를 포함하지 않는 자료구조인데 HashSet과의 차이점으론 내부적으로 Tree 구조를 사용해 원소를 저장하므로 원소들이 자동으로 정렬된 상태로 관리된다. 이는 원소가 삽입될 때 Tree의 적당한 위치에 배치되기 때문인데 TreeSet을 사용하게 된다면 정렬과 중복을 한 번에 해결 가능하기 때문에 사용해 봤다.
public int longestConsecutive(int[] nums) {
if(nums.length == 0) return 0;
TreeSet<Integer> set = new TreeSet<>();
for (int num : nums) {
set.add(num);
}
int maxLength = 1;
int currentMax = 1;
Iterator<Integer> itr = set.iterator();
int prev = itr.next();
while(itr.hasNext()){
int current = itr.next();
if(current == prev + 1){
currentMax++;
} else {
currentMax = 1;
}
maxLength = Math.max(maxLength, currentMax);
prev = current;
}
return maxLength;
}배열의 원소들을 TreeSet에 넣어준 뒤 iterator를 통해 원소에 접근해 준다. HashSet이었다면 순서가 보장되지 못한 채로 접근이 되겠지만 TreeSet을 사용하였기 때문에 정렬된 상태로 원소에 접근이 가능하다. 그렇게 이전 값을 보관하며 정렬되어 연속된 두 개의 원소를 비교하며 수열을 만족한다면 길이를 증가시켜 주고 만족하지 못한다면 새로운 수열을 시작하게 된다.
Stream
위에서의 정렬과 중복 제거를 stream을 사용해 수행해 주는 방법이다. stream을 사용하게 되면 기존 배열의 구조로 나머지 로직 수행이 가능하기 때문에 TreeSet을 사용하는 것보다 좀 더 빠른 성능을 보였다.
public int longestConsecutive(int[] nums) {
if(nums.length == 0) return 0;
int[] newArr = Arrays.stream(nums).sorted().distinct().toArray();
int maxLength = 1;
int current = 1;
for (int i = 1; i < newArr.length; i++) {
if (newArr[i] == newArr[i - 1] + 1) {
current++;
} else {
current = 1;
}
maxLength = Math.max(maxLength, current);
}
return maxLength;
}stream의 sorted()를 통해 정렬해 주고 distinct()를 통해 중복을 제거한 뒤 배열로 반환해 주었다. 나머지 과정은 위와 동일하나 배열의 인덱스를 통해 바로 접근할 수 있기 때문에 반복문의 시작을 1부터 시작해 주어 이전 원소와 비교하게 해 주었다.
나머지 비슷한 코드들도 정렬 후 중복을 제거하고 체크하는 방식은 유사하나 stream 대신 직접 처리를 해주는 코드였다.
범위 기반 접근
제일 성능이 좋았던 코드로 배열의 길이가 10000 이하 일 경우 정렬을 사용한 방식으로 수행하고 그 이상일 경우 범위 기반으로 접근하는 방식이었다. 효율성을 높이기 위해 정렬에 시간이 많이 소요되는 시점부터는 정렬을 하지 않고 진행하는 방법으로 신기한 방법이었다.
public int longestConsecutive(int[] nums) {
if(nums.length == 0)return 0;
if(nums.length < 10000){
Arrays.sort(nums);
int longest = 0;
int current = 0;
int prev = nums[0] - 2;
for(int num : nums){
if(num == prev)continue;
if(num - prev == 1){
current += 1;
}
else{
longest = Math.max(longest, current);
current = 1;
}
prev = num;
}
return Math.max(longest, current);
}해당 부분은 정렬을 통해 수행하는 방법으로 이전 코드들과 거의 동일한 내용의 로직이다.
else{
int min = nums[0];
int max = nums[0];
for(int num : nums){
if(num < min){
min = num;
}
else if(num > max){
max = num;
}
}
int range = max - min + 1;
boolean[] isObserved = new boolean[range + 1];
for(int num : nums){
int index = (num - min);
isObserved[index] = true;
}
int longest = 0;
int current = 0;
for(boolean _isObserved : isObserved){
if(_isObserved){
current += 1;
}
else{
longest = Math.max(longest, current);
current = 0;
}
}
return Math.max(longest, current);
}
}이 부분이 범위 기반 접근을 통해 해결하는 코드인데 배열을 돌며 최댓값과 최솟값을 구한 뒤 해당 범위 안에서만 체크를 하는 방법이었다. 즉 배열의 크기가 100000으로 크더라도 내부 원소 중복이 가능하여 실제 배열 내 숫자의 범위는 0~9 정도밖에 안 될 수도 있다. 그런 경우 크기 100000의 배열을 여러 번 반복하는 처리는 매우 비효율적으로 범위 내의 숫자를 담을 수 있는 크기의 배열을 따로 만들어 실제 값 범위에서 처리를 하게 되는 것이다. 즉 100000 크기의 배열을 10 크기의 배열로 변경해 처리하는 방법이다. 여기서는 원본 배열에 존재하는 최대 최소 값을 기준으로 실제 수열의 길이만큼 boolean 배열을 만들고 실제 최솟값을 boolean 배열 0번 인덱스에 매칭시키고 최댓값을 boolean 배열의 마지막 인덱스에 매칭시켜 범위 내 원소들이 존재한다면 true로 표시하여 체크한 뒤 boolean 배열을 다시 순회하며 최대 수열의 길이를 구하게 된다.
배열의 크기가 작다면 굳이 싶은 방법이라 기준점인 10000을 기준으로 큰 경우에만 적용해 주었는데 중복된 원소가 많은 큰 배열에선 상당히 효율적으로 수행되는 방법인 것 같다.
전체 코드
TreeSet
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length == 0) return 0;
TreeSet<Integer> set = new TreeSet<>();
for (int num : nums) {
set.add(num);
}
int maxLength = 1;
int currentMax = 1;
Iterator<Integer> itr = set.iterator();
int prev = itr.next();
while(itr.hasNext()){
int current = itr.next();
if(current == prev + 1){
currentMax++;
} else {
currentMax = 1;
}
maxLength = Math.max(maxLength, currentMax);
prev = current;
}
return maxLength;
}
}
stream
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length == 0) return 0;
int[] newArr = Arrays.stream(nums).sorted().distinct().toArray();
int maxLength = 1;
int current = 1;
for (int i = 1; i < newArr.length; i++) {
if (newArr[i] == newArr[i - 1] + 1) {
current++;
} else {
current = 1;
}
maxLength = Math.max(maxLength, current);
}
return maxLength;
}
}
범위 기반
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length == 0)return 0;
if(nums.length < 10000){
Arrays.sort(nums);
int longest = 0;
int current = 0;
int prev = nums[0] - 2;
for(int num : nums){
if(num == prev)continue;
if(num - prev == 1){
current += 1;
}
else{
longest = Math.max(longest, current);
current = 1;
}
prev = num;
}
return Math.max(longest, current);
}
else{
int min = nums[0];
int max = nums[0];
for(int num : nums){
if(num < min){
min = num;
}
else if(num > max){
max = num;
}
}
int range = max - min + 1;
boolean[] isObserved = new boolean[range + 1];
for(int num : nums){
int index = (num - min);
isObserved[index] = true;
}
int longest = 0;
int current = 0;
for(boolean _isObserved : isObserved){
if(_isObserved){
current += 1;
}
else{
longest = Math.max(longest, current);
current = 0;
}
}
return Math.max(longest, current);
}
}
}'알고리즘 > 코딩테스트-NeetCode' 카테고리의 다른 글
| [NeetCode-LeetCode] Subtree of Another Tree JAVA (0) | 2025.01.01 |
|---|---|
| [NeetCode-LeetCode] Find Minimum in Rotated Sorted Array JAVA (0) | 2024.12.31 |
| [NeetCode-LeetCode] Top K Frequent Elements JAVA (1) | 2024.12.28 |
| [NeetCode-LeetCode] Group Anagrams JAVA (1) | 2024.12.27 |
| [NeetCode-LeetCode] Missing Number JAVA (1) | 2024.12.19 |