[9주차_월요일] 징검다리 건너기

[Jewan1120]

• 사이트 : 프로그래머스(PG)
• 문제: 징검다리 건너기
• 번호: 64062
• 레벨: Level 3

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[yeongleej]

🤔 시간복잡도 고려사항

• stones[i] <= 200,000,000(2억)
• stones의 개수 <= 200,000

=> 모든 돌이 2억의 크기를 갖고 있을 때 총 건널 수 사람의 수는 2억 => 사람의 수 이분탐색 : O(log2억) == 27.5754247590989, 약 28 (단, 이때 이분탐색은 밑이 2인 로그) => 모든 디딤돌 건너기 : 최대 200,000 => 총 시간복잡도 : O(200,000 * 28) 가능

💡 풀이 아이디어

• 매개변수 탐색으로 건널 수 있는 최대의 사람 수 구함
• 구해야 하는 것: 최대 사람 수
  • s: 0
  • e: Integer.MAX_VALUE (모든 돌이 2억의 크기를 갖고 있다면 총 2억명의 사람이 건널 수 있음)
• 결정 함수
  • 현재 사람 수(mid)가 모두 건널 수 있는 가
  • cnt : 건널 수 없는 돌
  • 건널 수 없는 돌이 연속으로 k개 이상되면 모든 사람이 건널 수 없음

    int cnt = 0;    // 건널 수 없는 돌의 개수 
    for(int i=0; i<stones.length; i++) {
    if(stones[i] - mid < 0) {
        cnt++;
    } else {
        cnt = 0;
    }
    // 건널 수 없는 돌의 개수가 연속으로 k개 이상되면 불가능
    if(cnt >= k) return false;
    }

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간 복잡도 : stones.length<=200_000 -> O(N^2) 불가
• 완전 탐색 -> 시간 초과 -> 이분 탐색으로 탐색 범위 줄여줌 ->O(N logN)

💡 풀이 아이디어

-문제에서 구하는 것 : 징검다리를 건널 수 있는 최대 니니즈 친구들의 수 구하기

• 한명씩 징검다리를 건너는 경우하여 돌을 줄이는 과정 -> 시간초과
• 이분탐색으로 특정 인원이 건널 수 있는지 여부만 확인 -> 매개변수 탐색
• mid : 건널 수 있는 사람의 수 (target)
  • mid명까지 건널 수 있으면 -> answer = mid 갱신 -> start = mid+1 // (mid+1)명까지 건널 수 있는지 확인
  • mid명까지 건널 수 없으면 -> end = mid-1 // 범위를 줄임
• 반복문 종료 : start <= end
  • check(mid명까지 건널 수 있는지 확인하는 함수)

   int cnt = 0; // 연속으로 건널 수 없는 돌의 개수
        for(int i = 0; i < stones.length; i++) {
            if(stones[i] < mid) { // 현재 돌에 mid명이 건너려고할 때 
                cnt++;
                if(cnt>=k) // 연속으로 건널 수 없는 돌이 k개 이상일 경우
                     return false; 
            } else cnt=0; // 연속성 끊김
        }

처음에 완전탐색으로 풀었었다가 시간 초과 났습니다..! 시간복잡도를 처음부터 잘 고려하기!

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= stone 배열 각 원소들의 값 <= 200,000,000
• 1 <= k: 한 번에 건너뛸 수 있는 디딤돌의 최대 칸 수 <= stone 배열의 길이
• 1 <= stone 배열의 크기 <= 200,000
• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한이라고 되어 있지만, 원소 값이 최대 200,000,000이기 때문에 니니즈 친구들의 최대 수도 200,000,000명이 됨
• O(200,000 log200,000,000) ≈ 500만

💡 풀이 아이디어

• 니니즈 친구들의 수를 조절하면서 이분탐색 진행

  • int s = 0, e = 200_000_001
  • boolean canGo: s와 e 값을 조절하면서 니니즈 친구들의 수가 정해졌을 때, 징검다리를 건널 수 있는지 확인
  • 배열을 순차적으로 탐색하며, stones[i] - m <= 0이 되는 연속적인 구간의 길이가 k이상이 된다면 징검다리를 건널 수 없음

  boolean canGo = true;
  for(int stone: stones) {
    if(stone - m < 0) cnt++;
    else cnt = 0;
  
    if(cnt >= k) canGo = false;
  }

• 돌을 건넌 사람의 최대 수를 구하는 문제이기 때문에 upper bound(e) 구하기

[baexxbin]

🤔 시간복잡도 고려사항

• stones[i] <= 200,000,000 (2*10^9)
• stones의 개수 <= 200,000 (2*10^6)
• 매개변수 이분탐색 시
  • 매 다리별로 건널 수 없는 돌 체크 (N)
  • 최대로 건널 수 있는 사람 수에 대해 이분탐색 (log(max(stones)))
  • Nlog(max(stones)), 약 200,000×28=5,600,000 < 1억 → 가능

💡 풀이 아이디어

• 매개변수 이분탐색
  • 탐색 값 mid: 다리를 건널 사람 수
  • 매개변수 조건: mid로 다리를 건널 수 있는지 (canGo())
    • 못건너는 돌멩이(다리 값 - mid <=0)가 연속 k개 이상이면 못건넘

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 이분탐색
• 시간복잡도: stones길이 1 이상 200,000 이하
  • 니니즈가 무제한이므로 완전탐색 시 시간초과
  • 이분탐색으로 풀이 시 O(logN) 으로 풀이 가능(+ 매개변수 탐색 시 O(N) 만큼 소요됨)

💡 풀이 아이디어

• 핵심은 "최대 친구들"이 다리를 건널 수 있는지, 없는지를 판단하는 것

  int right = 0;
  int right = 200_000_000;    //★친구들의 수를 최대값으로 지정
  while(left < right){
  int mid = (left + right)/2;
  //더 많은 친구들이 다리를 건널 수 있는지
  if(canGo(mid,stones,k)){
      left = mid+1;
      friends = Math.max(friends, mid);
  }else{
      //친구들이 다리를 건널 수 없다면 숫자를 줄이기
      right = mid;
  }
  }

[Jewan1120]

🤔 시간복잡도 고려사항

• stones 배열의 크기는 1 이상 200,000 → 2 x 10^5 이므로 O(N logN)이하로 가능

💡 풀이 아이디어

• k의 범위가 주어지고 그 안이 모두 0의 값이면 안됨 → 슬라이딩 윈도우
• 슬라이딩 윈도우 안의 최댓값들 중 최솟값을 구하는 문제
• Deque를 이용해서 슬라이딩 윈도우를 구현

  // 슬라이딩 윈도우를 만들 큐
  Deque<Integer> dq = new ArrayDeque<>();
  for (int i = 0; i < stones.length; i++) {
    // 최댓값(큐의 맨 앞)이 슬라이딩 윈도우의 크기를 벗어났다면 제거
    if (!dq.isEmpty() && dq.peekFirst() == i - k)
        dq.pollFirst();
    // 최댓값을 유지하며 현재 들어갈 요소보다 작은 값들 제거
    while (!dq.isEmpty() && stones[dq.peekLast()] <= stones[i])
        dq.pollLast();
    dq.offerLast(i); // 현재 돌의 인덱스 추가
    // 슬라이딩 윈도우가 완성되는 순간부터 최솟값 계산
    if (i >= k - 1)
        answer = Math.min(answer, stones[dq.peekFirst()]);
  }