난이도: Lv.3유형: 슬라이딩 윈도우해결 여부: 틀림내가 생각했던 아이디어/큰 가닥K개씩 부분수열에서 최댓값을 찾고, 그 최댓값이 제일 작을떄가 정답이다. 라는 발상까지는 맞았다. 그리고 이는 O(N) 이라서 시간도 괜찮을 줄 알았는데 정확도는 다맞았고 효율성에서 타임오버가 떴다.그래서 최댓값 찾는 방식을 deque 으로 하나씩 빼주고, 더해주는 식으로 바꿨는데 그래도 타임에러가 났다. 오답 이유문제는 반복문 안에서 호출하는 max() 였다. 이게 계속 돌면서 O(N*M) 이어서 타임오버가 난 것이다.해답다음 로직을 추가해야 한다. 어차피 이전에 들어왔으면서, 이후의 값보다 작은 값은 필요가 없다. 그래서 바로 신참 들어올때 지워버린다.이 방법을 쓰면 무조건 맨 앞의 값이 가장 크다. 그래서 계속 맨..
Algorithm
난이도: Lv.3유형: bfs/dfs해결 여부: 정답내가 생각했던 아이디어/큰 가닥전형적인 bfs/dfs 택일하는 그래프 연결문제다. 정답을 받았다. 오답 이유해답차집합으로 하는것보다는 그냥 visited 로 true/false 기록하는게 더 효율적이라고 한다.#기억할 문법 #set 활용 문법set.add(값) #값 추가set.remove(값) #값 제거 set.discard(값) #값 제거 (값이 없어도 에러 안남)set.union(set2) #합집합set.intersection(set2) #교집합set.difference(set2) #차집합set.isdisjoint(set2) #두 집합이 서로소인지 확인 (공통 원소가 없는지)set.issubset(set2) #부분집합인지 확인 (자신이 다른 집합의 ..
난이도: Lv.3유형: 문자열해결 여부: 효율성 틀림내가 생각했던 아이디어/큰 가닥처음에는 대칭이라는 점을 이용해서, 한 문자열 중심으로 대칭되는거를 하려다가 그러면 홀수문자열 밖에 안된다는 걸 알고, 짝수도 따로 추가해주었다.오답 이유갈래는 맞았으나 중복호출이 문제였다. for문에서랑 is_palin으로 돌면서 중복 확인해서 O(N^3) 이 나왔다.해답for문과 is_palin을 하나로 합친 중복 제거한 코드를 써준다. #기억할 문법 함수 안에 함수 선언해서 nested 구조로 지역변수를 전역변수처럼 사용하기#내 오답코드def is_palin(s,start,end): for i in range(0,(end-start+1)//2,1): if s[start+i]!=s[end-i]: ..
난이도: Lv.3유형: 투포인터해결 여부: 해결내가 생각했던 아이디어/큰 가닥각자 하나씩 비교해가면서 지워가면 되는 문제로 맨 처음에는 각 A,B 속성을 2차원에 부여한다음에 하나로 정렬시키는걸 생각했다.그런데 짜다보니 리스트를 합칠 필요도 없다는 것을 발견했고, 그냥 하나씩 pop(0) 하는 식으로 했다.오답 이유오답은 아니고 효율성도 통과는 했지만 더 빨리하는 방법은 pop(0) 을 쓰지 않는 것이다.그냥 이런문제 나올떄마다 pop(0) 하지말고 투포인터로 포인터 위치만 기록해놓고 옮겨서 해당 값 보는게 편하다.해답시간쪽만 조금 다르다#기억할 문법 없다.#내 정답코드def solution(A, B): answer = 0 #합칠 필요도 없다. A.sort(reverse=True) ..
난이도: Lv.3유형: 수학해결 여부: 정답내가 생각했던 아이디어/큰 가닥곱이 최대가 되게하는 합이 정해진 수열을 찾아라 인데. 이건 원래 알고있던거라 당연히 균등해야지 생각하고 바로 했다.너무 쉬워서 뭐가 더 효율적이거나 edge case가 있나 싶었는데 이게 맞았다. 오답 이유해답이딴게 LV.3?굳이 따지면 더 간결한 문법이나 내장함수도 있다는거#기억할 문법 # 몫과 나머지 한번에 구하기quotient, remain = divmod(s, n)# 리스트 한번에 +와 *로 for문 append 없이 만들기temp_list = [value_a] * n + [value_b] * m#내 정답코드def solution(n, s): if n>s: return [-1] answer = []..
난이도: Lv.3유형: 이분탐색해결 여부:오답내가 생각했던 아이디어/큰 가닥이분탐색 문제 야근지수 꺼 틀려서 그때 그 아이디어 그대로 시도했다.큰 가닥은 맞았다. 다만..오답 이유low 초기값 설정이 문제였다. low를 무심코 n이라고 뒀는데 그래서는 안되었다. 1이라고 두는게 맞았다. 걍 잘 모르겠으면 low는 가능한 작아도 되고, high는 무식하게 커도 된다는 갓민 기억하자. 이분탐색에서 while에 등호 들어간다는 것도해답low값만 바꾸고 굳이 따지면#기억할 문법 #리스트 컴프리헨션은 아니지만 리스트 순회하면서 뭔가 계산할 때도 바로 조건 붙여서 계산하기 가능하다. #컴프리헨션에 얽매이지 말고 상황에 맞게 활용하기temp=sum(mid//t for t in times)#내 오답코드def solut..
난이도: Lv.3유형: 힙해결 여부: 정답내가 생각했던 아이디어/큰 가닥힙이나 덱 써서 한다고 생각했다. 실제로 모범답안도 힙이었다.근데 파이썬에서 heapq 은 최소밖에 지원 안한다는걸 알고 걍 리스트로 통과되나 했는데 그냥 통과 되어버렸다.오답 이유틀린건 아니다. 다만 매번 정렬하는게 효율이 떨어져 나중에 타임오버에러가 날 수 있다.해답2단계인데, 우선 조금 개선된 방식은 최소힙 쓴다음에 최대 삭제하라고 하면 remove를 쓰고 heapify를 쓰는거다. heap에서도 remove를 지원한다. 대신 그러면 heapify()로 재정렬이 필요하다. 제일 좋은 방식은 최대힙, 최소힙 2개 다 쓴다. 그리고 넣을때는 최대힙에는 -붙여서 뒤집어서 넣는다. 그리고 넣을떄 (value,ID)를 쌍으로 넣는다. 그..
난이도: Lv.3유형: 이분탐색, 힙해결 여부: 틀림내가 생각했던 아이디어/큰 가닥이분탐색으로 적정값 찾는 문제다. 여기까지 큰 가닥은 제대로 잡고 구현도 어느정도 잘되었다. 그런데...오답 이유문제는 샤갈 엣지케이스였다. 해답cutline을 바로 항상 /2 로 저장하는게 아니라, mid랑 분리시켜 가능할때만 저장하고, 이상/이하로 처리해서 +-1 더해주어야지 엣지케이스가 안난다.. 걍 외우자#기억할 문법 # 순회하면서 바로 조건ㅇ붙여서 계산하기 가능하다needed = sum(w - mid for w in works if w > mid) #내 오답코드def is_possible_cut(n,works,cutline): havetocut=0 for w in works: if cutli..
