난이도: 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 = []..
Algorithm
난이도: 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..
난이도: 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이 없는경우랑 머리속에 섞여서 햇갈려서 [:] 로 리스트 슬라이싱 후 매번..
난이도: Lv.3유형: 그래프해결 여부: 틀림내가 생각했던 아이디어/큰 가닥문제는 간단한다. 승-패 나와있을때 몇명의 순위나 알 수 있는가?이차원 배열 그래프로 푸는 방식이다.푸는 방법 자체는 어느정도 가닥을 잡았다. 중요한건, 모든 경기를 뛴 놈도 순위가 정해지지만 타율에 의해서도 정해진다는 것 (가령, 전승한놈한테 이기면 걔는 무조건 1등, 반대도 성립)그래서 이차원 배열 만들고 승-패 표에 기록해가면서 AvsB에서 A승, B패로 주어졌을때 A한테 이긴놈은 B한테도 이긴다고 기록하기. B한테 진놈은 A에게도 진다고 기록하기 라는 가닥은 잡았다.오답 이유근데 문제는 두번이상 타고들어갈떄였다. 가령 A한테 이긴놈 한테 이긴놈은 이겼다고 기록해놓아야 했다.그래서 재귀돌리니까 timeout error났다.해..
난이도: Lv.3유형: 백트래킹해결 여부: 틀림내가 생각했던 아이디어/큰 가닥큰 가닥은 맞았는데 이제 곱연산을 하면서 겹치는 중복은 제외하는 로직을 어떻게 하는가가 문제였다.ban_id와-user_id가 매칭되는 경우의 수를 구하는건데, 1대1매칭인데, 가능한건 여러개여서 겹치면 안되는 그런 문제였다. 불량사용자와 그냥 사용자 중 어떤 걸 기준으로 삼는게 좋을지 발상이 있나 싶어서 일단 둘다 만들었다. 그래서 각 리스트에서 하나씩 뽑아보고, 그 뽑은것들안에서 중복이 없게 해야했다.아니면 1~n까지 쭉 하나씩뽑되 버리고 중복이 없게 하거나...오답 이유product가 아닌 combine으로 접근한게 패착이었다. DFS로도 접근을 못했다.해답-DFs를 쓰거나 product연산을 쓰거나 아래처럼 product..
