[이분 탐색] 백준 3020: 개똥벌레

문제: 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N(짝수)미터, 높이는 H미터이다. 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가며 등장한다. (석순은 밑에서 자라나고, 종유석은 위에서 자라난다.)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다. 가령 4번째 구간으로 개똥벌레가 날아간다고 하면, 3번째 석순과 4번째 석순의 사이 정도인 높이를 날아간다고 보면 된다.

 

이 때, 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간이 몇 개 있는지 구하는 프로그램을 작성하시오.

---

입력: 첫째 줄에 N과 H가 주어진다. N은 항상 짝수.

다음 N개의 줄에 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

---

 

사실 문제만 놓고 보면 정말 간단해 보인다. 설명만 잘 따라가도 충분히 답을 낼 수 있으니 말이다.

아래의 코드는 단순히 답을 구해보기 위한 코드이다.

def find(i):
    crush_cnt = 0
    for k in range(len(huddle)):
        if k % 2: # 홀수일 때, 즉 종유석(위에서 자라남)일 때
            # 종유석의 길이와 동굴의 높이를 가지고 몇m 이상 비행하면 부딪히는지를 판별해보자
            if huddle[k] + i > H:
                crush_cnt += 1
        else: # 석순일 때
            if huddle[k] >= i:
                crush_cnt += 1

    return crush_cnt

N, H = map(int, input().split()) # N: 동굴의 길이, H: 동굴의 높이
huddle = []
for i in range(N):
    huddle.append(int(input()))

# huddle에는 석순과 종유석이 번갈아가며 저장되어있는 상태이다. 석순은 아래서부터, 종유석은 위에서부터 자라난다.
# 개똥벌레가 날 수 있는 높이의 범위는 1 ~ H
save_min = [200000] # 최소로 부딪히는 경우의 값을 저장할 리스트. 최댓값이 20만
for i in range(1, H + 1):
    temp = find(i)
    if save_min[0] > temp: # 값이 갱신될 때
        save_min = [temp]
    elif save_min[0] == temp: # 최솟값과 같을 때
        save_min.append(temp)

ans = len(save_min)
print(save_min[0], ans)

자 이제 이 코드를 돌려보면?

4퍼센트에서 짤없이 시간초과가 뜰 것이다. 우린 여기서 한가지를 더 고려해줘야 한다.

그건바로 '유망성 조사'.

간단히 말해 이런거다. 3문제 이상 틀리면 과락인 시험이 있다고 하자. 근데 첫 페이지에서 4개를 틀려버렸다. 그 뒷부분을 메겨볼 필요가 있을까? 없다.

 

유망성조사를 고려한 코드는 아래와 같다.

def find(i):
    crush_cnt = 0
    for k in range(len(huddle)):
        if k % 2: # 홀수일 때, 즉 종유석(위에서 자라남)일 때
            # 종유석의 길이와 동굴의 높이를 가지고 몇m 이상 비행하면 부딪히는지를 판별해보자
            if huddle[k] + i > H:
                crush_cnt += 1
        else: # 석순일 때
            if huddle[k] >= i:
                crush_cnt += 1
        if crush_cnt > save_min[0]:
            break

    return crush_cnt

N, H = map(int, input().split()) # N: 동굴의 길이, H: 동굴의 높이
huddle = []
for i in range(N):
    huddle.append(int(input()))

# huddle에는 석순과 종유석이 번갈아가며 저장되어있는 상태이다. 석순은 아래서부터, 종유석은 위에서부터 자라난다.
# 개똥벌레가 날 수 있는 높이의 범위는 1 ~ H
save_min = [200000] # 최소로 부딪히는 경우의 값을 저장할 리스트. 최댓값이 20만
for i in range(1, H + 1):
    temp = find(i)
    if save_min[0] > temp: # 값이 갱신될 때
        save_min = [temp]
    elif save_min[0] == temp: # 최솟값과 같을 때
        save_min.append(temp)

ans = len(save_min)
print(save_min[0], ans)

근데 얘도 4퍼에서 시간초과가 뜬다. 뭐가 문제일까... 고민을 좀 했다.

문제를 다시 살펴봤다. 한가지 좋은 아이디어가 머리를 스친다.

리스트에 종유석과 석순의 길이를 쭉 받는다. 얘네를 종유석 리스트와 석순 리스트로 나눈 후 각각의 리스트를 오름차순이든 내림차순이든 정렬한다면?

그러고 나서 특정 범위의 길이만 구할 수 있다면(비행 높이에 따라 부딪힐 가능성이 있는 종유석과 석순의 길이가 다를 것인데, 그 범위를 특정지을 수 있기에 정렬된 리스트 내의 길이를 통해 쉽게 구할 수 있을 것)

 

해당 로직을 코드로 구현하면 다음과 같다.

N, H = map(int, input().split()) # N: 동굴의 길이, H: 동굴의 높이
huddle = []
for i in range(N):
    huddle.append(int(input()))

seuk = [] # 석순, 아래서 자람
yous = [] # 종유석, 위에서 자람
for i in range(len(huddle)):
    if i % 2: # i가 홀수 -> 짝수번째 요소 -> 종유석
        yous.append(huddle[i])
    else: # 석순
        seuk.append(huddle[i])

seuk.sort()
yous.sort()

# 종유석 목록과 석순 목록을 따로 분류해둠
# print(seuk) # [1, 2, 3, 3, 3, 3, 4]
# print(yous) # [2, 2, 3, 3, 3, 4, 4]

# 비행 높이가 i -> 석순의 경우 i 이상일 때 부딪힘, 종유석의 경우 i + 종유석 길이가 H보다 커질 때 부딪힘
# 석순과 종유석의 부딪힘 포인트를 저장하자
seuk_point = len(seuk)
yous_point = len(yous)
ans_point = -1 # 최대치보다 높음
ans_count = 0
for i in range(1, H+1):
    for j in range(len(seuk)):
        if seuk[j] >= i: # 부딪힘
            seuk_point = j
            break

    for k in range(len(yous)):
        if yous[k] + i > H:
            yous_point = k
            break

    if seuk_point + yous_point > ans_point: # 갱신될 때
        ans_count = 1 # 이때부터 다시 카운트 해야하므로
        ans_point = seuk_point + yous_point
    elif seuk_point + yous_point == ans_point: # 같을 때
        ans_count += 1 # 가짓 수 추가

    seuk_point = len(seuk)
    yous_point = len(yous)

# len - point -> 부딪힐 개수
# N - ans_point
print(N - ans_point, ans_count)

결론은 또 시간초과. 위 로직에서 시간초과가 날만한 부분은 크게 2가지가 있다고 생각한다.

1. 길이가 매우 긴 list를 sort하는 과정

2. sort된 list를 순회하며 부딪힘의 시작지점을 찾는 과정

 

1번의 경우 어쩔 수 없는 부분이라 생각한다. sort를 하여 일종의 가지치기를 할 수 있다고 생각했기 때문.

그럼 2번은? 위의 로직과 같이 전체 list를 순회하는 것이 아닌 이분탐색을 활용하여 필요한 인덱스를 빠르게 찾아내는게 시간단축에 효과적일 것이라는 생각이 들었다.

 

아래는 이분탐색을 활용한 코드.

def find_idx_seuk(i):
    # 이분탐색을 활용, 부딪히기 시작하는 인덱스를 찾아내자.
    # 석순의 경우 i와 같거나 큰 값이 시작되는 부분을 찾으면 된다.
    start = 0
    end = len(seuk) - 1
    while end - start > 1:
        middle = (start + end) // 2
        if seuk[middle] >= i:
            end = middle
        elif seuk[middle] < i:
            start = middle

    if seuk[start] >= i:
        return start
    else:
        if seuk[end] >= i:
            return end
        else:
            return len(seuk)

def find_idx_yous(i):
    # 이분탐색을 활용, 부딪히기 시작하는 인덱스를 찾아내자.
    # 종유석의 경우 i와 종유석의 길이의 합이 H보다 커지는 값이 시작되는 부분을 찾으면 된다.
    start = 0
    end = len(yous) - 1
    while end - start > 1:
        middle = (start + end) // 2
        if i + yous[middle] > H:
            end = middle
        elif i + yous[middle] <= H:
            start = middle

    if i + yous[start] > H:
        return start
    else:
        if i + yous[end] > H:
            return end
        else:
            return len(yous)

N, H = map(int, input().split()) # N: 동굴의 길이, H: 동굴의 높이
huddle = []
for i in range(N):
    huddle.append(int(input()))

seuk = [] # 석순, 아래서 자람
yous = [] # 종유석, 위에서 자람
for i in range(len(huddle)):
    if i % 2: # i가 홀수 -> 짝수번째 요소 -> 종유석
        yous.append(huddle[i])
    else: # 석순
        seuk.append(huddle[i])

seuk.sort()
yous.sort()

# 종유석 목록과 석순 목록을 따로 분류해둠
# 비행 높이가 i -> 석순의 경우 i 이상일 때 부딪힘, 종유석의 경우 i + 종유석 길이가 H보다 커질 때 부딪힘
# 석순과 종유석의 부딪힘 포인트를 저장하자
len_seuk = len(seuk)
len_yous = len(yous)
seuk_point = len(seuk)
yous_point = len(yous)
ans = 1000000
ans_count = 0
for i in range(1, H+1):
    seuk_point = find_idx_seuk(i)
    yous_point = find_idx_yous(i)
    semi_ans = len_seuk - seuk_point + len_yous - yous_point
    if semi_ans < ans:
        ans = semi_ans
        ans_count = 1
    elif semi_ans == ans:
        ans_count += 1

print(ans, ans_count)

문제의 조건에 따라 이분탐색을 하는 방식이 조금씩 변형되는데, 아직 연습이 부족해 코드가 바로바로 짜지진 않는 것 같다. 문제 좀 많이 풀어봐야겠다.