[학교 과제] 인기 검색어 (c++)

문제

입력으로 첫 째줄에는 입력 단어의 수 N(5 <= N <= 1,000,000)이 주어지고 한 줄씩 단어가 주어진다.

이 단어를 읽고 [N/2] + 1 회 이상 나타나는 단어를 인기 검색어라 한다 인기 검색어를 있으면 출력하고 

없으면 NONE을 출력한다.

풀이 방법

입력 N이 주어졌을 때 과반수를 찾는 문제이다 

 

첫 번째 방법

시간 복잡도 O(N^2) 의 풀이 방법으로 배열을 이중 for 문을 돌며 각각의 단어 갯수를 세어서 가장 큰 단어를

찾아 과반이 넘는지 확인하는 방법이다

두 번째 방법

시간 복잡도 O(NlogN) 으로 단어를 입력 받고 단어를 사전순으로 정렬 한 후 단어를 순회하며 i 와 i+1이 같으면 

count = count + 1 다르면 count = 0 으로 하며 count 가 과반의 수가 넘어가면 for 문을 종료하며 return 하고 for 문을 다 돌았음에도 없으면 NONE을 리턴한다.

단어를 정렬 했기 때문에 같은 단어라면 인접해새 단어가 나온다는점을 이용하여 풀이하는 방법이다.

정렬 하는 과정 떄문에 O(NlogN)이 걸린다

세 번째 방법

시간 복잡도 O(N)으로 스택을 이용하여 푸는 방법이다.

이 알고리즘의 원리는 과반이 넘기 때문에 과반이 넘는 각 단어가 각각 하나의 다른 단어 씩과 짝지어 져서 제거 된다 하더라도 과반이 넘기 때문에 마지막에 과반이 넘는 단어가 남는 다는 점을 이용한다.

stack을 이용하여 top과 다음 단어가 다르면 pop, 같으면 push, stack이 empty면 push를 하여 마지막 stack에 있는 단어를 과반이라고 출력한다 여기서 stack 이 empty면 NONE을 출력 한다.

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main(){
    int n;
    vector<string> words;
    stack<string> stack;   
    cin >> n;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        words.push_back(s);
        if( stack.empty() ) stack.push(s);
        else if( stack.top() != s ) stack.pop();
        else stack.push(s);
    }    
    if( stack.empty() ){
        cout << "NONE" << endl;
    }
    else{
        string s = stack.top();
        int count = 0;
        for(int i = 0; i < n; i++){
            if( words[i] == s ) count++;
        }
        if( count > n/2 ) cout << s << endl;
        else cout << "NONE" << endl;
    }    
}