[C++] 백준(BOJ) 5597 과제 안 내신 분..?

 

풀이1 (내풀이)

• 단순한 1차원배열로 풀었다.
• 배열을 0으로 초기화후, 제출한 경우 1로 바꾸고 미제출자의 경우 0이므로
• 0의 값을 가진 인덱스+1 (=미제출자의 출석번호) 을 출력하도록 하였다.

#include <iostream>
using namespace std;
/*
* absent[30] 배열을 0으로 초기화하고
* for문으로 28번
* 제출자의 출석번호를 받아 absent의 인덱스번호로 할당하여
* absent[i] = 1로 바꾼다.
* absent를 인덱스 오름차순으로 훑는데 1이면 출력한다.
*/
int main() {
	int absent[30] = { 0 };
	int k;
	
	for (int i = 0; i < 28; i++)
	{
		cin >> k;
		absent[k-1] = 1;
	}

	for (int i = 0; i < 30; i++)
		if (absent[i] == 0)
			cout << i+1 << endl;
	return 0;
}

 

시간복잡도:
학생수를 n이라 하면,
과제를 낸 학생수만큼 for문으로 absent배열의 값을 바꾸고 -> O(n-2) 
과제를 안낸 학생은 최악의 경우 n회 for문 내의 코드를 반복해야하므로, ->O(n)
따라서 O(n-2)+O(n) = O(n)

 

풀이2 (다른사람)

• 전체적인 풀이 접근은 풀이1과 같지만,
• 1차원배열의 크기를 31로 두어 인덱스와 출석번호의 차이 1을 고려하지 않아 더 좋다.
• if의 조건부에 1인 경우 맞다고 판단하므로 이를 이용해 조건부를 간단히 하였다.

#include <iostream>

using namespace std;

int main() {

  int arr[31] = { 0, };
  int a;

  for(int i = 0; i < 28; i++) {
    cin >> a;
    arr[a] = 1;
  }

  for(int i = 1; i <= 30; i++) {
    if(!arr[i]) cout << i << '\n';
  }

  return 0;
}

 

 

---