[C++] 백준 1270 - 땅따먹기

문제 - 땅따먹기 (Silver3)

[백준 1270] https://www.acmicpc.net/problem/1270

풀이 전략

• N만큼 반복하는 하나의 반복문 안에서 M을 입력받고 M만큼 숫자를 입력 받아서 Map에서 입력한 숫자와 동일한 index 위치의 값을 증가시킨다.
• M개의 숫자를 입력받은 뒤, maxFreq를 업데이트 해서 입력한 숫자가 제일 많은 수를 maxNum으로 지정한다.

참고

unordered_map

: map처럼 <key,value>로 값을 저장하지만, map과 달리 앞에 붙어있는 unordered의 의미처럼 정렬이 되지 않은 map이다. Hash 함수를 이용하여 탐색을 하기 때문에 정렬을 할 필요가 없기 때문이다.

#include <unordered_map>
unordered_map <string,int> map;
unordered_map <string, vector<string>> map;

[멤버 함수]

• map.at(idx) : idx번째 원소를 참조, 범위를 점검
• map[idx] : idx 원소를 참조, 범위를 점검하지 않음
• map.clear() : 모든 원소 제거
• map.insert(make_pair(key,value)) : key, value 삽입
• map.begin(), map.end() : 첫번째와 ,마지막원소 가리킴.
• map.find(key) : 특정 키를 가진 원소를 찾는다.
• map.count(key) : 특정 키를 가진 원소의 개수
• map.erase(key) : key의 원소를 제거

[단점]
하지만, 원소의 개수와 해시 충돌 가능성은 비례하기 때문에
1. 원소의 개수가 적고 빠른 성능을 원할 땐 unordered_map
2. 원소의 개수가 많아 안정성을 원할 땐 map
을 사용하면 된다.

map은 정렬되어 있는 상태에서 탐색을 수행하기 때문에 O(logN)의 시간이 걸리지만, unordered_map 같은 경우는 O(1)의 시간이 걸리기 때문에 해시 충돌만 없으면 상당히 효율적인 방법이라고 할 수 있다.

소스 코드

#include <iostream>
#include <unordered_map>
using namespace std;

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

    int N,M;
    cin>>N;

    unordered_map<long long,int> war;
    
    long long maxNum=-1,maxFreq=0;
    long long num;

    while(N--){
        cin>>M;
        
        for(int j=0;j<M;j++){
            cin>>num;
            war[num]++; // 입력한 숫자에 대응하는 index 위치값 증가
            // num이 key이고 war[num]이 value인 셈
            if(war[num]>maxFreq){
                maxFreq=war[num];
                maxNum=num;
            } // maxFreq와 maxNum 업데이트
        }

        int halfM=M/2;
        if(maxFreq>halfM){
            cout<<maxNum<<'\n';
        }else{
            cout<<"SYJKGW"<<'\n';
        }
        war.clear();
        maxFreq=0;
        maxNum=-1;
    }
    return 0;
}

결과

3번 틀린 이유는 첫번째는 maxFreq를 안하고 maxNum으로만 했다가 틀렸고, 두번째랑 세번째는 그놈의 long long 자료형으로 안하고 int형으로 했다가 틀렸다.
답이 맞게 출력되는데 틀린다? 그러면 long long이 문제다....