백준 10570번 [Favorite Number](C++) -yes6686- 티스토리

백준 문제 풀이: 10570

---

문제 링크: https://www.acmicpc.net/problem/10570

문제 설명:

주어진 숫자들 중 가장 많이 등장한 숫자를 구하는 문제입니다. 만약 여러 개의 숫자가 같은 최빈도를 가지면, 그 중 가장 작은 값을 출력해야 합니다.

---

문제 해결 코드

// Favorite Number 문제의 최적화된 코드
#include <iostream>
#include <cstring> // memset 사용을 위한 헤더
using namespace std;

int arr[1001]; // 1부터 1000까지의 숫자 빈도를 저장

int main() {
    ios::sync_with_stdio(false); // 입출력 속도 향상
    cin.tie(NULL); // cin과 cout의 동기화를 끊음

    int n; // 테스트 케이스 개수
    cin >> n;

    while (n--) {
        int v; // 숫자의 개수
        cin >> v;

        int maxCount = 0; // 최빈도의 값
        int result = 1001; // 조건에 맞는 숫자 (초기값은 범위 밖의 큰 수)
        memset(arr, 0, sizeof(arr)); // 배열 초기화

        for (int i = 0; i < v; i++) {
            int num;
            cin >> num;
            arr[num]++;

            // 최빈도 업데이트 조건
            if (arr[num] > maxCount || (arr[num] == maxCount && num < result)) {
                maxCount = arr[num];
                result = num;
            }
        }
        cout << result << '\n'; // 결과 출력
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 배열을 사용해 숫자별 등장 횟수를 카운팅하고, 최빈도 숫자를 실시간으로 업데이트하는 방식입니다. 등장 횟수와 숫자값 조건을 동시에 비교합니다.
• 구현 세부사항:
• memset(arr, 0, sizeof(arr)): 테스트 케이스마다 배열을 초기화해 숫자 등장 횟수를 리셋합니다.
• if (arr[num] > maxCount || (arr[num] == maxCount && num < result)): 조건문으로 최빈도 업데이트를 수행합니다.
• 숫자가 같을 경우, 더 작은 값을 선택하도록 num < result를 사용했습니다.
• 시간 복잡도 분석:
• 각 테스트 케이스에서 최대 1000개의 숫자를 처리하므로, 단일 테스트 케이스의 복잡도는 O(v)입니다.
• 전체 복잡도는 O(n * v)입니다. (n: 테스트 케이스 개수, v: 입력 숫자 개수)

---

결과

최적화된 코드로 실행 시 높은 효율성을 보여줍니다. 배열 초기화와 조건문 최적화를 통해 불필요한 연산을 줄였습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!