[Algorithm] Non-Constructible Value

  오늘 다룰 주제는 Non-Constructible Value(Change) 이다. positive integer 로 구성된 array 가 주어졌을 때, 각각의 원소들의 합으로 나타낼 수 없는 최소의 값을 Non-Constructible Value 라고 정의한다. 예를 들어, coins 배열이 [1, 2, 5] 로 주어졌을 때 각각의 원소들로 만들어낼 수 있는 값은 1, 2, 3, 5 이므로 Non-Constructible Value 는 4 이다. 

 

  가장 먼저 떠올릴 수 있는 방법은 주어진대로 꾸덕꾸덕 구현하는 것이다. 주어진 배열을 ascending order 으로 sorting 한 다음에 모든 원소들의 합을 구한다. 그러면 Non-Constructive Value 는 1~max_sum+1 중 하나일 것이 자명하다. Non-Constructible Value 인지 아닌지를 1부터 차근차근 검사해나가면 된다. 이를 위한 변수를 current_sum 이라고 하자. 검사한다는 것은 주어진 배열을 1회 순회하면서, 배열 내 원소들로 current_sum 을 만들어낼 수 있는지 아닌지를 체크한다는 것이다. 구현하기 전에 시간 복잡도를 간단하게 계산해보아야 한다. outer loop 에서 current_sum 을 1 부터 max_sum 까지 증가시킬 것이고 inner loop 에서는 given array 를 순회하면서 Constructible 한지 아닌지 판단하므로 O(N*M) 의 시간복잡도를 가지며 공간 복잡도는 O(1) 임을 알 수 있다. 이때 N 은 given array 의 size 이고 M 은 max_sum 이다.

 

  current_sum 이 Constructible 한지 아닌지를 판단하는 과정을 조금 더 자세하게 설명해보겠다. current_sum 보다 작거나 같은 원소를 마주하면, current_sum 에서 해당 원소의 값을 뺀다. 이를 모든 원소들에 대해서 반복하면, current_sum 이 0이거나 0 보다 클 것이다. current_sum 이 0이 되었다는 것은 해당 current_sum 은 Constructible 하므로 inner loop 를 탈출한다. current_sum 이 0보다 크다는 것은, current_sum 이 Non-Constructible 하다는 것이다. 왜냐면 array 내의 원소들의 합으로 current_sum 을 나타낼 수 없기 때문이다. 그러므로 current_sum > 0 이면, current_sum 을 반환하면 되는데 주의할 점은 current_sum 이 constructible 한지 아닌지 판단하는 과정에서 current_sum 에서 array 의 원소를 subtract 했으므로, current_sum 에 해당하는 outer index 반환해야 한다는 것이다.  만약 inner loop, outer loop 를 모두 탈출하게 되면 max_sum 이하로 Non-constructible Value 가 없다는 것이므로 max_sum+1 이 Non-constructible Value 가 된다. 이를 코드로 작성하면 아래와 같다.

#include <vector>
using namespace std;
// brute - force 
// time  : O(NM) -> N is # of coins , M is max_sum
// space : O(1)
int nonConstructibleChange(vector<int> coins) {
	// Write your code here.
	int max_sum = 0;
	int current_coin = 0;
	int current_sum = 0;
	sort(coins.begin(), coins.end());
	for (auto ele : coins) {
		max_sum += ele;
	}
	for (int i = 1; i < max_sum; i++) {
		current_sum = i;
		for (int j = coins.size() - 1; j >= 0; j--) {
			current_coin = coins[j];
			if (current_coin <= current_sum) {
				current_sum -= current_coin;
			}
			if (current_sum == 0) {
				break;
			}
		}
		if (current_sum > 0) {
          return i;
		}
	}
	return max_sum+1;
}

  위 방법을 optimize 한 하나의 loop 만으로 해결하는 clever 한 풀이가 존재한다. 시작은 동일하다. 주어진 array 를 ascending order 로 sorting 한 다음에, current_sum 을 0으로 초기화 한다.

 

  주어진 array 가 [1,2,5] 라면 해당 array 를 정방향으로 순회하면서 array[i] 와 current_sum+1 을 비교한다. 만약 array[i] > current_sum+1 이면 current_sum+1 은 Non-Constructible 하다. 처음에는 array[0] = 1 과 current_sum+1 = 1 을 비교할 것이고, 여기서는 array[0] == current_sum+1 이기 때문에 current_sum+1 이 Non-Construtible 하지는 않으므로 current_sum 에 array[0] 을 더해준다. 그러면 다음 반복에서는 array[1] = 2 이고, current_sum+1 = 2 인데 array[1] == current_sum+1 이므로 current_sum+1 이 Non-Constructible 하지 않으므로 array[1] 을 더해준다. 다음은 array[2] = 5 이고, current_sum+1 이 4 가 되고 array[2] > current_sum+1 이므로 current_sum+1 을 array 내의 원소들의 합으로 나타낼 수 없게 된다. 그러므로 current_sum+1 을 반환해주면 된다. 해당 풀이는 초기에 정렬을 해야하므로 시간 복잡도 O(nlogn) 이며 공간 복잡도는 O(1) 이다. 코드는 아래와 같다.

#include <vector>
using namespace std;

// solution2.cpp
// time  :  O(nlogn)
// space :  O(1)

int nonConstructibleChange(vector<int> coins) {
	// Write your code here.
	sort(coins.begin(), coins.end());
	int current_sum = 0;
	for (int i = 0; i < coins.size(); i++) {
		if (coins[i] > current_sum + 1)
			return current_sum + 1;
		current_sum += coins[i];
	}
	return current_sum + 1;
}

  실제 면접장이나 코딩테스트를 볼 때, 이와 같이 효율적인 방법이 바로 떠오르지 않을 가능성이 클 것 같다. 면접이라면 brute - force 방식을 먼저 구현하면서 clever 한 풀이로 가는 아이디어를 면접관을 통해 얻어내서 구현하면 될 것 같고, 코딩 테스트라면 constraint 를 잘 파악하고 brute-force 로 TLE 가 발생하지 않을것 같으면 고민하지말고 바로 구현해서 통과하는 것이 좋을 것 같다.

https://github.com/versatile0010/AlgoExpert

GitHub - versatile0010/AlgoExpert: Solutions to AlgoExpert Problems.