Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- python
- 그리디
- 재귀
- DP
- 다이나믹 프로그래밍
- 파이썬
- 가상메모리
- 가상메모리 관리
- BFS
- 스택
- N과M
- 딕셔너리
- 백준
- dfs
- BOJ
- 프로그래머스
- 힙
- level1
- programmers
- 수학
- 다익스트라
- level3
- 브루트포스
- level2
- MYSQL
- dict
- 운영체제
- level0
- 구현
- 코딩테스트
Archives
- Today
- Total
동캄의 코딩도장
프로그래머스 level3 [보석 쇼핑] 파이썬 본문
https://programmers.co.kr/learn/courses/30/lessons/67258
# 프로그래머스 보석 쇼핑
def find_m_gem(jew):
min_=1000000
for gem in jew:
if min_>jew[gem]:
min_=jew[gem]
m_gem=gem
return m_gem
def solution(gems):
answer = [-1,-1]
jew = {}
kinds = len(set(gems))
for i in range(len(gems)):
jew[gems[i]] = i
if len(jew) == kinds:
m=min(jew.values())
diff = i-m
answer[0] = m+1
answer[1] = i+1
i+=1
break
m_gem=find_m_gem(jew)
while i<len(gems):
if m_gem==gems[i]:
jew[gems[i]]=i
m_gem=find_m_gem(jew)
else:
jew[gems[i]]=i
m=jew[m_gem]
if i-m<diff:
answer[0]=m+1
answer[1]=i+1
diff=i-m
i+=1
return answer
일단 모든 보석이 한번 씩 탐색이 된다면, for문을 탈출한다.
가장 앞에 있는 보석(m_gem)과 보석의 위치(jew[m_gem])를 파악한다.
만약에 i 번째 탐색하는 보석이 m_gem과 같은 보석이면, jew[gems[i]]를 갱신한 뒤, 다시 m_gem을 탐색하고,
그렇지 않다면 jew[gems[i]]만 갱신하고 그냥 넘어간다.
즉, 가장 최소 index를 계속 갱신하면서, index의 최대와 최소가 가장 작아지는 index를 찾는다.
(문제를 좀 더럽게 풀었다... 투 포인터로 깔끔하게 해결하신 다른 분의 풀이를 올린다.)
def solution(gems):
size = len(set(gems))
dic = {gems[0]:1}
temp = [0, len(gems) - 1]
start , end = 0, 0
while(start < len(gems) and end < len(gems)):
if len(dic) == size:
if end - start < temp[1] - temp[0]:
temp = [start, end]
if dic[gems[start]] == 1:
del dic[gems[start]]
else:
dic[gems[start]] -= 1
start += 1
else:
end += 1
if end == len(gems):
break
if gems[end] in dic.keys():
dic[gems[end]] += 1
else:
dic[gems[end]] = 1
return [temp[0]+1, temp[1]+1]
'코테 > 프로그래머스' 카테고리의 다른 글
프로그래머스 level2 [두 큐 합 같게 만들기] 파이썬 (0) | 2022.09.03 |
---|---|
프로그래머스 level1 [성격 유형 검사 하기] 파이썬 (0) | 2022.09.03 |
프로그래머스 level3 [ [1차] 셔틀버스] 파이썬 (0) | 2022.04.19 |
프로그래머스 level3 [N으로 표현] 파이썬 (0) | 2022.04.13 |
프로그래머스 level3 [하노이의 탑] 파이썬 (0) | 2022.04.11 |