백준 1946번 : 신입사원
https://www.acmicpc.net/problem/1946

1. 문제 이해

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

문제에서 볼드 처리한 두 부분에서 문제 해결 방식을 도출할 수 있다.
1) 1차 시험 등수, 2차 시험 등수가 있다.
2) 1차 시험 등수, 2차 시험 등수가 나보다 높은 지원자가 한 명이라도 있으면 안된다.
즉, 특정 지원자보다 두 시험 등수가 모두 높은 지원자가 있는지만 확인하면 되기 때문에 '그리디 알고리즘'을 떠올릴 수 있다.

2. 문제 풀이

2-1. 첫번째 풀이(시간초과)

from sys import stdin
input = stdin.readline

if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        N = int(input())
        rank = [tuple(map(int, input().split())) for _ in range(N)]
        rank.sort(key=lambda x : x[0])
        rmv = []
        
        for i in range(N):
            top = rank[i][1]        
            for r in range(i+1,N):
                if rank[r][1] > top :
                    rmv.append(rank[r])             
        a = N - len(set(rmv))
        print(a)        

• 아이디어
  1 - 1차 시험 등수 기준 오름차순 정렬을 한다.
  2 - 특정 지원자보다 앞 지원자는 1차 시험 등수가 무조건 높은 상황이다. 따라서 2차 시험 등수까지 앞 지원자보다 낮으면 탈락한다. 즉, 2차 시험 등수만 앞 지원자보다 높은지 확인하면 된다.
  3 - 모든 지원자와 비교해야하기 때문에 for문을 돌려 모든 지원자와 비교할 수 있도록 한다.
  4 - 기준에 부합하지 않은 지원자는 rmv 리스트에 넣었다가, 마지막에 set으로 중복 제거한 후 전체 지원자에서 rmv 리스트의 길이를 뺀 값을 프린트한다.

• 새로 알게 된 것
  1 - rmv 리스트의 값을 set으로 중복제거할 때, list형을 담고 있는 list는 set적용이 안된다. 따라서 rank에 입력값을 받아줄 때 tuple로 받아야만 set으로 중복제거가 가능하다.

2-2. 두번째 풀이(정답)

from sys import stdin
input = stdin.readline

if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        N = int(input())
        rank = [tuple(map(int, input().split())) for _ in range(N)]
        rank.sort(key=lambda x : x[0])
        top = rank[0][1] 
        count = 1
        
        for r in range(1,N):
            if rank[r][1] < top :
                count += 1
                top = rank[r][1]
                
        print(count)     

• 새로 알게 된 것
  1 - 앞서 시간초과가 난 코드는 이중 for문을 사용했다. 현재 코드는 for문을 하나만 쓰고, top의 등수를 그 때 그 때 업데이트해주는 방식을 사용했다. 이렇게 코드 짜는 방식을 계속 익혀야겠다고 생각했다.

3. 정리

3-1. set과 tuple과의 관계

: list(mutable) vs tuple(immutable)이다. 이번 문제처럼 값 두개를 같이 가지고 다녀야 할 경우 그리고 그것을 set을 통해 중복제거할 필요가 있는 경우, tuple을 써야한다.
경험상 이런 상황에서는 둘 중 재지말고 tuple로 바로 가도 무방할 듯 하다.

3-2. 이중 for문 되도록 쓰지 않고 구현할 수 있는 센스를 기르자!