[삼성 SDS 알고리즘] 가장 많은 수

[삼성 SDS 알고리즘] 가장 많은 수

문제 출처 : https://koitp.org/problem/SDS_PRO_2_4/read/

문제

$N$개의 정수가 주어진다. 이 중 가장 많이 등장하는 수를 구하시오. 만약 이런 수가 여러 개라면 작은 수를 출력하세요.

입력

첫 번째 줄에는 정수의 개수 $N$이 주어진다. $(1\le N\le 1000000)$

두 번째 줄부터 N개의 줄에 걸쳐 각 줄에 하나의 정수가 주어진다. 이 수의 절대값은 $2^{31}-1$ 이하이다.

출력

가장 많이 등장하는 정수를 출력하시오.

힌트

예제 입력

4
1
2
3
3

예제 출력

3

문제 풀이

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int N;
    cin >> N;
 
    vector<int> a(N);
    vector<int> b(N);
 
    for (int i = 0; i < N; i++){
        cin >> a[i];
        b[i] = a[i];
    }
 
    int max, maxNum = 0;
 
    for (int i = 0; i < N; i++) {
        int count = 0;
        if (i == 0)
            max = 0;
        
        for (int j = 0; j < N; j++) {
            if (a[i] == b[j])
                count += 1;
        }
 
        if (count >= max) {
 
            if (count == max) {
                if (maxNum <= a[i])
                    maxNum = maxNum;
                else
                    maxNum = a[i];
            }
 
            else{
                max = count;
                maxNum = a[i];
            }
        }
    }
 
    cout << maxNum << endl;
 
 
}

채점해보니 몇 개를 제외한 대부분의 테스트케이스를 시간초과 문제로 통과하지 못했다ㅠ

아마도 이중 for문을 사용하면서 시간복잡도가 증가해서 그런 것 같다... 다시 생각해보고 풀어보기