[2023-01-03]

Start

---

PassingCars 문제

 

아래는 어제 상태이다..

이중 for문이 돌아가고 있어서 시간복잡도는 O(n^2)인 아주 여므벼으인 상태이다.

 

얼른 마저 풀어보겠습니당..

 

성능 테스트 20%가 나왔는데 result가 1,000,000,000 일 경우 -1 처리 해주는 부분 때문인 것 같다.

지금 이 레슨을 극복하지 못하는 이유는 커다란 입력 범위와 타이트한 시간 제한에 비해 시간복잡도가 너무 크다는 점이다.

 

커다란 입력 범위를 줄일 수 있다고 판단되는 로직을 짜보고 있는 중이다.

위와 같이 짠 이유는 0과 1이 반반일 경우

이중 for문으로 돌게 되는 값이 원래 코드에서는 n * n = n ** 2였지만 (n/2) * (n/2) = n**2 / 4 가 될 것이라고 생각했다.

 

물론 위처럼 0과 1이 반반인 경우는 평균적인 시간복잡도일 수 있지만 최악의 시간복잡도는 여전히 n ** 2이기 때문에 실패했다.

 

 

너무너무 안 풀려서 다른 사람이 푼 답을 보았는데 생각보다 코드가 너무 간단하고 간단한 구현이었는데 어떻게 못했나싶다..

O(N)으로 간단하게 구할 수 있었던 문제였다..ㅜㅜ

 

---

GenomicRangeQuery 문제

 

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        int size = P.length, result = 0, size_s = S.length();
        int[] result_array = new int[size];
        int[] s_array = new int[size_s];
        Map<Character, Integer> map = new HashMap<>();
        map.put('A', 1);
        map.put('C', 2);
        map.put('G', 3);
        map.put('T', 4);


        Map<Integer, Integer> sh_rt = new HashMap<>();
        int prev = 0;
        
        for(int i = 1; i < size_s; i++) {
            if (S.charAt(prev) != S.charAt(i)) {
                sh_rt.put(prev, i - 1);
                s_array[i] = i;
                prev = i;
                
            } else {
                s_array[i] = prev;
            }
            if (i == size_s - 1) {
                sh_rt.put(prev, i);
            }
        }

        int p = 0, q = 0, temp = 0;
        for(int i = 0; i < size; i++) {
            result = 4;
            
            p = P[i];
            q = Q[i];
            
            while(p <= q) {
                result = result > map.get(S.charAt(p)) ? map.get(S.charAt(p)) : result;
                p = sh_rt.getOrDefault(s_array[p] + 1, Integer.MAX_VALUE);
            }
            result_array[i] = result;
        }

        return result_array;
    }

 

문자열을 압축하고 있는데..눈물이 좀 나서.. 잠시 lesson 6을 풀고오려고 한다..

 

---

Start

 

---

Distinct 문제

배열에서 유일한 값을 찾는 문제이다.

 

도망친다고 딱히 천국이 있는 거는 아니고.. 천국이 있을거라고 생각도 하지 않았다..ㅎㅎ

 

오름차순으로 정렬한 후 오른쪽으로 한 칸씩 가면서 처음 등장한 숫자의 위치를 저장해놓고

이전 칸과 다른 숫자가 나오면 저장해놓은 숫자와 비교해서 1이 아니면 해당 값이 distinct한 값이라고 생각했다....???????????????뭐라고?

 

 

도망친 곳에 천국은 없다는 말은 맞는 말이지만

천국이 있을 수는 있다.. 근데 그..멍청한 바보가 천국에 가면 가끔 천국인 줄 모를 수 있다..

 

갑자기 바보가 되어버려서..? distinct를 헷갈리면서 문제를 잘못 이해했다..

어려운 문제가 안디ㅏ..

 

 

그...non empty array라고 적혀있지 않을 경우에 빈 배열에 대한 예외처리를 해놓거나 테스트를 해보는 것이 좋겠다..

 

---

MaxProductOfThree 문제

 

3개를 곱하는 것이기 때문에 무조건 정렬해서 뒤의 세 개를 곱하는 것뿐만 아니라 앞의 두 개를 곱하고 뒤의 하나를 곱한 값과도 비교해봐야한다.

그렇지 않으면..점수가 반토막난다..

 

 

---

위의 꺼 풀고..다시 lesson 5로 돌아왔습니당..

MinAvgTwoSlice 문제

index 0 부터 배열의 오른쪽으로 이동하면서 더한 값을 map에 저장하고

평균값을 구하는데.. 정확도에서 날라갔으니 정확한 풀이는 아닐 것이다..

 

답이 틀리면..코딜리티가 답답해하면서 반례를 던져준다..

좋은 반례를 통해 문제를 찾았다.. 문제는 소숫점 값까지 해서 비교하고 있었던 게 아니라... 나눈 값만 비교하고 나머지는 비교하고 있지 않았다..

 

따라서 나머지를 비교함으로써 위와 같이 정확도 테스트를 통과한 것을 볼 수 있고..

성능 테스트가 날아간 것을 볼 수 있다..

 

눈에 보이는 시간복잡도는 O(n ** 2)로 보이는데.. O(n ** 3)이라고 하시네..

 

근데 뭐..아니고 말고를 떠나서 테스트 결과가 말해주니까.. 줄일 수 있는 방법에 대해서 생각해봐야겠다..