Today I Learned

텍스트오늘 할일
1. LeetCode
2. 강의 3개
3. 싱가포르 여행계획 수정
4. 노트북 파일권한문제 해결

오늘 한일
1. LeetCode

• 11. Container with most water문제를 다시 도전해보고있다.
      가장 간단한 sort방법으로 접근했을 경우 48/62 test cases에서 Time Limit Exceeded가 발생했다.

    public int maxArea(int[] height) {
        int size=height.length;
        //way1_전부 계산하여 정렬_48/62 Time Limit Exceeded
        Set<Integer> uniq_dimension=new HashSet<Integer>();
        int demension=0;
        for(int first_x=0; first_x<size; first_x++){
            for(int second_x=first_x+1; second_x<size; second_x++){
                demension=(second_x-first_x)*(Math.min(height[first_x], height[second_x]));
                uniq_dimension.add(demension);
            }
        }
        return Collections.max(uniq_dimension);
    }

도저히 감이 안잡히네..

• 규칙성 찾기
  현재 실패하며 나온 모든 테스트 케이스들을 그려보기로 했다.
  현재의 테스트케이스들은 다음과 같다

1. solution.test(solution.maxArea(new int[]{1,8,6,2,5,4,8,3,7}) , 49);
   

2. solution.test(solution.maxArea(new int[]{1,1}) , 1);
   

3. solution.test(solution.maxArea(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}) , 25);
   

4. solution.test(solution.maxArea(new int[]{4,3,2,1,4}) , 16);
   

5. solution.test(solution.maxArea(new int[]{1,0,0,0,0,0,0,2,2}) , 8);
   

가장 높은 막대의 반 미만의 막대를 포함시키지 않는다는 규칙성을 발견하여 해당 부분을 예외처리하고, 조건을 조절했지만 마찬가지로 48/62케이스에스 Time Limit Exceeded오류가 발생하였다.

• 초기 코드에서 시간복잡도 줄이기
  

넓이를 저장하는 공간의 타입을 HashSet에서 LinkedHashSet으로 변경->시간초과(48/62)

넓이를 저장하는 공간의 타입을 HashSet에서 LinkedList로 변경->메모리초과(47/62)

두번째 for문의 second_x를 뒤에서부터 탐색->시간초과(48/72)

힌트열람

투포인터를 사용하여.. 작은 높이의 포인터를 움직여라

class Solution {
    public int maxArea(int[] height) {
        int size=height.length;

        //way2_최적화시도
        Set<Integer> uniq_dimension=new LinkedHashSet<>();
        int demension=0;
        for(int first_x=0, second_x=size-1; first_x<second_x;){
            demension=(second_x-first_x)*(Math.min(height[first_x], height[second_x]));
            uniq_dimension.add(demension);
            if(height[first_x]<height[second_x])
                first_x++;
            else
                second_x--;
        }
        return Collections.max(uniq_dimension);
    }
}

힌트를 참고하여 문제를 해결했지만, 잘 이해는 가지 않는다.
두개의 막대를 사용해서 순회해야하는 것은 마찬가지인데 하나의 막대를 탐색하는 시간 O(n)을 줄일 순 없으니 증감할 때 둘 중 높이가 낮은 포인터를 이용해서 최적화를 진행한 것으로 이해된다.

높이가 3인 막대와 높이가 5인 막대가 있을 때, 높이가 5인 막대를 움직이기보다 높이가 3인 막대를 움직여 해결한다.. 이중for문을 사용하지 않고 단일for문에서 증감조건에 대해 규칙을 설정해서 이중for문의 효과를 내게할 수 있다는 것을 알아간다.

• 1679. Max Number of K-Sum Pairs은 정수배열에서 합이 k인 두 원소를 제거할 때 몇번 연산이 실행되는지를 묻는 문제이다.

초기코드는 다음과 같은데, 이전의 two pointer를 최대한 살려 문제를 해결해보려했지만 first와 second모두 옮겨야 할 경우 어떤 값에 우선순위를 줄지에 대한 부분이 해결되지 않는 문제가 있다.

    public int maxOperations(int[] nums, int k) {
        int size=nums.length;

        //way1
        int operation_count=0;
        for(int first=0, second=size-1; first<second; ){
            if(nums[first]>k){
                first++;
            } else if(nums[second]>k){
                second--;
            } else{//first와 second위치의 숫자는 k보다 작다
                if(nums[first]+nums[second]==k) {
                    first++;
                    second--;
                    operation_count++;
                    continue;
                }
                boolean possible_first=has_element(nums, k-nums[first], first, second);
                boolean possible_second=has_element(nums, k-nums[second], first, second);
                if(possible_first&&possible_second) {
                    first++;
                    //애매함
                } else if(possible_first){
                    second--;
                } else if(possible_second){
                    first++;
                } else{
                    first++;
                    second--;
                }
            }
        }

        return operation_count;
    }

    private boolean has_element(int[] nums, int search_num, int first, int second){
        for(int i=first+1; i<=second; i++)
            if(nums[i]==search_num)
                return true;
        return false;
    }

두번째로, 포인터를 하나만 사용하며 쌍에 해당하는 index를 찾고 다음 탐색 시 해당 index를 제외하고 검색해보았다.

 		public int maxOperations(int[] nums, int k) {
        int size=nums.length;
        //way2
        int pair_index;
        List black_list=new ArrayList();
        for(int i=0; i<size; i++){
            if(black_list.contains(i))
                continue;
            pair_index=find_pair_index(nums, k-nums[i], i, black_list);
            if(pair_index!=-1){
                black_list.add(pair_index);
            }
        }
        return black_list.size();
    }
    private int find_pair_index(int[] nums, int search_num, int from, List black_list){
        for(int i=from+1; i<nums.length; i++)
            if(nums[i]==search_num && !black_list.contains(i))
                return i;
        return -1;
    }

꽤나 큰 성과다. Time Limit Exceeded가 발생했다. 이제 현재의 코드를 최적화해보자. 사실 현재의 방법도 결국 이중 for문과 다를바가 없다. 함수를 호출하여 순회하기 때문이다.

• 시간복잡도 줄이기

첫번째 시도의 아이디어를 가져와 i번째값이 k보다 크면 건너뛰기->시간초과

코드를 간소화시키기 위해 별도의 list공간 활용없기 검색한 index는 k+1로 만들어서 무력화시킴

class Solution {
    public int maxOperations(int[] nums, int k) {
        int size=nums.length;
        int count=0;
        //way4 blacklist말고 k+1로 만들어버리자. 양수니까
        for(int i=0; i<size-1; i++){
            int pair_value=k-nums[i];
            for(int j=i+1; j<size; j++) {
                if (nums[j] == pair_value){
                    count++;
                    nums[j]=k+1;
                    break;
                }
            }
        }
        return count;
    }
}

같은 Time Limit Exceeded이지만 테스트케이스가 46/51로 거의 통과되었다. 추가적으로 최적화시켜보자.

마땅한 방법이 생각나지 않던 찰나, 빠뜨린 코드를 찾아냈다. 가장 좋은 결과를 보여준 위 코드에는 i나 j가 해당하는 값이 k보다 큰 경우 다음 순회로 넘어가는 최적화 코드를 넣지 않았다. 우선 i최적화 코드만 추가해보았다.

class Solution {
    public int maxOperations(int[] nums, int k) {
        int size=nums.length;
        int count=0;
        int pair_value;
        int j;
        //way4 blacklist말고 k+1로 만들어버리자. 양수니까
        for(int i=0; i<size-1; i++){
            if(nums[i]>k)//예외처리
                continue;
            pair_value=k-nums[i];
            for(j=i+1; j<size; j++) {
                if (nums[j] == pair_value){
                    count++;
                    nums[j]=k+1;
                    break;
                }
            }
        }
        return count;
    }
}

진짜 아름다운 초록색 결과창이다... 비록 아슬아슬하게 꼴지로 통과하긴 했지만 최적화보다도 케이스를 덜어낼 수 있는 예외처리 역시 정말 중요하다는 것을 새삼스럽게 알 수 있었다.

j의 예외처리의 경우 어차피 아래 코드에 비교연산이 사용되기에 2배 더 많은 2696ms가 소요되었다. 물론 해당 코드 역시 통과이다.
추가적으로 최적화를 진행해보고 싶지만, 정말 오랜시간 생각해보았었기에 엄두가 나진 않는다. 그리고 꼴지인 줄 알았는데, Java기준 상위 5.07%를 기록했다. 문제의 카테고리가 two pointer인데 이중for문으로 해결하여 약간 아쉽긴하지만, 오늘은 여기서 마무리를 해야겠다.