Level 3 징검다리 건너기 <2019 카카오 인턴십> Python3

https://programmers.co.kr/learn/courses/30/lessons/64062?language=python3 

코딩테스트 연습 - 징검다리 건너기

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_징검다리건너기.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def solution(stones, k):
    answer = 0
    left = 1
    right = max(stones)
    while left <= right:
        mid = (left+right)//2
        blank = 0
        for s in stones:
            if s < mid:
                blank += 1
            else:
                blank = 0
            if blank == k:
                break
        if blank < k:
            left = mid + 1
            answer = mid
        else:
            right = mid - 1
    return answer

---

풀이 과정

 15분만에 빠르게 문제를 풀고 채점해보니 정확성만 다 맞고 효율성에서 시간초과가 났다..ㅠ 이후 35분동안 다른 풀이를 추가적으로 고민해봤는데 떠오르지 않았다. 이분 탐색을 적용해볼 생각을 못했다 ㅠㅠ 다음에 비슷한 문제를 푼다면 꼭 이분 탐색을 떠올리고 마리라!!

 

 문제에서 len(stones)의 최대 길이는 200,000이고, stones[i]의 최대 값은 200,000,000이라고 주어졌기 때문에 시간복잡도를 고려해야한다. 다리를 건너는 사람 수를 기준으로 이분 탐색을 진행하면 탐색하는 사람 수의 범위를 반씩 줄여나가기 때문에 O(log2 N)의 시간이 소요되고, 다리를 모두 통과할 수 있는지 확인하는데 최대 O(M)이 소요되므로 O(M log2 N)에 문제를 해결할 수 있다.

이때, N = max(stones), M = len(stones)이다.

 즉, 최악의 경우 N = 200,000,000이 될 수 있으며, M = 200,000이다.

따라서 약 5,500,000번의 연산이 발생한다.

def solution(stones, k):
    answer = 0
    
    #이분 탐색: 탐색 대상 = 사람 수, 범위 = 1~max(stones)
    left = 1
    right = max(stones)
    
    while left <= right:
        mid = (left+right)//2
        
        #mid 명의 사람들이 징검다리를 건너지 못하는 연속한 디딤돌 개수를 카운팅
        blank = 0
        for s in stones:
        	#현재 디딤돌의 숫자가 mid보다 작아 건널 수 없는 경우, blank 카운팅
            if s < mid:
                blank += 1
            #현재 디딤돌을 mid명의 사람이 건널 수 있는 경우, blank 초기화
            else:
                blank = 0
            #건널 수 없는 연속한 디딤돌의 개수가 k인 경우, mid명의 사람들은 징검다리를 건널 수 없다.
            if blank == k:
                break
        #mid명의 사람들이 모두 디딤돌을 건널 수 있는 경우
        if blank < k:
        	#현재 mid값을 answer값으로 갱신한 후, left 값을 조정하여 더 많은 사람들이 건널 수 있는지를 탐색한다
            left = mid + 1
            answer = mid
        #mid명의 사람들이 모두 디딤돌을 건널 수 없는 경우, right 값을 mid-1만큼 줄인다.
        else:
            right = mid - 1
    return answer
#시간복잡도 = O(M log N), 공간복잡도 = O(M)

---

오답 노트

• 정확성만 통과한 코드

풀이 시간 15분

 BFS 알고리즘을 구현하는 것처럼 queue를 통해 현재 건너고 있는 사람의 위치를 담아주었다. 한 사람씩 징검다리를 통과하도록 문제를 풀었기 때문에, O(N*M)의 시간복잡도를 가지기 때문에 시간 초과가 발생한다. 이때, N = max(stones), M = len(stones)이다.

from collections import deque
def solution(stones, k):
    q = deque()
    cnt = 0
    while True:
        q.append(-1)
        while q:
            now = q.popleft()
            for kk in range(1, k+1):
                new = now+kk
                if new >= len(stones):
                    cnt += 1
                    break
                if stones[new] > 0:
                    stones[new] -= 1
                    q.append(new)
                    break
        for kk in range(k):
            if stones[kk] > 0: break
        else:
            break
    return cnt

---

참고

• 1.크레인 인형뽑기 게임 -> https://hwayomingdlog.tistory.com/142

Level 1 크레인 인형뽑기 게임 <2019 카카오 인턴> Python 3

• 2. 튜플 ->2021.09.06 - [코테 노트/프로그래머스] - Level 2 튜플 <2019 카카오 인턴십> Python 3

Level 2 튜플 <2019 카카오 인턴십> Python 3

• 3. 불량 사용자 ->2021.08.31 - [코테 노트/프로그래머스] - Level 3 불량 사용자 <2019 카카오 개발자 겨울 인턴십> Python 3

Level 3 불량 사용자 <2019 카카오 개발자 겨울 인턴십> Python 3

• 4. 호텔 방 배정 ->