오늘 할일
1. LeetCode
오늘 한일
1. LeetCode
- Increasing Triplet Subsequence는 배열에서 연속된 3개의 인덱스가 하나라도 증가하면 true를, 그렇지 않으면 false를 반환하는 문제이다. 첫 시도는 3중 for문을 사용해 제출했는데 Time Limit Exeeded가 발생하였다.
public class Solution {
public boolean increasingTriplet(int[] nums) {
for(int i=0; i< nums.length-2; i++){
for(int j=i+1; j<nums.length-1; j++){
for(int k=j+1; k<nums.length; k++){
if(nums[i]<nums[j] && nums[j]<nums[k]){
return true;
} else{
}
}
}
}
return false;
}
}
복잡도 조건을 확인해보니
Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?
시간복잡도 O(n)에 공간복잡도 O(1)로 해결하라고 되어있었다. 추가적인 최적화가 필요해보인다.
최적화 시도
- 정렬하면서 수행되는 과정에서 문제를 해결해보면 어떨까 생각해봤는데 최악의 조건으로 복잡도가 가장 낮은게 힙정렬, 병합정렬 nlog2n으로 문제의 요구조건인 O(n)을 만족하지 못한다.
- Time Limit Exceeded가 발생한 예시를 보면, 연속된 값이 시간을 많이 잡아먹는 듯 하다. 연속된 수는 증가하는 조건에 만족되지 않기 때문에, 3번 초과로 연속된 원소를 3개로 줄이는 방식을 적용해보려 했다. 하지만 주어진 변수는 int[]꼴로 중간값을 변경하는 과정에서 많은 복잡도가 발생할 것으로 보여 시도하지 않았다.
- 이전의 최적화 시도와 같이 stream api를 사용해보기로 했다. 우선 Time Limit Exceeded가 api로 해결되는지를 확인하기 위해 시작부분에 .distinct로 중복을 무작정 제거하고 돌려보니 대부분의 테스트케이스를 통과했다.
- 문제를 잘못 구현한 것이 있었다. 연속된 index를 구하는 것이라면 for문을 하나만 사용하면 되는데 3개를 사용하여 연속이 아닌 i<j<k대소관계만을 확인해 조건에 만족하지 않는 index (예를 들어 1,2,4)까지도 탐색하였다. 해당 부분을 수정하여 제출했는데, 기존에 이해한 것이 맞는 듯 하다. [20, 100, 10, 12, 5, 13]에서 true를 반환해야한다.
- stream api를 사용하려 했는데, 연속적인 수를 처리하는데에 최적화되어 있기에 두번째 최적화 시도방법을 효율적으로 실제 구현해보려고 한다. 하지만 초기 배열을 전처리하려면 중복값들을 확인한 뒤 그 값을 실제 저장해야하는데 그 과정에서 공간복잡고 O(1)를 만족하지 못할 것 같다.
- 시간복잡도 O(n)을 위해서는 index table을 사용해야한다고 판단했다. 고로 아래와 같은 코드를 작성했다.
class Solution {
public boolean increasingTriplet(int[] nums) {
int size=nums.length;
Map<Integer, List<Integer>> index_table=new HashMap<>();//value와 indexList
for(int i=0; i<size; i++){
int value=nums[i];
if(!index_table.keySet().contains(value)){//현재 값이 key로 저장되어있지 않다면
List list=new ArrayList<Integer>();//새로운 리스트에
list.add(i);//index정보를 추가해서
index_table.put(value, list);//put
} else{//값이 이미 key로 존재한다면
index_table.get(value).add(i);//인덱스정보 추가
}
}
List<Integer> key_list=index_table.keySet().stream().toList();
for(int i=0; i< key_list.size()-2; i++){
int value1= key_list.get(i);
for(int j=i+1; j< key_list.size()-1; j++) {
int value2 = key_list.get(j);
for(int k=j+1; k<key_list.size(); k++) {
int value3 = key_list.get(k);
List indexes1 = index_table.get(value1);
List indexes2 = index_table.get(value2);
List indexes3 = index_table.get(value3);
int indexes1_max = (int) Collections.max(indexes1);
int indexes2_min = (int) Collections.min(indexes2);
int indexes2_max = (int) Collections.max(indexes2);
int indexes3_min = (int) Collections.min(indexes3);
if (indexes1_max < indexes2_min && indexes2_max < indexes3_min)
return true;
}
}
}
return false;
}
}
그 결과 기존 Time Limit Exceeded에러가 난 test case 32번을 통과하고 62번까지 진행된 것을 확인할 수 있었다.
해당 에러는 value들을 순차적으로 확인하기 이전에, 크기 순서대로 정렬이 되어있지 않아서 임을 확인할 수 있었다. 다음과 같이 sort코드를 추가한 뒤 에러가 발생했던 테스트 코드를 통과했다는 것을 확인했다.
하지만 다른 테스트 케이스에서 오류가 발생했다.
몇가지 조건을 보완한 후 제출해보았는데 Time Limit Exceeded가 다시 발생하였다.
최적화를 추가적으로 진행해야 할 듯 하다.
- 하지만 추가적인 최적화를 새로이 생각하기보다, 현재 Time Limit Exceeded가 발생한 테스트 케이스가 74/83으로 거의 통과했기에 해당 케이스를 예외처리하는 TDD방식으로 진행화는 것이 더 좋겠다고 생각하였다. 해당 케이스를 확인해보면 10000부터 내림차순으로 쭉 진행하는 케이스임을 알 수 있다. 해당 케이스를 예외처리하기 위해 전부 내림차순인 배열의 경우를 따로 확인하여 false를 리턴하는 코드를 추가작성하였다.
//74번 케이스를 위한 사전 체크
boolean isDescending=false;
for(int i=0; i<nums.length-1; i++){
if(nums[i]>nums[i+1]) {
isDescending = true;
} else {
isDescending=false;
break;
}
}
if(isDescending)
return false;
가장 오래걸린 문제가 아닐까 싶다. 이번 문제의 풀이는 좀 난잡하게 했기에 전체 알고리즘을 정리해보면 배열 원소를 기준으로 정렬한 다음 해당하는 인덱스들을 비교하는 방식으로 풀이하였다. 구체적인 접근방법은 아래와 같다.
- 배열의 원소를 키값으로, 배열 원소의 인덱스틑 값으로 가지는 Map<Integer, List>를 생성하여 O(n)의 시간복잡도를 가지는 색인 테이블을 만들었다.
int size=nums.length;
Map<Integer, List<Integer>> index_table=new HashMap<>();//value와 indexList
for(int i=0; i<size; i++){
int value=nums[i];
if(!index_table.keySet().contains(value)){//현재 값이 key로 저장되어있지 않다면
List list=new ArrayList<Integer>();//새로운 리스트에
list.add(i);//index정보를 추가해서
index_table.put(value, list);//put
} else{//값이 이미 key로 존재한다면
index_table.get(value).add(i);//인덱스정보 추가
}
}- 키값을 기준으로 오름차순 정렬하였다.
//(-3: 6) (-1: 5) (0: 0, 4) (1: 3) (2: 2) (4: 1) List<Integer> key_list=index_table.keySet().stream().sorted().collect(Collectors.toList()); - 내림차순 배열의 경우를 예외처리 하였다.
//74번 케이스를 위한 사전 체크 boolean isDescending=false; for(int i=0; i<nums.length-1; i++){ if(nums[i]>nums[i+1]) { isDescending = true; } else { isDescending=false; break; } } if(isDescending) return false; - 정렬된 값,인덱스 map에서 key3가지를 순차적으로 가져온 후 해당하는 3개의 인덱스 리스트를 저장한다. 그 후 인덱스들의 대소관계를 비교하여 작은 값의 인덱스 리스트에서 하나라도 큰 값의 인덱스 리스트보다 크다면 false를 리턴하게 처리하였다.
//본격 알고리즘
for(int i=0; i< key_list.size()-2; i++){
int value1= key_list.get(i);
for(int j=i+1; j< key_list.size()-1; j++) {
int value2 = key_list.get(j);
for(int k=j+1; k<key_list.size(); k++) {
int value3 = key_list.get(k);
List indexes1 = index_table.get(value1);
List indexes2 = index_table.get(value2);
List indexes3 = index_table.get(value3);
int indexes1_min= (int) Collections.min(indexes1);
int indexes1_max = (int) Collections.max(indexes1);
int indexes2_min = (int) Collections.min(indexes2);
int indexes2_max = (int) Collections.max(indexes2);
int indexes3_min = (int) Collections.min(indexes3);
if (indexes1_max < indexes2_min && indexes2_max < indexes3_min)
return true;
if (indexes1_min < indexes2_min && indexes2_min < indexes3_min)
return true;
if (indexes1_max < indexes2_max && indexes2_max < indexes3_min)
return true;
}
}
}
return false;
이제 3학년..