5766 할아버지는 유명해!

간단한 구현문제

Direct Index Table과 두번째로 큰 값 찾기

1. 문제

---

간단 설명

문제가 번역체라 이해하는데 시간이 좀 걸렸다

매주마다 주어지는 랭킹정보를 보고, 2등 선수가 누구인지 찾는 문제

2. 문제 분석

---

필요변수

각 선수는 1~10000까지의 정수(선수 번호)로 식별. player[10001] 배열에 저장

몇주차 정보가 주어지는지 저장할 N

주차별 랭킹에 든 선수가 몇명인지 저장할 M

그 외에도 1등, 2등을 판별할 변수들과

2등이 여러명일 경우 이를 오름차순으로 정렬할 벡터 res 등

주의점

• 매주 랭킹에 선수의 이름이 오를 때마다 선수의 포인트가 1포인트씩 오른다고함

  주어지는 숫자자의 순서는 순위가 아니라 다같이 1점씩 받는것

• 각 테스트케이스별로 리더보드가 초기화 된다

• 2등을 구하는 방법에 주의

• 입력값이 많으니 cin, cout 사용시 주의할 것

알고리즘

1. 테스트케이스를 입력받는다. 
2. N과 M이 0이라면 종료한다
    - 아니라면, 스코어보드를 초기화한다
3. N주차 스코어 정보를 입력받는다
    3-1. M개의 선수들의 정보를 입력받는다.
    - 선수 번호가 나온다면, 그 선수의 인덱스에 +1 을 해준다
4. 2등의 점수를 구한다
    4-1. 현재 1등 점수보다 크다면, 1등 점수에 현재 점수를 넣고, 들고있던 점수를 2등에게 넘겨준다
    4-2. 1등보다는 작지만, 2등보다는 크다면, 2등 점수를 갱신한다
5. 2등의 점수와 같은 선수들을 res 벡터에 넣는다
6. res 벡터를 출력한다

3. 소스코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

#define MAX 10001

int player[MAX] = { 0 };

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	int N, M;

	while (1) {
		scanf("%d %d", &N, &M);
		if (N == 0 && M == 0) break;
		memset(player, 0, sizeof(player));
	
		for (int i = 0; i < N; i++) {
			// 1. N주차 스코어 정보 입력받기
			for (int j = 0; j < M; j++) {
				int tmp = 0;
				scanf("%d", &tmp);
				player[tmp] += 1;
			}

		}	

		// 2. 2등 구하기
		int first = 0, second = 0;
		for (int i = 0; i < MAX; i++) {
			// 현재 1등보다 큰값이 나오면 1등값을 2등에게 주고, 1등값을 받아옴
			if (first < player[i]) {
				second = first;
				first = player[i];
			}
			// 1등보다는 작은데, 1등과 같지 않고 2등보다 크다면 그 값을 2등에 넣는다
			else if (second < player[i] && player[i] != first) {
				second = player[i];
			}
		}

		// 2등 값과 같은 선소들을 찾아 벡터에 넣기

		vector<int> res;
		for (int i = 0; i < MAX; i++) {
			if (second == player[i]) {
				res.push_back(i);
			}
		}

		for (int e : res) {
			cout << e << " ";
		}
		cout << endl;
	}

	return 0;
}

두번째로 큰 값을 구하는 방법이 깔끔하지 못해서 찾아봤다

가장 큰 값을 배열에서 삭제하고 다시 순회하는 방법을 사용했는데, 개선한 방법이 더 깔끔한것 같다