[코딩테스트 C++] 신입사원

오늘의 문제

https://www.acmicpc.net/problem/1946

신입사원

• 문제분석
  입력 최대가 100000 => O(Nlog(N))인 알고리즘을 설계하면 됨
  정렬에 사용되는 시간복잡도 O(log(N))
  순차탐색 최대 O(N)

나의 풀이

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MAX = 100000;
pair<int, int> e[MAX];
int n;

// 신입사원
int solution(){
    int answer = 1;
    sort(e, e+n);
    int mini = e[0].second;
    for(int i=1;i<n;i++){
        if(e[i].second < mini){
            answer++;
            mini = e[i].second;
        }
        if(mini == 1)
            return answer;
    }
    
    return answer;
}

풀이 법

• 로직이 정확한데 왜 시간초과 나지!!! 하고 한참을 고민했다. Vector에 입력받아 solution에 보내는 과정이 시간이 오래 걸렸나보다.. 결국은 입출력에서의 시간때문에 틀렸던것. 백준으로 앞으로 계속 풀것이니 잘 생각해서 써야겠다.
• 서류순이든 면접순이든 오름차순으로 정렬한 후, 정렬한 분야의 1등의 다른 점수보다 작으면 answer을 올린다. 그리고 새롭게 갱신한다.

다른 답안

#include<iostream>
#include<cstdio>

using namespace std;

int T;
int N;
int v[100001];
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> T;

	for (int t = 0; t < T; t++)
	{
		cin >> N;
		for (int n = 0; n < N; n++)
		{
			int n1, n2;
			cin >> n1 >> n2;
			v[n1] = n2;
		}

		int tmp = v[1];
		int cnt = 1;
		for (int n = 2; n <= N; n++)
		{
			if (tmp >= v[n])
			{
				tmp = v[n];
				cnt++;
			}
		}

		cout << cnt << "\n";

	}

	return 0;

}

배울 점

• cin.tie(0); 은 실행속도를 높인다고 한다. 꼭 쓰자(test해보니 별 차이는 없는듯 하지만)