-
보석 쇼핑코딩 테스트/Level 3 2020. 10. 14. 21:30반응형
보석 쇼핑
2020 카카오 인턴십
534명 완료programmers.co.kr/learn/courses/30/lessons/67258
코딩테스트 연습 - 보석 쇼핑
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7]
programmers.co.kr
시간제한이 없다면..
def solution(gems): set_gems = set(gems) min_val = [float('inf'), None, None] for i in range(len(gems)): checker = {} for j in range(i, len(gems)): checker[gems[j]] = 1 if len(checker) == len(set_gems): if min_val[0] > j - (i - 1): min_val = [j - (i - 1), i + 1, j + 1] break return min_val[1:]테스트 1 〉 통과 (0.07ms, 10.7MB) 테스트 2 〉 통과 (0.36ms, 10.8MB) 테스트 3 〉 통과 (1.15ms, 10.7MB) 테스트 4 〉 통과 (22.59ms, 10.8MB) 테스트 5 〉 통과 (0.27ms, 10.8MB) 테스트 6 〉 통과 (0.05ms, 10.7MB) 테스트 7 〉 통과 (0.06ms, 10.8MB) 테스트 8 〉 통과 (38.93ms, 10.7MB) 테스트 9 〉 통과 (23.46ms, 10.8MB) 테스트 10 〉 통과 (89.21ms, 10.9MB) 테스트 11 〉 통과 (189.36ms, 11MB) 테스트 12 〉 통과 (43.91ms, 10.9MB) 테스트 13 〉 통과 (56.58ms, 10.9MB) 테스트 14 〉 통과 (734.86ms, 11.2MB) 테스트 15 〉 통과 (133.75ms, 11.2MB)브레이크를 하나 더 추가했습니다.
첫 번째 브레이크가 안 걸린단 말은 j가 끝까지 갔는데도 불구하고 조건에 맞는 게 없었다는 말이니까요.
이런 경우는 i에 두 번째 브레이크를 걸어 시간을 벌어줍니다. 파이썬 만의 for else 구문입니다. 처음엔 헷갈려요..딕셔너리를 이용해서
def solution(gems): set_gems = set(gems) min_val = [float('inf'), None, None] for i in range(len(gems)): checker = {} for j in range(i, len(gems)): checker[gems[j]] = 1 if len(checker) == len(set_gems): if min_val[0] > j - (i - 1): min_val = [j - (i - 1), i + 1, j + 1] break else: break return min_val[1:]정확성 테스트 테스트 1 〉 통과 (0.07ms, 10.6MB) 테스트 2 〉 통과 (0.36ms, 10.7MB) 테스트 3 〉 통과 (1.04ms, 10.8MB) 테스트 4 〉 통과 (0.24ms, 10.9MB) 테스트 5 〉 통과 (0.32ms, 10.8MB) 테스트 6 〉 통과 (0.05ms, 10.7MB) 테스트 7 〉 통과 (0.05ms, 10.7MB) 테스트 8 〉 통과 (14.10ms, 10.8MB) 테스트 9 〉 통과 (37.51ms, 10.7MB) 테스트 10 〉 통과 (0.95ms, 11MB) 테스트 11 〉 통과 (3.52ms, 11MB) 테스트 12 〉 통과 (41.48ms, 10.8MB) 테스트 13 〉 통과 (56.74ms, 11MB) 테스트 14 〉 통과 (60.99ms, 11.2MB) 테스트 15 〉 통과 (120.73ms, 11.2MB) 효율성 테스트 테스트 1 〉 실패 (시간 초과)딕셔너리 보다 조금 더 빠르게...
별도의 카운터를...def solution(gems): set_gems = set(gems) min_val = [float('inf'), None, None] for i in range(len(gems)): checker = {k: 0 for k in set_gems} counter = 0 for j in range(i, len(gems)): if checker[gems[j]] != 1: checker[gems[j]] = 1 counter += 1 if counter == len(set_gems): if min_val[0] > j - (i - 1): min_val = [j - (i - 1), i + 1, j + 1] break else: break return min_val[1:]정확성 테스트 테스트 1 〉 통과 (0.07ms, 10.7MB) 테스트 2 〉 통과 (0.37ms, 10.8MB) 테스트 3 〉 통과 (1.13ms, 10.7MB) 테스트 4 〉 통과 (0.35ms, 10.9MB) 테스트 5 〉 통과 (0.37ms, 10.7MB) 테스트 6 〉 통과 (0.05ms, 10.8MB) 테스트 7 〉 통과 (0.07ms, 10.7MB) 테스트 8 〉 통과 (13.90ms, 10.8MB) 테스트 9 〉 통과 (20.88ms, 10.8MB) 테스트 10 〉 통과 (1.08ms, 11MB) 테스트 11 〉 통과 (3.38ms, 11MB) 테스트 12 〉 통과 (37.55ms, 10.9MB) 테스트 13 〉 통과 (51.55ms, 10.9MB) 테스트 14 〉 통과 (56.07ms, 11.2MB) 테스트 15 〉 통과 (113.88ms, 11.3MB) 효율성 테스트 테스트 1 〉 실패 (시간 초과)합집합을 이용해서..
더 느림...def solution(gems): identities = len(set(gems)) min_val = [float('inf'), None, None] for i in range(len(gems)): checker = set() for j in range(i, len(gems)): checker.add(gems[j]) if len(checker) == identities: if j - (i - 1) < min_val[0]: min_val = [j - (i - 1), i + 1, j + 1] break else: break return min_val[1:]테스트 1 〉 통과 (0.07ms, 10.8MB) 테스트 2 〉 통과 (0.44ms, 10.6MB) 테스트 3 〉 통과 (1.32ms, 10.9MB) 테스트 4 〉 통과 (0.27ms, 10.9MB) 테스트 5 〉 통과 (0.33ms, 10.8MB) 테스트 6 〉 통과 (0.05ms, 10.7MB) 테스트 7 〉 통과 (0.06ms, 10.7MB) 테스트 8 〉 통과 (15.55ms, 10.8MB) 테스트 9 〉 통과 (27.65ms, 10.8MB) 테스트 10 〉 통과 (1.16ms, 11MB) 테스트 11 〉 통과 (3.94ms, 11.1MB) 테스트 12 〉 통과 (47.76ms, 10.8MB) 테스트 13 〉 통과 (69.44ms, 11MB) 테스트 14 〉 통과 (75.88ms, 11.1MB) 테스트 15 〉 통과 (149.12ms, 11.1MB) 효율성 테스트 테스트 1 〉 실패 (시간 초과)예상은 했지만 레벨 3 문제를 레벨 2 수준으로 풀어 본들...
통과될 리가 없죠?투 포인터 가즈아..
def solution(gems): if len(gems) == 1: return [1, 1] identities = len(set(gems)) min_val = [float('inf'), None, None] low = high = 0 counter = {gems[high]: 1} while high != len(gems) - 1 and low != len(gems) - 1: if len(counter) < identities: high += 1 counter[gems[high]] = counter.get(gems[high], 0) + 1 if len(counter) == identities: if min_val[0] > high - low + 1: min_val = [high - low + 1, low + 1, high + 1] if counter[gems[low]] == 1: del counter[gems[low]] else: counter[gems[low]] -= 1 low += 1 return min_val[1:] print(solution([1, 1, 1, 2, 3])) # [1, 5]정확성 테스트 테스트 1 〉 통과 (0.06ms, 10.8MB) 테스트 2 〉 통과 (0.12ms, 10.8MB) 테스트 3 〉 통과 (0.31ms, 10.8MB) 테스트 4 〉 통과 (0.30ms, 10.8MB) 테스트 5 〉 통과 (0.35ms, 10.7MB) 테스트 6 〉 실패 (0.33ms, 10.8MB) 테스트 7 〉 실패 (0.28ms, 10.9MB) 테스트 8 〉 통과 (0.52ms, 10.8MB) 테스트 9 〉 통과 (0.85ms, 10.8MB) 테스트 10 〉 통과 (0.57ms, 10.9MB) 테스트 11 〉 통과 (0.81ms, 11.1MB) 테스트 12 〉 통과 (1.37ms, 11MB) 테스트 13 〉 통과 (1.84ms, 10.9MB) 테스트 14 〉 통과 (1.59ms, 11.2MB) 테스트 15 〉 통과 (3.86ms, 11.3MB) 효율성 테스트 테스트 1 〉 통과 (4.64ms, 11.4MB) 테스트 2 〉 통과 (7.36ms, 15.2MB) 테스트 3 〉 통과 (15.44ms, 19.3MB) 테스트 4 〉 통과 (10.33ms, 23.2MB) 테스트 5 〉 통과 (24.52ms, 27.2MB) 테스트 6 〉 통과 (29.81ms, 31.2MB) 테스트 7 〉 통과 (34.51ms, 35.1MB) 테스트 8 〉 통과 (38.71ms, 39.1MB) 테스트 9 〉 통과 (46.18ms, 42.9MB) 테스트 10 〉 통과 (51.00ms, 46.9MB) 테스트 11 〉 통과 (57.83ms, 54.9MB) 테스트 12 〉 통과 (36.32ms, 62.8MB) 테스트 13 〉 통과 (54.09ms, 70.7MB) 테스트 14 〉 통과 (89.51ms, 78.5MB) 테스트 15 〉 통과 (95.01ms, 86.5MB)정확성 테스트 6, 7번 실패.
반례 [1, 1, 1, 2, 3]def solution(gems): if len(gems) == 1: return [1, 1] identities = len(set(gems)) min_val = [float('inf'), None, None] low = high = 0 counter = {gems[high]: 1} while high != len(gems) and low != len(gems) - 1: if len(counter) < identities: high += 1 if high != len(gems): counter[gems[high]] = counter.get(gems[high], 0) + 1 if len(counter) == identities: if min_val[0] > high - low + 1: min_val = [high - low + 1, low + 1, high + 1] if counter[gems[low]] == 1: del counter[gems[low]] else: counter[gems[low]] -= 1 low += 1 return min_val[1:]정확성 테스트 테스트 1 〉 통과 (0.06ms, 10.8MB) 테스트 2 〉 통과 (0.13ms, 10.8MB) 테스트 3 〉 통과 (0.31ms, 10.8MB) 테스트 4 〉 통과 (0.34ms, 10.7MB) 테스트 5 〉 통과 (0.38ms, 10.8MB) 테스트 6 〉 통과 (0.05ms, 10.8MB) 테스트 7 〉 통과 (0.05ms, 10.7MB) 테스트 8 〉 통과 (0.57ms, 10.8MB) 테스트 9 〉 통과 (0.86ms, 10.8MB) 테스트 10 〉 통과 (0.61ms, 10.8MB) 테스트 11 〉 통과 (0.92ms, 11MB) 테스트 12 〉 통과 (1.31ms, 10.9MB) 테스트 13 〉 통과 (2.05ms, 10.9MB) 테스트 14 〉 통과 (1.78ms, 11.2MB) 테스트 15 〉 통과 (4.03ms, 11.4MB) 효율성 테스트 테스트 1 〉 통과 (5.06ms, 11.4MB) 테스트 2 〉 통과 (7.65ms, 15.3MB) 테스트 3 〉 통과 (14.67ms, 19.2MB) 테스트 4 〉 통과 (11.99ms, 23.3MB) 테스트 5 〉 통과 (24.30ms, 27.1MB) 테스트 6 〉 통과 (29.74ms, 31.2MB) 테스트 7 〉 통과 (33.90ms, 35.2MB) 테스트 8 〉 통과 (42.54ms, 39.1MB) 테스트 9 〉 통과 (42.37ms, 42.8MB) 테스트 10 〉 통과 (53.65ms, 47MB) 테스트 11 〉 통과 (60.29ms, 55MB) 테스트 12 〉 통과 (42.54ms, 62.8MB) 테스트 13 〉 통과 (58.46ms, 70.7MB) 테스트 14 〉 통과 (93.87ms, 78.5MB) 테스트 15 〉 통과 (94.13ms, 86.5MB)중간 중간에 반복되는 if문들.. 싹 정리...
def solution(gems): identities = len(set(gems)) min_val = [float('inf'), None, None] low = high = 0 counter = {} while True: if len(counter) == identities: if min_val[0] > high - low: min_val = [high - low, low + 1, high] if counter[gems[low]] == 1: del counter[gems[low]] else: counter[gems[low]] -= 1 low += 1 elif high == len(gems): break else: counter[gems[high]] = counter.get(gems[high], 0) + 1 high += 1 return min_val[1:]정확성 테스트 테스트 1 〉 통과 (0.05ms, 10.8MB) 테스트 2 〉 통과 (0.09ms, 10.8MB) 테스트 3 〉 통과 (0.19ms, 10.8MB) 테스트 4 〉 통과 (0.21ms, 10.8MB) 테스트 5 〉 통과 (0.30ms, 10.8MB) 테스트 6 〉 통과 (0.04ms, 10.8MB) 테스트 7 〉 통과 (0.05ms, 10.7MB) 테스트 8 〉 통과 (0.33ms, 10.9MB) 테스트 9 〉 통과 (0.48ms, 10.9MB) 테스트 10 〉 통과 (0.37ms, 10.9MB) 테스트 11 〉 통과 (0.53ms, 11.1MB) 테스트 12 〉 통과 (0.71ms, 10.8MB) 테스트 13 〉 통과 (0.97ms, 10.9MB) 테스트 14 〉 통과 (1.02ms, 11.1MB) 테스트 15 〉 통과 (2.03ms, 11.2MB) 효율성 테스트 테스트 1 〉 통과 (2.53ms, 11.4MB) 테스트 2 〉 통과 (4.32ms, 15.3MB) 테스트 3 〉 통과 (7.70ms, 19.2MB) 테스트 4 〉 통과 (6.83ms, 23.3MB) 테스트 5 〉 통과 (13.35ms, 27.1MB) 테스트 6 〉 통과 (15.19ms, 31.1MB) 테스트 7 〉 통과 (18.49ms, 35.1MB) 테스트 8 〉 통과 (20.79ms, 39.1MB) 테스트 9 〉 통과 (24.29ms, 42.9MB) 테스트 10 〉 통과 (25.62ms, 47.1MB) 테스트 11 〉 통과 (29.63ms, 54.9MB) 테스트 12 〉 통과 (23.20ms, 62.8MB) 테스트 13 〉 통과 (31.22ms, 70.8MB) 테스트 14 〉 통과 (48.96ms, 78.6MB) 테스트 15 〉 통과 (51.13ms, 86.5MB)직접 투 포인터를 구현해 보니,
알고리듬은 어렵지 않은데..
if 문의 위치 선정이 까다로운 편인 것 같다. 주의~!반응형