[탐욕법/그리디(Greedy)] 문제풀이

백준 : 1439번 뒤집기

1439번: 뒤집기

내가 쓴 코드

s = input()
N = list(s)
zero, one = 0, 0

if N[0] == "0":
    zero += 1
else:
    one += 1

for i in range(1, len(N)):
    if N[i] != N[i-1]:
        if N[i] == "0":
            zero += 1
        else:
            one += 1

print(min(zero, one))

남이 쓴 코드

s = input()
cnt = 0
prev = '?'

for i in s:
	  if i != prev:
        prev = i
        cnt += 1

print((cnt)//2)

입력 받은 string에서 문자가 바뀔 때마다 cnt += 1을 해준다. cnt는 변화 횟수를 답고 있고 우리는 0 또는 1 둘 중 하나로만 바꾸면 되기 때문에 //2 해주면 된다. 맨 앞 문자도 cnt에 포함해주어야 하기 때문에 prev를 ‘?’로 설정해서 첫 문자가 0이든 1이든 cnt에 포함될 수 있도록 해준다.

[참고][https://codingpractices.tistory.com/72](https://codingpractices.tistory.com/72)

프로그래머스 : 무지의 먹방 라이브

코딩테스트 연습 - 무지의 먹방 라이브

def solution(food_times, k):
    low, high = 0, 100000000
    n = len(food_times)
    cutting = 0 # 모든 음식에 공통으로 뺄 숫자
    ltime = 0 # 마지막 인덱스를 가리킬 때의 시간
    
    # 이분탐색
    # low가 high보다 커지면 탈출
    while low <= high:
        mid = (low + high) // 2 # 모든 음식에 공통으로 뺄 숫자
        v = n * mid # 마지막 인덱스를 가리킬 때의 시간
        
        # 모든 음식에 공통으로 mid만큼 뺀다.
        # 뺐을 때 음수값을 가지면, 그만큼 v에서 빼준다.
        # 음수값만큼 해당 음식을 먹지 못했기 때문에 마지막 음식을 더 빨리 기리키게 될 것
        for f in food_times:
            tmp = f - mid
            if tmp < 0:
                v += tmp
        
        # v가 k보다 작거나 같으면
        if v <= k:
            # cutting과 ltime을 일단 mid와 v로 바꿔주고
            cutting, ltime = mid, v
            # 더 큰 cutting, ltime 값이 없을지 찾아본다
            low = mid + 1
        # v가 k보다 크면 말이 안되므로 high = mid-1로 범위를 변경하여 다시 해준다.
        else:
            high = mid - 1
    
    # 앞서 이분탐색으로 찾은 cutting 값을 모든 음식에서 빼준다.
    food_times = [f-cutting for f in food_times]
    
    for i in range(n):
        # 만약 먹을 음식이 남아있고 ltime과 k가 같다면 해당 음식의 인덱스 리턴
        if food_times[i] > 0 and ltime == k:
            return i+1
        else:
            # 만약 먹을 음식이 남아있고 ltime과 k가 같지 않다면 ltime에 1을 더해주고 다음 음식을 탐색한다
            if food_times[i] > 0:
                ltime += 1
            # 만약 먹을 음식이 남아있지 않다면 시간이 소요되지 않으므로 그대로 다음 음식으로 간다
    
    # 먹을 음식 없으면 -1
    return -1

헉 너무너무 어려웠다.. ㅠㅠ

아래 링크를 참고해서 이분탐색을 사용해 풀었다!!

우선순위 큐를 사용하는 방법 → 여기

[참고] https://onejunu.tistory.com/73