Programmers 12938: 최고의 집합

최고의 집합에 해당하는 조건은 아래와 같다.

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

1차 시도 - 최대한 유사한 값들을 곱하면 최대가 될 것이다.

동일한 값으로 먼저 나누고, 나머지를 +1씩 해 주도록 한다.

class Solution {
	public int[] solution(int n, int s) {
		LinkedList<Integer> answer = new LinkedList<Integer>();

		if (s / n == 0) {
			answer.add(-1);
		} else {
			answer.addAll(findSimilarElements(n, s));
		}

		return answer.stream().sorted().mapToInt(i -> i).toArray();
	}

	public LinkedList<Integer> findSimilarElements(int n, int s) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		int quotient = s / n;
		int remainder = s % n;

		for (int i = 0; i < remainder; i++) {
			list.add(quotient + 1);
		}
		for (int i = remainder; i < n; i++) {
			list.add(quotient);
		}

		return list;
	}
}

결과 - 시간초과

 

2차 시도 - sorting 부분을 지우자

1 <= n <= 10,000 이고 1 <= s <= 100,000,000이며 위의 경우는 sorting때문에 시간 복잡도가 O(NlogN)이었을 것이다.

아래와 같은 코드로 바꾼다면 O(N)만에 동작할 수 있다.

class Solution {
	public int[] solution(int n, int s) {
		LinkedList<Integer> answer = new LinkedList<Integer>();

		if (s / n == 0) {
			answer.add(-1);
		} else {
			answer.addAll(findSimilarElements(n, s));
		}

		return answer.stream().mapToInt(i -> i).toArray();
	}

	public LinkedList<Integer> findSimilarElements(int n, int s) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		int quotient = s / n;
		int remainder = s % n;

		int quotientNumber = n - remainder;

		for (int i = 0; i < quotientNumber; i++) {
			list.add(quotient);
		}
		for (int i = quotientNumber; i < n; i++) {
			list.add(quotient + 1);
		}

		return list;
	}
}

결과는 마찬가지로 시간초과...

 

3차시도 - 아무래도 stream부분과 list를 addAll하는 곳 때문에 시간 초과가 난 것 같다.

어차피 원소의 개수는 n개로 일정하기 때문에 LinkedList를 array로 바꾸는 방식이 아니라 바로 array를 구하도록 하자

class Solution {
	public int[] solution(int n, int s) {
		if (s / n == 0) {
			return new int[] { -1 };
		}

		return findSimilarElements(n, s);
	}

	public int[] findSimilarElements(int n, int s) {
		int[] answer = new int[n];
		int quotient = s / n;
		int remainder = s % n;

		int quotientNumber = n - remainder;

		for (int i = 0; i < quotientNumber; i++) {
			answer[i] = quotient;
		}
		for (int i = quotientNumber; i < n; i++) {
			answer[i] = quotient + 1;
		}

		return answer;
	}
}