[6주차_화요일] 공유기 설치

[icegosimperson]

• 사이트 : 백준(BOJ)
• 문제: 공유기 설치
• 번호: 2110

🤔 시간복잡도 고려사항
💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• 2 ≤ N ≤ 200,000 → 2 x 10^5이므로 O(N logN)
• 이분 탐색 혹은 매개 변수 탐색

💡 풀이 아이디어

• 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치 → 매개 변수 탐색의 UpperBound를 출력
  • 매개 변수 : 두 공유기 사이의 최소 거리
  • 결정 함수 : 해당 매개 변수의 거리로 공유기를 설치 했을 때 설치하려는 공유기의 수보다 많은지 확인

    private static boolean isPossible(int param) {
    int cnt = 1;
    int prev = 0; // 마지막으로 공유기가 설치된 집의 인덱스
    for (int i = 1; i < n; i++) {
    // 마지막으로 설치된 집과의 거리가 param보다 크다면 공유기 설치
    if (arr[i] - arr[prev] >= param) {
        cnt++;
        prev = i;
    }
    }
    // 많이 설치되도 됨 -> 몇 개 지워버리면 되니깐
    return cnt >= c;
    }

[yeongleej]

🤔 시간복잡도 고려사항

• 집의 개수: N ≤ 200,000
• 공유기 개수: C ≤ 200,000
• 좌표 xi ≤ 1,000,000,000 => 두 공유기 사이의 최대 거리는 1,000,000,000가 될 수 있으므로 이분탐색 고려

💡 풀이 아이디어

• 구해야 하는 것(mid): 두 공유기 사이의 거리
  • 시작값: 0
  • 끝값: (마지막집의 좌표 - 첫번쨰 집의 좌표) == 최대거리
• 매개변수 탐색
  • 결정문제: 설정한 공유기 사이의 거리(mid)값으로 C개의 공유기를 설치할 수 있는가 없는가의 문제
  • mid의 거리로 공유기를 설치했을 때의 필요한 개수가 C보다 작다면, 거리를 좁혀야 함
  • mid의 거리로 공유기를 설치했을 때의 필요한 개수가 C보다 크거나 같다면 거리를 좀 늘릴 수 있음
• 좌표값이 1억보다 크므로 long으로 설정

[baexxbin]

🤔 시간복잡도 고려사항

• 2 ≤ N ≤ 200,000 → 2 x 10^5
• O(N logN)

💡 풀이 아이디어

• 이분탐색, 매개변수 탐색 이용
• 이분탐색: 가능한 최대 거리 mid 구하기
• 결정조건: canWifi()
  • 거리 dist에서 공유기 개수: C가 가능한지
  • 현재 집 - 이전 집의 거리가 설정한 dist보다 크거나 같으면 공유기 설치

[KodaHye]

🤔 시간복잡도 고려사항

• 2 <= 집의 개수 <= 200,000이기 때문에 집에 대해 이중 반복문 사용 X
• 공유기 사이의 최대 거리에 따른 설치해야 되는 공유기의 개수를 구하면서 이분탐색 진행하기 (O(NlogN))

💡 풀이 아이디어

• 두 공유기 사이의 거리를 최대로 하는 프로그램 작성 → UpperBound
• int s, e, m: 공유기 사이의 거리 조절
• int cnt: 설치해야되는 공유기 개수
• int getCnt(int m, int[] arr): 설치해야되는 공유기의 개수를 구하는 함수

[icegosimperson]

🤔 시간복잡도 고려사항 시간 복잡도 : N, C <= 200,000 xi <= 10^9 -> 이분 탐색 시간 복잡도를 줄여줘야함 -> O(N logN)

💡 풀이 아이디어

• 가장 인접한 두 공유기 사이의 최대 거리를 출력
• 공유기 사이의 최소 거리를 mid값으로 두어 UpperBound

  while(s <= e){
          int first = houses[0];
          int count = 1;
          int m = (s+e)/2; // mid = 공유기 사이의 최소 거리
          for(int i=1; i<N; i++){
              if(houses[i] - first >= m){
                  count++;
                  first = houses[i];
              }
          }
          if(count>=C){ // 공유기를 더 설치할 수 있는 경우
              ans = m;
              s = m+1; 
          } else e = m-1; 
  }

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 이분탐색
• 시간복잡도: 집 갯수 (2 ≤ N ≤ 200,000) 으로 10^5
  • 이분탐색으로 풀이할 경우 O(logN) 으로 풀이가능

💡 풀이 아이디어

• 정해진 공유기 수를 설치한 집 사이 "거리의 최대값" 찾기
  • mid 값을 기준으로 거리 간격을 조정하기 때문에 거리의 최대값 후보가 됨
  • 간격을 조정하면서 mid값이 최적의 거리의 최대값이 되도록 함
• while(left <= right)
  • left와 right가 겹치는 구간을 포함해 한 번 더 탐색을 진행함으로써 최적의 결과를 보장할 수 있게 됨
  • left = mid + 1
  • 현재 설정한 간격으로도 충분히 공유기를 설치할 수 있으므로, 더 큰 간격이 가능한지 확인하기 위해 간격을 넓힌다.
  • left를 움직여 mid 값을 키움으로써 간격을 넓힘.
• right = mid-1
  • 더 많은 공유기를 설치하기 위해 간격을 좁힌다
  • right를 움직여 mid 값을 줄임으로써 간격을 좁힘.