[BOJ] 1946번 - 신입 사원

문제 링크

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

문제 유형

그래프 탐색 - 그리디, DFS/BFS

🌈문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.
그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

1. 첫 시도 + 아이디어
인덱스를 사람을 구별할 수 있는 장치로 두고, 인덱스에 대한 순위인 int값을 정렬하여 각 리스트를 슬라이싱하여 비교하려고 하였다. 그리고 자신보다 우선순위에 있는 인덱스에 있는 값과 뒤쳐진다면 모두 정답에서 제외하려고 하였다.

2. 코드

T = int(input())
for _ in range(T):
    answer = 2
    dica = {}
    dicb = {}
    answer_list = []
    N=int(input())
    for i in range(N):
        a,b = map(int, input().split())
        dica[i] = a
        dicb[i]= (b)

    lista = sorted(dica, key = lambda x : dica[x])
    listb = sorted(dica, key=lambda x: dicb[x]) #사람의 순위 리스트

    answer_list.append(lista[0])
    answer_list.append(listb[0])
    for i in range(1, N):
        if lista[i] in answer_list:
            continue
        listc = []
        me = lista[i]
        num = listb.index(me)

        listc = listb[num:]
        for j in range(0, i):
            if lista[j] in listc:
                    answer = answer + 1
                    answer_list.append(me)
                    break

    for i in range(1, N):
        if listb[i] in answer_list:
            continue
        listc = []
        me = listb[i]
        num = lista.index(me)
        listc = lista[num:]
        for j in range(0, i):
            if listb[j] in listc:
                answer = answer + 1
                answer_list.append(me)
                break
    for j in range(0,len(answer_list)):
        num1 = lista.index(answer_list[j])
        num2 = listb.index(answer_list[j])
        for i in range(1,N):
            num3 = listb.index(lista[i])
            if i < num1 and num3 < num2:
                answer = answer -1

    print(answer)

나는 딕셔너리를 이용하여 순위 인덱스가 같이 정렬될 수 있게끔 하였고, 그 순위에 따라서 리스트 슬라이싱이 일어나게 하였다. 정말 시간이 무지막지하게 많이 걸린다.

개선점
나는 서류 순위와 면접 순위를 모두 오름차순으로 정렬해서 헷갈렸다.nlogn안에 시간 복잡도가 나와야 한다. 먼저 기본 아이디어는 다음과 같다.
첫번째 서류심사를 성적순으로 정렬하고, 두 번째 점수인 면접을 비교하여 합격자를 결정한다
1. A라는 학생이 서류, 심사 모두 어떤 사람보다 낮으면 안된다.
-> 즉, A보다 서류 심사 성적이 높은 학생들보다, A가 면접 성적이 높아야 한다. 이 조건만 가지고 문제를 풀어보겠다는 생각을 가지면 된다.

T=int(input())
for i in range(T):
    N=int(input())
    people = []
    for j in range(N):
        people.append(list(map(int,input().split())))

    people.sort()
    people_list = people_list[0][1]
    cnt = 1 #서류 1등은 무조건 합격! 

    for j in range(len(people_list)):
        if temp > people_list[j][1]: #면접 점수가 temp가 더 높아야.
            cnt += 1
            temp = people_list[j][1] #1등으로 등록

    print(cnt)

문제를 간단하게 해결할 수 있는 방법을 항상 고민해보자.