[알고리즘/프로그래머스] 체육복 - C++

오늘도 알바를 마치고 어김없이 달린다.

알고리즘 공부해서 미래에 있을 코딩테스트를 뿌시자.

*본인은 C++로 코딩할 예정이다.

---

1. 문제

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다.

다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다.

학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.

예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다.

체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

 

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost,

여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때,

체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

출저 - 프로그래머스

2. 사고 - 탐욕법

1. 학생의 수만큼 배열을 만들고, 가지고 있는 체육복 수를 지정한다.

2. 맨앞과 맨뒤에 배열을 추가하여 구현시 편리하게 만든다.

3. 모두 1로 지정하고, reserve 학생들은 +1, lost는 -1을 준다.

4. 순환하면서 체육복을 빌려줄 수 있을때(2일때), 작은번호가 0이면 체육복을 빌려주며 수를 수정한다.

5. 0이 아니면 뒷번호 역시 조사하여 조건에 맞으면 조정한다.

6. 알고리즘 복잡도는 for문이 3번 돌며 총 O(n)의 복잡도를 가지게 될 것이다.

3. 코딩

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
	int answer = 0;
	//vector<int> v;
	vector<int> v(n+2, 1);
	//for (int i = 0; i <= n+1; i++) {
	//	v.push_back(i);
	//	v[i] = 1;
	//}
	for (auto &j : lost)v[j]--;
	for (auto &k : reserve)v[k]++;
	for (int i = 1; i <= n; i++) {
		if (v[i]==2 && v[i-1]==0) {
			v[i - 1]++;
			v[i]--;
		}
		else if (v[i] == 2 && v[i + 1] == 0) {
			v[i + 1]++;
			v[i]--;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (v[i] >= 1) {
			answer++;
		}
	}
	return answer;
}

int main(void) {
	int num = 5;
	vector<int> lost;
	lost.push_back(2);
	lost.push_back(4);
	vector<int> reserve;
	reserve.push_back(3);

	cout << solution(num, lost, reserve) << endl;

	return 0;
}

- 학생수 : 5명(1번, 2번, 3번, 4번, 5번)

- 여분가져온 착한 친구 : 3번

- 잃어버린 친구 : 2번, 4번

= 수업을 들을 수 있는 학생수 : 4명

4. 알게된 것

시간복잡도만 보고 알고리즘의 좋고, 나쁨을 판단할 수 없다는 것을 알게되었다.

만약 학생수가 10,000,000명이라고 생각하고 여벌을 가져온 학생이 2명이라고 생각해보자.

여기서 위 알고리즘으로 구현하면 10,000,000개의 공간이 필요로 하며, O(n)이지만 여러번의 연산을 필요로한다.

이럴경우 다음과 같이 사고 해 볼 수 있다.

1. 여벌의 체육복을 가져온 학생들의 번호를 정렬한다. > O(nlogn)

2. 잃어버린 학생에 대해 빌려줄 수 있는 학생을 찾아서 처리한다(lost를 해쉬화) > O(1)

 

위의 알고리즘은 O(nlogn)이기 때문에 알고리즘만 보면 O(n)보다는 비효율적으로 보일 수 있으나,

학생수가 매우 많고, 여벌을 챙겨온 학생 수가 이에 비해 매우 적으면 오히려 아래와 같은 방식이

더 나은 알고리즘이 될 수 있다.

 

이와 같이 시간복잡도만 보고 모든 것을 판단할 수 없다는 것을 알게 되었다.

---

다음엔 체육복 가져간 도둑부터 잡는 걸로 하자.