[TIL]Day 136
탐욕법(Greedy)
- 부분적인 최적해가 전체적인 최적해
- 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택
- 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 ==
앞 단계에서의 선택이 이후 단계에서의 동작에 의한 해의 최적성에 영향을 주지 않음
프로그래머스 탐욕법 문제 풀기
체육복
- 빌려줄 학생들을 "정해진 순서"로 살펴야하고, 이 "정해진 순서"에 따라 우선하여 빌려줄 방향을 정해야함.
학생 수만큼 배열을 확보하고, 여기에 각자가 가지고 있는 체육복의 수를 기록한다. -> 번호 순서대로 "스캔"하면서 빌려줄 관계를 정한다. - ! 코드 구현의 편의성을 위해 앞 뒤에 원소 추가
- 학생수는 극단적으로 많고 여벌의 체육복을 가져온 학생은 매우 적다면?
- 여벌의 체육복을 가져온 학생들의 번호를 정렬(O(klogk)시간 복잡도이기 때문에 n이 크고 k가 작을때만 의미있음. n은 전체길이 k는 여벌의 체육복 길이)하고, 이것을 하나하나 순서대로 살펴보면서 빌려줄 수 있는 다른 학생(해시)을 찾아서 처리한다.
방법 1 - O(n)
def solution(n, lost, reserve):
students = [1] + [1 for _ in range(n)] + [1]
for i in reserve:
students[i] = 2
for i in lost:
students[i] -= 1
for i in range(len(students)):
if students[i] == 0:
if students[i+1] == 2:
students[i+1] = 1
students[i] = 1
elif students[i-1] == 2:
students[i-1] = 1
students[i] = 1
return students.count(1) + students.count(2) -2
def solution(n, lost, reserve):
u = [1]*(n+2)
for i in reserve:
u[i] += 1
for i in lost:
u[i] -= 1
for i in range(1,n+1):
if u[i-1] == 0 and u[i] == 2:
u[i-1:i+1] = [1,1]
elif u[i] == 2 and u[i+1] == 0:
u[i:i+2] = [1,1]
return len([x for x in u[1:-1] if x > 0])
방법 2 - O(klogk)
def solution(n,lost,reserve):
s = set(lost) & set(reserve)
l = set(lost) - s
r = set(reserve) - s
for x in sorted(r):
if x -1 in l:
l.remove(x - 1)
elif x + 1 in l:
l.remove(x + 1)
return n - len(l)
def solution(n, lost, reserve):
answer = n - len(lost)
tmp = list(set(lost) & set(reserve))
for i in tmp:
lost.remove(i)
reserve.remove(i)
answer = answer + len(tmp)
for i in lost:
for j in reserve:
if j in [i-1,i,i+1]:
reserve.remove(j)
answer = answer + 1
break
return answer
d[i]를 0이 아닌 1로 두는 이유는 0이면 if절에서 False로 인식하기 때문
def solution(n, lost, reserve):
lost_set = set(lost)
reserve_set = set(reserve)
intersection = lost_set & reserve_set
reserve_set -= intersection
lost_set -= intersection
reserve = sorted(list(reserve_set))
d = {}
for i in lost_set:
d[i] = 1
for i in reserve:
if d.get(i-1,False):
del d[i-1]
elif d.get(i+1,False):
del d[i+1]
return n - len(d)
큰 수 만들기
- 앞 자리에 큰수가 와야함.
- 앞 자리에서부터 하나씩 골라서 담되, 지금 담으려는 것보다 작은 것들은 도로 뺀다. 단, 뺄수 있는 수효에 도달할때까지
- 큰 수가 앞 자리에, 작은 수가 뒷 자리에 놓이도록
- (제약조건) 뺄수 있는 숫자의 수
- 주의할점 이미 순차적으로 되어있는 경우
def solution(number, k):
stack = [number[0]]
for num in number[1:]:
while k > 0 and stack and stack[-1] < num:
k -= 1
stack.pop()
stack.append(num)
if k > 0:
stack = stack[:-k]
return ''.join(stack)
조이스틱
- 맨처음 생각한 방식은 순차적으로 보면서 왼쪽 혹은 오른쪽으로 이동하는것 중에 최적을 계산했다.
- 그러나 순차적이기보단 지금내 포커스에서 가장 이동이 적은 것들을 처리해나가는 방식이 맞다.
- 예를들어 ABAAAACHG가 있으면 1번 인덱스 B 처리하고 마지막 인덱스 G 처리하고 그다음 G옆에 H 처리하고 이런식으로...
def solution(name):
answer = 0
items = [(i,min(ord(t) - ord("A"),ord("Z") - ord(t) + 1)) for i,t in enumerate(name) if t != 'A']
cur = 0
while items:
tmp = get_min_move(items,cur,len(name))
answer += tmp[0]
cur = tmp[1]
return answer
def get_min_move(items,cur,length):
tmps = []
for i,item in enumerate(items):
tmps.append((abs(item[0]-cur),i,item[1],item[0]))
tmps.append((cur+length-item[0],i,item[1],item[0]))
min_item = min(tmps)
items.pop(min_item[1])
return (min_item[0]+min_item[2],min_item[3])
Author And Source
이 문제에 관하여([TIL]Day 136), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@du-du-zi/TILDay-136저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)