백준 20937번 [떡국](C++) -yes6686- 티스토리

백준 문제 풀이: 20937 떡국

---

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

문제 설명:

n개의 떡국 그릇에 번호가 매겨져 있습니다. 각 떡국 그릇에는 어떤 수가 적혀 있으며, 같은 수가 적힌 떡국 그릇이 있을 수 있습니다. 이 때, 가장 많은 떡국 그릇에 적힌 숫자가 몇 개인지를 출력하는 문제입니다.

---

문제 해결 코드

// 20937 떡국 - 최적화된 코드
#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 떡국 그릇의 개수
    cin >> n;

    unordered_map<int, int> cnt; // 숫자별 개수 저장
    int ans = 0; // 가장 많은 떡국 그릇의 개수

    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        cnt[num]++;
        ans = max(ans, cnt[num]); // 최대값 갱신
    }

    cout << ans << '\n'; // 결과 출력
    return 0;
}

---

코드 설명

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

• 핵심 알고리즘: 입력받은 숫자를 해시 맵(unordered_map)에 저장하여, 해당 숫자가 등장한 횟수를 카운트합니다. 이후 등장 횟수의 최댓값을 계산합니다.
• 구현 세부사항:
  • unordered_map를 사용해 특정 숫자의 등장 횟수를 저장합니다.
  • 각 입력마다 현재 숫자의 등장 횟수를 cnt[num]에 증가시키고, 동시에 ans를 갱신합니다.
• 시간 복잡도 분석:
  • 입력이 최대 n번 반복되고, unordered_map의 평균 접근 시간은 O(1)이므로 전체 시간 복잡도는 O(n)입니다.
  • 효율적인 자료 구조를 사용해 메모리와 시간 모두 최적화했습니다.

---

결과

입력된 떡국 그릇 번호의 개수를 바탕으로 가장 많이 등장한 숫자의 개수를 효율적으로 구할 수 있습니다.

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