• 30분정도 고민했을때 대략적인 아이디어가 떠오르면 max1시간까지 고민
• 30분동안 전혀 아이디어가 생각나지 않을경우 정답확인
• 매일 복습

그리디

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘이다. 현재 상황에서 가장 좋아보이는 것만을 선택하기 때문에, 정확한 답을 도출하지 못하더라도 그럴싸한 답을 도출하는데에 도움이된다. 하지만 코딩테스트에서는 대부분 최적의 해를 찾는 무제가 출제되기 때문에 그리디 알고리즘의 정당성을 고민하면서 문제 해결방안을 떠올려야 합니다.

• 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘 모두 그리디 알고리즘이다

1. 모험가 길드

---

공포도가 X인 모험가는 반드시 X명 이상으로 구성
몇명의 모험가는 마을에 남아도 된다
그룹의 최댓값 출력

• 책예제는 {2,3,1} {2,2}로 두었지만 3 제외한 {1,2}{2,2} 2 그룹도 괜찮나? 오름차순으로 시작? 내림차순으로 시작?
  테케가 부족...

  

  n = int(input())
  traveler = list(map(int, input().split()))
  traveler.sort(reverse=True)
  
  print(traveler)
  
  num = traveler[0]
  while num>0:
      # 1. 값을 줄여나가면서?
      # 2. 이중 for문을 사용?

  
  

정답보니까 어이없었음
내가구한 예시중 가장 최솟값이 될수있는걸 하나 골라서 코드구현에 집중하면 되는데 그냥 전체가 보이지 않는다고 포기한게 큰요인인듯.
그룹내 인원을 어떻게 체크할것인가, 공포도 비교부분을 생각하지못함. 기억하기

"""
모험가 길드
5
2 3 1 2 2
"""

n = int(input())
traveler = list(map(int, input().split()))
traveler.sort()

answer = 0
people = 0
for x in traveler:
    people +=1 
    if people >= x: # 현재 그룹에 포함된 모험가 수 >= 현재 확인 하고 있는 공포도 
        answer +=1
        people = 0
print(answer)

2. 곱하기 혹은 더하기

---

• 내코드 (30분, 시간복잡도 O(N))

"""
곱하기 혹은 더하기
02984
567
"""

# 처음에 0이면 무조건 합
# 도중에 0이면 앞부분은 합, 뒷부분은 곱
# 예시1 - 02984
# 예시2 - 002984
# 예시3 - 0020984

s = input()
snum = 0 #합
for c in s:
    if snum>0:
        if int(c)==0:
            snum+=int(c)
        else:
            snum*=int(c)
    else:
        snum+=int(c)
print(snum)

• 정답

data = input()
result = int(data[0]) # 첫 번째값 무조건 넣기
for i in range(1, len(data)):
    num = int(data[i])
    
    # 현재값<=1 거나 합<=1이면 덧셈 
    if num <= 1 or result <=1:
        result += num
    else:
        result *= num
print(result)

내코드의 경우 snum(총합)먼저 비교, 현재값 비교 순서
정답코드는 총합과 현재값을 동시에 비교해서 코드를 줄임

3. 문자열 뒤집기

---

• 에러
  문제 이해 못하고 한번에 바꿔버림. 이러면 더 작은값을 찾은 의미가 없음;;;

s = input()
zero = s.count('0')
one = s.count('1')

# 더 작은 값을 변경
if zero >= one:
    s=s.replace('0','1')
else:
    s=s.replace('1','0')
print(s)

• 정답코드
  바뀌는 순간의 갯수가 더 작은 값을 구하는 것

"""
문자열 뒤집기
0001100
000110011000
"""

data = input()
cn0 = 0 #전부0로 바뀌는 경우
cn1 = 0 #전부1로 바뀌는 경우
# 첫번째 원소
if data[0] =='1':
    cn0 +=1
else:
    cn1 +=1

# 두번째 원소부터 모든 원소 확인
for i in range(len(data) -1):
    if data[i] != data[i+1]:  #현재값[i] 다음값[i+1] 달라질 때
        #1로 바뀌는 경우
        if data[i+1] == '1':
            cn0 +=1
        else:
            cn1 +=1
print(min(cn0, cn1))

내코드는 각 갯수의 총합을 구해서 더 적은값만 출력하기 때문에 연속했을때 바뀌는 순간의 갯수를 구하지는 못함

4. 만들 수 없는 금액

---

• 에러

n = int(input())
money = list(map(int, input().split()))
money.sort()
answer = 0
ch = [0]*(money[-1]+1)
ch[0]=1

for i in range(1, len(money)+1):
    t1 = t2 = 0
    snum = 0
    snum += money[t2]
    t2+=1
    while t1 < t2:
        if snum==i:
            ch[i]=1
            t1=t2=0
        else:
            if snum >i:
                t1+=1
                snum-=money[t1]
            else:
                t2+=1
                snum+=money[t2]
        if t1 ==t2:
            print(i)
            break
    break

t1, t2를 사용해서 값을 줄이는 방식으로 하려 했는데
구현에서 막힘. 조건문을 어떤식으로 둬야할지, 탈출 조건에 대한 부분도 애매해짐.

• 정답

n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for x in data:
    if target < x:
        break
    # target >= x
    target +=x
print(target)

1 ~ target-1까지의 모든 금액을 만들 수 있는 상태이며
현재 확인하는 동전의 단위가 target 이하면 만들 수 없음.
코드는 이해됐는데 어떤 원리야...?

5. 볼링공 고르기

---

• 내코드
  10분

"""
볼링공 고르기
5 3
1 3 2 3 2

8 5
1 5 4 3 2 4 5 2
"""

from itertools import combinations, permutations
n, m = map(int, input().split())
k = list(map(int, input().split()))

perm = list(combinations(k,2))
answer=0
for x, y in perm:
    if x!=y:
        answer+=1
print(answer)

• 정답

n, m = map(int, input().split())
data = list(map(int, input().split()))
answer=0
# 볼링공 무게 리스트
array = [0]*11

# 무게에 해당되는 볼링공 갯수 구하기
for x in data:
    array[x]+=1

"""
n5 m3
볼링공 무게 리스트 : 1 3 2 3 2
"""

# 1-m까지 무게 처리
for i in range(1, m+1):
    n-= array[i] # A선택할 수 있는 개수 제외
    answer+= array[i]*n #B가 선택하는 경우의 수, 곱하기
print(answer)

6. 무지의 먹방 라이브

---

• 문제주소 : https://school.programmers.co.kr/learn/courses/30/lessons/42891

• 에러1
  문제 예제는 맞았으나 테케에서 우수수 터림...
  변경되는 인덱스를 어떻게 찾을것인가

  

def solution(food_times, k):
    answer = 0
    while k> 0:
        for _ in range(len(food_times)):
        	# 먼저 0으로 다 끝났을 경우
            if sum(food_times)==0:
                return -1
            k -= 1
            # 종료시, 출력 
            if k == 0:
                return food_times.index(1) #정확한 인덱스를 알아야함
            # 첫번째 값이 0이면 0을 추가해서 회전     
            if food_times[0]==0:
                food_times.pop(0)
                food_times.append(0)
            # 첫번째 값이 0이 아니면 0번째값에 -1하고 다시 집어넣기     
            food_times.append(food_times.pop(0) - 1)
    return answer
print(solution([3,1,2],5))

• 정답 - 우선순위 큐 사용
  시간이 작은 값대로 정렬후 다 먹었을때 시간 기준 계산

import heapq
def solution(food_times, k):
    answer = 0
    if sum(food_times) <= k:
        return -1

    q=[]
    for i in range(len(food_times)):
        heapq.heappush(q, (food_times[i], i+1))
    sum_value = 0
    previous = 0

    length = len(food_times)
    while sum_value + ((q[0][0] - previous)* length) <=k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous)* length
        length -= 1
        previous = now

    answer = sorted(q, key=lambda x: x[1])
    return answer[(k - sum_value)%length][1]

print(solution([3,1,2],5))