링크 : 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 solution(gems):
# answer = []
# return answer
gem_list = set(gems)
n = len(gems) # n = 8
i, j = 0, 1
temp = []
while j < n+1 :
if set(gems[i:j]) == gem_list :
# print(gems[j-i, i:j])
temp.append([j-i, i+1, j])
i += 1
else :
j += 1
temp.sort(key=lambda x : (x[0],x[1],x[2]))
return(temp[0][1:3])
정답은 맞는데 왜 시간초과가 날까를 생각해봤다
리스트 인덱싱을 하는 과정에서 [i:j] 가 n 이라면 O(n) 인데, 이게 너무 크고 빈번해서 그런것같다.
Dict를 써봐야할것같다
애매하게 해결한 코드
def solution(gems):
gem_list = set(gems)
n = len(gems) # n = 8
i, j = 0, 0
temp = []
gem_dict = dict()
for gem in gem_list :
gem_dict[gem] = 0
def check(gem_dict) :
if 0 in gem_dict.values() :
return False
else :
return True
while j < n :
if check(gem_dict) == False :
gem_dict[gems[j]] += 1
j += 1
else :
temp.append([j-i,i+1,j])
gem_dict[gems[i]] -= 1
i += 1
temp.append([j-i,i+1,j])
temp.sort(key=lambda x : (x[0],x[1],x[2]))
return(temp[0][1:3])
이렇게 풀면 87점? 정도 맞는다. 여기서 어떻게 더 고쳐야할지 아직도 모르겠다.
'CodingTest' 카테고리의 다른 글
백준 20444 색종이와 가위 (0) | 2022.08.17 |
---|---|
백준 2661 좋은수열 (0) | 2022.08.17 |
백준 18232 텔레포트정거장 파이썬 (0) | 2022.07.20 |
백준 10826 피보나치수4 파이썬 (0) | 2022.07.20 |
리트코드 Tapping Rain Water (0) | 2022.07.13 |