링크 : https://school.programmers.co.kr/learn/courses/30/lessons/67258 문제 #Testcase gems = ["ZZZ", "YYY", "NNNN", "YYY", "BBB"] #[1,5] gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] #[3,7] 투포인터st로 접근하기 DIA RUBY RUBY DIA DIA EMERALD SAPPHIRE DIA 일때, DIA RUBY EMERALD SAPPHIRE가 모두 포함되는 구간을 찾는것이 문제인데 정확성과 효율성을 찾아야하는 문제다보니, 어케할까 고민하다가 슬라이딩윈도우(투포인터) 방법으로 접근해봤다 시간초과 나는 코드 def ..

링크 : https://programmers.co.kr/learn/courses/30/lessons/72411 문제 문자열의 부분문자열 부분문자열(substring)이란 쉽게말해서 문자열을 구성하고 있는 문자열이다. 예를들어 ‘abcd’의 경우, 길이가 1인 문자열 [ a, b, c, d ], 길이가 2인 문자열 [ ab, bc, cd ] 길이가 3인 문자열 [ abc, bcd ], 길이가 4인 문자열 [ abcd ] 조합을 사용한 문자열 문제를 잘 읽어보면 ‘부분문자열의 순서' 는 중요하지않다고 말한다. 만약 ab, ba가 있다면 이 두개는 사실 같은문자열으로 취급해줘야한다. 이때 사용하는 라이브러리가 from itertools import combinations 이다. 소스코드(해설) for cour..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/92344 무지성으로 풀면 무조건 시간초과난다 이 문제는 정확성과 효율성이 따로 구분되어있다. 무조건 모든 방식에서 생각해봐야한다는거다 시간초과 코드는 하단에 첨부한다 사전지식 : 누적합 보통 구간의 합계를 sum(리스트시작:리스트끝) 이걸로 구하는데 이게 리스트길이만큼의 시간복잡도가 사용된다. 그러면 합산 한번당 O(n)이 걸리는데 당연히 연산 횟수가 많아지면 많아질수록 비례해서 길어질것이다 그런데 누적합을 사용한 방식은 누적합계를 더한다음에 리스트끝원소-리스트시작원소 를 지정해서 계산하는데 리스트인덱싱1개는 O(1)이거든요. 그래서 누적합은 O(1)+O(1) 시간에 구간의 합계를 구할수 있어서 사용한다..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/60057 문자열의 크기는 어떻게 될까? 테케2번 : ababcdcdababcdcd ⇒ 절반인 8개로 압축되면 2ababcdcd → N//2까지 압축 가능함 ⇒ 압축 범위는 1~N//2 압축이 진행되는 범위는 어디일까? 문자열 전역에서 압축이 일어날수 있음 ⇒ 문자열을 훑어야 하는 범위는 N 압축단위가 클수록, 압축문자열의 길이가 길까? 압축길이를 탐색할때 1→ (N//2) 방향으로 하나씩 늘려서 찾는방법과 (N//2) → 1 방향으로 하나씩 줄여서 찾는 방법이 있다. N//2 → 1 방향으로 탐색할때 큰 단위로 압축된 문자열의 압축문자열이 길까? 에 대해서 생각해봤는데 내생각은 ‘아니다’. 2개 단위로 ..