난이도: Lv.3유형: DP, 문자열 처리, 누적합, sliding window해결 여부: 틀림내가 생각했던 아이디어/큰 가닥대충 어케하는지는 알았는데 하다가 코드 비효율적이고 문제 풀이 시간도 다 되어서 관두었다.아이디어 자체는 계속 시작하는 초로 비교하는 것일 것이다.오답 이유/는 float 반환해서 망가짐불필요한 문자열 초 반복최대 로그 길이상 배열 순회하면 시간복잡도 늘어남.무엇보다 가장 효율적인 시간이 시작시간이 아닐때가 존재한다. 그래서 이 방법은 아예 틀렸다. 해답-누적합을 2개 만든다. 36만개 짜리 배열 만들어서 시작시간에 +1, 종료시간에 -1 해준다,여기서 1차 누적합을 만든다. 배열 한번 순회하면서 이전값 다 더해주면 현재 시청자 수가 나온다.2차 누적합으로 한번더 같은 방식을 쓰면..
Algorithm/Prefix sum, Two pointer, Sliding Window
난이도: Lv.3유형: 부분합, 누적합해결 여부:틀림내가 생각했던 아이디어/큰 가닥2차원 배열로 합으로 하면 되는데... 효율성테스트에 Lv.3 까지 있는걸로 봐서는 그냥 합은 아닌것같고그렇다고 부분 합으로 하기에도 시간 많이 걸리는 건 똑같은데. 그냥 일단은 틀릴걸 알면서도 brute force로 해보았다.오답 이유타임오버. 정확성 테스트는 다 맞았으나 당연히 효율성 테스트는 통과 못함해답부분합인데 2차원 배열을 활용한 새로운 방법이다. 개념을 알면 맞고 모르면 틀린다.사각형 기준으로 같은값을 더한다 하면, 시작점과 끝점에는(왼쪽위와 오른쪽 아래) 그만큼 +를, 다른 두 꼭짓점에는(오른쪽 위와 왼쪽 아래) 그만큼 -를 한다.그런 후 최종 계산단계에서는 왼쪽-> 오른쪽 합 누적시키기, 위쪽-> 아래쪽으로..
난이도: Lv.3유형: 슬라이딩 윈도우해결 여부: 틀림내가 생각했던 아이디어/큰 가닥K개씩 부분수열에서 최댓값을 찾고, 그 최댓값이 제일 작을떄가 정답이다. 라는 발상까지는 맞았다. 그리고 이는 O(N) 이라서 시간도 괜찮을 줄 알았는데 정확도는 다맞았고 효율성에서 타임오버가 떴다.그래서 최댓값 찾는 방식을 deque 으로 하나씩 빼주고, 더해주는 식으로 바꿨는데 그래도 타임에러가 났다.오답 이유문제는 반복문 안에서 호출하는 max() 였다. 이게 계속 돌면서 O(N*M) 이어서 타임오버가 난 것이다.해답다음 로직을 추가해야 한다. 어차피 이전에 들어왔으면서, 이후의 값보다 작은 값은 필요가 없다. 그래서 바로 신참 들어올때 지워버린다.이 방법을 쓰면 무조건 맨 앞의 값이 가장 크다. 그래서 계속 맨 앞..
난이도: Lv.3유형: 투포인터해결 여부: 해결내가 생각했던 아이디어/큰 가닥각자 하나씩 비교해가면서 지워가면 되는 문제로 맨 처음에는 각 A,B 속성을 2차원에 부여한다음에 하나로 정렬시키는걸 생각했다.그런데 짜다보니 리스트를 합칠 필요도 없다는 것을 발견했고, 그냥 하나씩 pop(0) 하는 식으로 했다.오답 이유오답은 아니고 효율성도 통과는 했지만 더 빨리하는 방법은 pop(0) 을 쓰지 않는 것이다.그냥 이런문제 나올떄마다 pop(0) 하지말고 투포인터로 포인터 위치만 기록해놓고 옮겨서 해당 값 보는게 편하다.해답시간쪽만 조금 다르다#기억할 문법 없다.#내 정답코드def solution(A, B): answer = 0 #합칠 필요도 없다. A.sort(reverse=True) ..
난이도: Lv.3유형: 투 포인터해결 여부: 틀림내가 생각했던 아이디어/큰 가닥양방향으로 잘라가면 될거라 생각했다. 앞에서 끝까지 자르고, 끝에서 다시 앞까지 자르고오답 이유타임오버가 나서 temp를 그대로 넘겨주는게 아니라 변수로만 표시하는 방식으로 바꾸었다. 그런데도 에러가 났다.다음과 같은 반례가 있기 때문이다.. gems = ["A", "B", "B", "B", "C", "A", "B", "C"] 이런상황일때 정답은 6,8 이지만 나는 1,5를 뱉는다.해답투포인터를 제대로 사용하지 않은것이 문제였다. 나는 단순히 범위를 줄이는데만 사용했는데 모든 상황을 탐색하는 투포인터는 다음과 같이 움직인다.startpos, endpos 를 0으로 초기화 한다.endpos는 조건이 맞지 않는동안 (맞을때까지)움..
난이도: Lv.3유형: 부분합해결 여부: 틀림 이후 개선시켜 정답내가 생각했던 아이디어/큰 가닥부분합이라는 가닥은 잡았다.그래서 Sn 수열을 만들어서 빼면 되지 않을까 싶었다.그래서 -1, 1 이걸 역순으로 곱한거 수열 2개를 만들고 거기서 나오는 최댓값 2개를 서로 비교해서 최종 max를 정하면 되지 않을까?오답 이유근데 그러면 음수가 섞여있고, 음수밖에 없을수도 있으니 Sr-Sl 조건에서 r>l 이어야만 한다고 생각해 for문을 한번 더 돌렸다. 그러면 실패와 시간 초과가 떴다. Sr-Sl 이라고 생각했을때 지정된 r보다 작은 l이지만 그중에서 Sl을 최소로 해야했다. 그 과정에서 그냥 maxi 검증하듯이 하면 되는데 아예 Sl이 없는경우랑 머리속에 섞여서 햇갈려서 [:] 로 리스트 슬라이싱 후 매번..
