[7주차_목요일] 최고의 집합

[KodaHye]

• 사이트 : 프로그래머스(PG)
• 문제: 최고의 집합
• 번호: 12938
• 레벨: level3

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

### 💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• 자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다. → 10^4이므로 O(N^2)이하의 탐색
• 근데 문제는 O(N)으로 풀어야함..
• 그리디

💡 풀이 아이디어

• 해당 수를 n개로 분리해서 곱했을 때 최댓값 → 최대한 평균 값들로 곱해줬을 때가 최대
• s의 값의 n번째 자리에 들어가야하는 수 구하기, 나머지 있을 경우 + 1

  // 오름차순으로 정렬하기 위해 뒤에서 부터 값 설정
  for (; n > 0; n--) {
    // 마지막 위치에 만들 수 있는 최댓값 설정
    answer[n - 1] = s / n;
    // 나머지가 존재한다면 +1
    if (s % n != 0)
        answer[n - 1]++;
    // s값 변경
    s -= answer[n - 1];
  }

  // n = 3, s = 10 인 경우로 가정
  1. n = 3: (10) / 3 → arr[n - 1] = 4
  2. n = 2: (10 - 4) / 2 → arr[n - 1] = 3
  3. n = 1: (10 - 4 - 3) / 1 → arr[n - 1] = 3

  나머지 처리를 answer[n - 1] = (int) Math.ceil((double) s / n);로 하니 시간초과나요.. 왜?

[yeongleej]

🤔 시간복잡도 고려사항

• 원소의 개수 n <= 10,000 => O(n^2) 이하의 풀이방법 생각하기

💡 풀이 아이디어

• n > s 이면 만들 수 없음

  • 최소 원소값은 1인데 1로 n개를 만들면 s를 넘으니깐 X

• n개의 원소의 곲이 최댓값이 되려면, 원소 간의 값 차이가 별로 안나야함

  • 즉, n개로 s를 만들 수 있는 최소 원소값 : s / n
  • 모든 원소의 기본값이 되므로 초기값은 s / n으로 채움
  • s / n의 나머지가 남았다면, 오름차순 정렬이므로 마지막 원소부터 1씩 증가
    • 예) n=3, s = 17
    • 17 / 3 = 5; 17 % 3 = 2;
    • answer = [5, 5, 5] -> 17을 만들기 위해 마지막 2개의 원소 1씩 증가
    • answer = [5, 6, 6]

[baexxbin]

🤔 시간복잡도 고려사항

• 자연수(원소)의 개수 n, 1 <= n <= 10,000 (10^4)
• O(N^2)이하로 풀기

💡 풀이 아이디어

• 무조건 가운데 값(숫자간 고르게 분포)가 곱이 가장 큼
• 숫자를 고르게 분포하도록 만들기
  • s/n 몫으로 n개만큼 분배
  • s%n 나머지는 뒤에서부터 하나씩 분배
• 예외처리
  • s<n 합이 분배할 수보다 작으면 분배 불가 if (s<n) return new int[]{-1};

처음에 홀수,짝수로 나눠서 2씩묶음 분배로 복잡하게 생각했는데,, 고르게 분포에 집중하면 엄청 간단하게 빨리 풀리는 문제였다!

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= n <= 10_000
• 1 <= 모든 원소의 합 <= 100_000_000
• 10_000 <= n의 개수 <= 100_000_000

집합의 원소는 중복을 허용함. 완전탐색을 할 경우 100_000_000H10_000가 되므로 시간 초과가 발생함

💡 풀이 아이디어

처음에 n의 개수가 명시적으로 적혀있지 않아서, 완탐으로 풀었으나 시간 초과 발생

• 그리디(?) 적인 사고로 풀이 수정
• 곱이 최대가 되기 위해서는 원소들이 중간 값으로 옹기종기 있어야 됨

  
  int div = s / n;
  int mod = s % n;

for(int i = 0; i < n; i++) { answer[i] = div; if(n - i <= mod) answer[i] += 1; }

> 완탐으로 푸는 문제인 줄 알았는데, 아니네요 !!!!!!! ㅠ ㅠ 문제를 잘 이해하고, 조건 잘 파악하좟

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간 복잡도 : s <= 10^8 O(N) 이하로 풀기

💡 풀이 아이디어

• 최고의 집합을 구하는 문제
• 최고의 집합 조건1 : 각 원소의 합이 S, 조건2 : 원소의 곱이 최대가 되는 집합
• s/n 값을 배열에 할당해주고, 배열 뒤쪽에서부터 큰 값을 count++

      int r = s%n;
      for(int i=n-1; i>=0; i--){
          answer[i] = s/n;
          if(r>0){
              answer[i]++;
              r--;
          }
      }
      return answer;

  시간초과 : 오름차순 정렬된 배열 리턴 Arrays.sort 했으나, 시간초과되어서 배열 뒤쪽에서부터 큰값을 할당해줬습니다 1 반환 아무 생각없이 return -1로 했었는데, 오류 발생 했었습니다 /Solution.java:12: error: incompatible types: int cannot be converted to int[] return -1; // -1 출력 문제가 요구한 반환값 잘 보기..!

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 그리디
• 시간복잡도: 자연수 개수 최대 10^4, 합 s는 최대 10^9

💡 풀이 아이디어

{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } 그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합

1. 각 원소의 합이 S가 되는 수의 집합
2. 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합

• 예제를 보면 조합 값들을 최대한 동일하게 만들어줬을 때 원소의 곱 이 최대가 될 수 있음

• S%N 나머지에 따라서 나머지가 없을 때까지 몫에 균등 분배하는 방식으로 최고의 집합을 구할 수 있음
  

  처음에 합 s의 크기가 크고, 정렬도 가능할 것 같아서 이분탐색으로 접근을 했는데, 결국 불가능한걸 알았어요! 이분탐색으로 풀이가 불가능한 이유? 이분탐색으로 풀이하면 O(logN) 으로 시간초과는 안되지만, 단일값을 검색하는게 아니고 조합을 찾아야하기 때문에 풀이가 불가능함 (최고의 집합은 중복 조합도 가능하기 때문에 이분탐색으로 불가)