23.08.01. 풀었던 문제들 복기

Leetcode 77. Combinations, 8분

 예전에 DFS로 순열/조합/중복순열/중복조합 코드를 썼었다. 코드야 그대로 쓰면 된다.

 예전에 짰던 게 제일 깔끔하게 짜였던 걸로 기억했는데, 이번에 안 보고 짠 것도 비슷하게 짜진다. 다행이군.

// Runtime 10 ms Beats 93.32%
// Memory 9.9 MB Beats 56.99%

class Solution {
public:
    vector<int> nums;
    vector<vector<int>> answer;
    void combination(int cur_d, int max_d, int prev_idx, vector<int>& result){
        if(cur_d == max_d){
            answer.push_back(result);
            return;
        }

        for(int i = prev_idx + 1; i<nums.size(); i++){
            result[cur_d] = nums[i];
            combination(cur_d+1, max_d, i, result);
        }
    }
    vector<vector<int>> combine(int n, int k) {
        for(int i = 1; i<=n; i++) nums.push_back(i);
        vector<int> result(k);

        combination(0, k, -1, result);

        return answer;
    }
};

 

 

 

BOJ 18310. 안테나, 21분

 처음에는 binary search로 푸는 문제인 줄 알았는데, 이 문제의 경우 parametric search의 형태가 아니다. 왜냐하면, binary search를 사용하기 위한 판정 함수가 O, X로 나타나지 않기 때문이다. 기준을 잡으면 O, X는 되는데,,, 기준을 뭘로 잡을지도 문제다. 양 옆을 계속 봐야 하니까. 이건 아닌 것 같지 않나?

 그래서 고민하다가... 정렬 후 가운데 위치면 결과가 최솟값일거라 생각해 그렇게 접근했고, 맞았다.

 중복을 지우면 안 되는 이유는 [1, 10, 10]을 보면 된다.

////////////////////// write your code below

// N = 20만, 범위는 10만
// BF로는 절대 못풀고, 아마 binary search인 듯.
// BS도 아닌 것 같기도 하고... OX로 표현할 수 있는 게 아님. 기준이 잡혀야 함.

int N;
vector<int> houses;	

void solve(){
	cin>>N;
	houses.resize(N);
	for(int i = 0; i<N; i++){
		cin>>houses[i];
	}	

	// sort
	sort(houses.begin(), houses.end(), less<int>());
	
	// get mid
	int mid = (N-1)/2;
	cout<<houses[mid];

	return;
}

 

시간복잡도

 O(nlogn)

 

 

 

BOJ 23742. Player-based Team Distribution, 27분

 그다지 어려운 문제는 아니었는데... 수식 실수로 오래 걸렸다.

 일단 첫 접근은

• +인 애들은 다 한 팀으로 묶고
• -인 애들은 다 따로따로 쓰면 되지 않을까?

였는데, [+ 팀에 아주 작은 - 하나를 더하면 결과값이 더 커지지 않나]? 에서 완벽한 솔루션을 얻었다. 이 때, 더하는 애들은 작은 순서부터 넣는게 더 많이 넣을 수 있기 때문에 절댓값이 작은 애들부터 넣으면 된다.

1. arr에서 +인 애들은 sum에 전부 다 더하고, 개수를 cnt에 넣는다.
2. 나머지 애들은 negs에 넣고 내림차순 정렬한다.
3. 이후 negs의 모든 element, neg에 대해
   1. sum * cnt + neg <= (sum + neg) * (cnt + 1)이 true면 그 neg는 + 그룹에 넣어도 된다. 아닌 경우 혼자인 팀으로 만들면 됨.
   2. 이 때, 좌항은 +는 그룹으로, neg는 개인으로 셌을 때이고, 우항은 +그룹에 neg를 넣었을 때 점수 총 합이다.

 이렇게 잘 만들었는데, 실수는

 sum * cnt + neg로 해야 하는데 sum * cnt - neg로 한 것

 그리고 sum * cnt과 neg를 합친 값과 (sum + neg) * (cnt + 1)을 비교했어야 했는데 sum * cnt와만 비교한 것. 2가지 이다.

int N;
vector<int> arr;

void solve(){
	cin>>N;
	arr.resize(N);
	for(int i = 0; i<N; i++) cin>>arr[i];

	ll sum = 0;
	int cnt = 0;
	vector<int> negs;
	for(int i : arr){
		if(i >= 0){
			sum += i;
			cnt++;
		}
		else negs.push_back(i);
	}
	sort(negs.begin(), negs.end(), greater<int>());

	ll negsum = 0;
	for(int neg : negs){
		if(sum * cnt + neg <= (sum + neg) * (cnt + 1)){
			sum += neg;
			cnt++;
		}
		else negsum += neg;
	}

	cout<<sum * cnt + negsum;
}

 

시간복잡도

 전부 다 O(n)의 for문만 돌고, 정렬에 O(nlogn)이 걸리니까 O(nlogn)

 

공간복잡도

 arr, negs 배열을 사용하므로 O(n)

 

후기

 실수가 뼈아프다. 아니었더라면...

 

 

 

BOJ 10502 덧셈, 62분

 처음에는 binary search로 접근했다... ㅋㅋㅋㅋ 부끄럽다.

 그렇게 생각한 이유가, [시작점]과 [끝점]을 알아야 한다고 생각했기 때문이다. 그러나, 위에서 언급했던 것과는 다르게 이 경우 O, X를 판별할 수는 있다. 그러나 그것을 기점으로 시작점을 당겨야 하는지, 끝점을 밀어야 하는지 알 수가 없다.

 때문에 다른 접근이 필요하다.

 

 sumToI라는 배열 하나를 두고, sumToI[i]는 1부터 i+1까지 합을 넣어두자.

 N이 주어졌을 때, 모든 sumToI를 순회하면서 N - sum이 i+1로 나눠 떨어지는지를 보자. 만약 나눠 떨어진다면, 

• 원래 1 + 2 + 3 + 4 + ...였던 것에
• 나눠 떨어진 몫을 더하면 된다. 예를 들어 6이라면 7 + 8 + 9 + 10 + ...가 된다. 

 이렇게 풀 경우, sumToI의 i는 더한 숫자의 개수를 의미하기 때문에 문제가 제시하는 가장 짧은 표현도 만족한다.

vector<ll> sumToI; // sumToI[i] : 1부터 i+1까지 sum

void init(){
	int i = 1;
	ll sum = 0;
	while(1){
		sum = (i+1) * i / 2;
		i++;
		if(sum > 1e9) break;
		sumToI.push_back(sum);
	}
}

void solve(){
	int N; cin>>N;

	for(int i = 0; i<sumToI.size(); i++){
		ll sum = sumToI[i];
		if(N < sum) break;
		if((N - sum) % (i+1) == 0 && i != 0){
			ll gap = (N - sum) / (i+1);
			cout<<N<<" = ";
			for(int n = 1; n<i+1; n++){
				cout<<n+gap<<" + ";
			}
			cout<<i+1+gap<<'\n';
			return;
		}
	}
	cout<<"IMPOSSIBLE\n";
}

 

시간복잡도

 sumToI vector의 size는 약 5만 정도이다. t가 얼마나 주어질지 모르긴 한데.. 한 번에 O(5만)으로 풀 수 있다. 대충 t=2000까지 커버할 수 있다.

 

공간복잡도

 O(5만)의 sumToI를 사용하므로 O(5만)

 

후기

 코테용 공부니까.. 일단 brute-force로 먼저 접근을 해 보자.

 

 

 

2485. 가로수, 7분

 문제를 읽고, [간격을 같게 하기 위한 최소 개수]를 만들기 때문에.. 간격들의 최대공약수를 사용하면 된다. GCD는 포스팅 링크에 정리해 두었다.

// GCD같다. 어떻게 하더라?

ll getGCD(ll a, ll b){
	ll r;
	while(b != 0){
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

void solve(){
	int N; cin>>N;
	vector<ll> positions(N), gaps(N-1);
	for(int i = 0; i<N; i++) cin>>positions[i];
	for(int i = 1; i<N; i++) gaps[i-1] = positions[i] - positions[i-1];

	ll GCD = getGCD(gaps[0], gaps[1]);
	for(int i = 2; i<N-1; i++){
		GCD = getGCD(GCD, gaps[i]);
	}

	ll answer = 0;
	for(ll gap : gaps){
		answer += gap / GCD - 1;
	}
	cout<<answer;
}

 

시간복잡도

 GCD의 시간복잡도는 O(log(min(a, b))). 입력 정수는 10억이므로 min(a, b)를 10억으로 잡아도 log(10억)은 얼마 안 된다.

 

공간복잡도

 입력을 저장하기 위한 용도로 N size vector 2개를 쓰므로 O(N)