[3주차_목요일] 43236_징검다리

[Jewan1120]

• 사이트: 프로그래머스
• 문제: 징검다리
• 번호: 43236
• 레벨: Level4

[baexxbin]

🤔 시간복잡도 고려사항

• 1<=distance<=1,000,000,000 (10^9)
• O(NlogN)이내로 풀어야함

💡 풀이 아이디어

• 이분탐색 이용
• mid 값(최소 거리)이 가능하면 길이 키워보기(최소 길이 중 최대 값 찾기)
  • 최대거리 값을 찾아가는 과정 >> 이분탐색
  • removeCnt() >> 이분탐색 변수 조절
    • mid가 돌 사이간 최소거리가되려면 몇개의 돌을 지워야하는지
    • 지운 돌의 갯수가 n보다 작거나 같으면 mid거리 가능

이런 유형의 이분탐색은 항상 이분탐색 떠올리고 시간초과되는 조합으로 시도하는 이상한 습관이 있다... 더 연습 많이하기..

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= distance <= 1,000,000,000
• 1 <= 바위의 개수 <= 50,000
• distance 배열을 선형탐색하거나, 바위 배열을 2번 반복하기만 해도 1억 번의 연산을 넘음
• 이분탐색을 하면 O(lonN)으로 풀이 가능

💡 풀이 아이디어

• s, e를 조절하는 기준을 가능한 두 지점 사이의 최소 거리로 설정
• int tmp: 가능한 두 지점 사이의 최소 거리
• int s = 0, e = distance

while(s <= e) {
    tmp 값 구하기

    // 최소 길이가 middle가 될 수 있을 때
    // 제거해야되는 최소 돌의 개수
    int tmp = removeCnt(rocks, m, distance);

    // 제거해야되는 돌의 개수가 주어진 값보다 같거나 작으면
    // 현재 값이 작아서 다른 큰 값들이 많다는 의미
    // 현재 값의 크기를 키워줘야 됨
    if(tmp <= n) {
        answer = m;
        s = m + 1;
    // 제거해야 되는 돌의 개수가 주어진 값보다 크다면
    // 해당 값보다 작은 값들이 많아서 작은 거리을 없애기 위해 돌을 많이 없애야 된다는 의미
    // 현재 값을 줄여줘야 됨
    } else {
        e = m - 1;
    }
}

어떤걸 기준으로 해야되는지 고민을 많이 했습니당,,또 최소 돌의 개수를 구하는 것도 어떻게 해야되는지,, ㅠ 소프티어 문제랑 비슷한거 같은데, 다시 풀어도 어렵네요,,,ㅠ 이분 탐색 진짜 이번에 확실하게 넘어가야겠어요,,, 감으로 문제푸는 버리잣 ,,,,,,,,,,!!!

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ 바위의 개수 ≤ 50,000 → 10^4이므로 O(n^2)이하의 알고리즘 선택
• 특정 범위 내에서 최소 혹은 최대의 값을 찾는 문제 → 이분 탐색

💡 풀이 아이디어

• 정렬되지 않은 배열이므로 이분 탐색을 위해 정렬
• 이분 탐색의 타겟은 각 바위 사이의 최소 거리
  • 두 바위 사의 거리가 최소한 타겟 이상이 되어야 함
• 해당 타겟으로 지울 수 있는 돌의 수를 계산해서 n개 이하라면 값 갱신
  • n개 이하라면 아무 돌이나 치워서 n개를 만들 수 있기 때문에 상관없음
• 더 큰 최소 거리를 탐색하기 위해 왼쪽 경계 재설정

🔗 비슷한 문제

• 휴게소 세우기 해당 문제를 푼 후에 접근하면 쉬울 것 같습니다.

옛날에 풀었던 문제라 다시 한번 복기할 겸 풀어봤는데 어렵네요.. 아이디어 없으면 힘들었던 문제였습니다.

[yeongleej]

🤔 시간복잡도 고려사항

• distance <= 1,000,000,000
• distance가 충분히 크고 + 최소(or 최대)값을 찾는 문제이므로 이분탐색 고려

💡 풀이 아이디어

• 이분탐색을 이용해야 하므로 정렬 + 마지막 도착 지점인 distance 추가
• 구해야 하는 것: 바위간 거리의 최소값
• 시작, 끝 = (0, 도착지점)
• 이분탐색 제어 함수
  1. 제거해야 할 바위 수 카운팅
     • 마지막으로 건넜던 바위 저장(pre)
     • 제거해야 할 바위 수를 카운트
     • 현재 탐색하는 바위와 pre바위 사이의 거리가 mid값 보다 크면 제거
  2. 현재 최소거리(mid)가 가능한지 체크
     • 제거해야 할 바위 수가 n보다 작거나 같으면 가능 + 최소거리 증가하기
     • 그렇지 않으면 최소거리 감소

mid 값이 실제 바위들 간의 거리와 같아야 한다는 것에만 집중에서 숲을 보지 못했던 것 같습니다,,,,,, 이분탐색,,,,,, 크고 자세하게 보자

[icegosimperson]

🤔 시간복잡도 고려사항 시간 복잡도 : n:10억, O(log N)

💡 풀이 아이디어

• 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값 mid

• 거리가 일정하고 바위 순서가 바뀌지 않음 -> 이분탐색 사용

• 이분탐색 구조

      while(left <= right){
          int mid = (left + right)/2; 
          if(getRemovedRock(rocks, mid, distance) <= n){ // 바위 제거 개수가 작으면               
              answer = mid;
              left = mid  + 1;
          } else{
              right =  mid -1;
          }
      }

• 바위 제거 함수 : 몇개의 바위를 제거해야 하는지 계산

  public int getRemovedRock(int[] rocks, int mid, int distance){
      int before =0; // 출발지점
      int end = distance;  // 도착지점
      int removeCnt = 0; // 제거한 바위 개수
  
      for(int i=0; i<rocks.length; i++){
          if(rocks[i] - before < mid){ // 현재 바위와 이전 위치 사이의 거리가크면
              removeCnt++; // 바위 제거
          }
          else before = rocks[i]; // 바위 유지, 이전 위치를 현재 바위로 업데이트
      }
      if(end - before < mid) // 마지막 구간도 mid보다 짧으면 바위 제거
          removeCnt++; 
      return removeCnt;
  }

시간 복잡도를 고려할 때 이분 탐색을 떠올렸으나, 바위 제거를 이분 탐색으로 어떻게 구현 해야할 지 되게 막막했었습니다. 현재 바위 위치와 비교해서 갱신하는 것도 어려웠고,,, 더 연습해야겠습니다 ㅠ.ㅠ

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 이분탐색
• 시간복잡도: 1 ≤ distance ≤ 10^9 크기로 O(logN)

💡 풀이 아이디어

• 이분탐색의 중간 값을 구간의 0~distance 거리의 중간점으로 해서 구간의 최소거리를 구하는 이유?
  • 중간 값은 이분탐색을 위한 최소 거리의 후보이고, 이 값을 기준으로 바위 사이의 구간이 가능한 최소 거리인지 확인
• 제거해야 하는 바위 수를 세는 이유?
  • 돌을 제거하지 않으면, 어떤 돌 사이의 거리가 너무 짧아 최소 거리를 크게 만들 수 없음
  • 만약 돌을 제거하면 제거한 길이만큼 다음 바위의 구간이 늘어남