알고리즘 스터디 - 그리디 3문제 풀이 (feat. 블로그2, 우체국, 공항)

백준 20365번 : 블로그2 - 실버 2

블로그2 같은 경우에는 블로그에다가 문제 풀이 결과를 색칠하는 문제로 가장 적게 색칠을 하는 수를 구하는 것이다.

위 사진처럼 색깔을 덮어써서 최소의 경우의 수를 구하는 것이다.

Test Case

1. N = 8 color = BBRBRBBR / answer = 4
2. N = 6 color = BRBBRR / answer = 3
3. N = 6 color = BRRRRB / answer = 2

이 케이스의 경우처럼 BB가 연속이면 B, RR이면 R로 하나의 경우로 쳐서 계산을 해야 한다는 것이다. 이 경우를 고려해서 문제를 풀었을 때 내 코드는 아래와 같다.

내 코드

n = int(input())
color = input()

blue, red = 0, 0

final = color[0]
if final == "R":
    red += 1
else:
    blue += 1

for i in range(1, n):
    if color[i] == "B":
        if final[-1] == "B":
            continue
        else:
            final += color[i]
            blue += 1
    else:
        if final[-1] == "R":
            continue
        else:
            final += color[i]
            red += 1

answer = 1
if blue >= red:
    answer += red
else:
    answer += blue

print(answer)

다른 사람 코드

import sys
input = sys.stdin.readline 

n = int(input())
p = input()
anw = p[0]

for i in p:
    if i != anw[-1]:
        anw += i

print(min(anw.count('B'), anw.count('R')) + 1)

내 코드를 돌렸을 때는 너무 많은 시간이 걸렸는데 다른 사람 코드를 보고 이렇게 최적화 할 수 있구나 하면서 나는 그러지 못한게 너무 아쉽다.

백준 2141번 : 우체국 - 골드 4

이 문제 같은 경우는 그리디인줄 모를 정도로 정렬 후 계산하는 문제만 존재하였다. 그럼에도 불구하고 골드 4인 이유는 테스트 케이스가 한 개만 있어서 다른 경우의 수를 생각하기 어렵기 때문이다. 예를 들어, 기존 테스트 케이스를 보게 되면 당연히 거리 순대로 인구 수와 동일하게 나온다고 생각할 수 있다.

3
1 3
2 5
3 3

하지만 그것만 보면 실패를 하게 된다. 왜냐하면 실제 입력은 순서대로 나오지 않고 섞이기 때문에 정렬하는 과정이 필요하다. 그리고 이 문제의 핵심은 오른쪽, 왼쪽이 전체 인구 수의 중간이 되는 최적의 위치를 찾는 것이다. 그래서 이를 적용하면 바로 문제가 풀리게 된다. 물론 4번만에 풀게 되었다.

알고리즘 코드

import sys

n = int(sys.stdin.readline())
village = []
total = 0

for _ in range(n):
    x, a = map(int, sys.stdin.readline().split())
    village.append([x, a])
    total += a

village.sort()

temp = 0
for i in range(n):
    temp += village[i][1]
    if (temp >= (total+1)//2):
        print(village[i][0])
        break

백준 10775번 : 공항 - 골드 2

이 문제는 공항에서 비행기가 착륙을 하는데 도킹할 수 있는 게이트의 최대 개수를 찾는 것이다. 여기서 일일이 빈 게이트를 찾는 것은 어려움이 존재하기 때문에 비어있는 게이트를 찾기 위하여 유니온-파인드 함수를 사용하여 찾게 된다. 근데 문제는 이게 왜 그리디일까 라는 의문이다. 물론, 그리디라고 말을 하면 가장 먼저 찾은 것을 도킹 해준다고 할 수 있지만 아직은 그리디인지는 의심이 간다. 그래도 분리 집합 (Disjoint Set)을 학습할 수 있어 좋았다.

import sys

g = int(sys.stdin.readline())
p = int(sys.stdin.readline())

def find(x):
    if gate[x] != x:
        gate[x] = find(gate[x])
    
    return gate[x]

def union(a, b):
    a = find(a)
    b = find(b)

    if a < b:
        gate[b] = a
    else:
        gate[a] = b

gate = [i for i in range((g+1))]

answer = 0
for i in range(1, p+1):
    docking = int(sys.stdin.readline())
    parent = find(docking)

    if parent == 0:
        break
    else:
        answer += 1
        union(parent, parent-1)

print(answer)