[백준] 1946번 신입 사원(python)

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

1946번: 신입 사원

 

1. 내가 작성한 코드

t = int(input())

for i in range(t):
  n = int(input()) #지원자 수
  apply = [] #지원자의 점수
  cnt = 1 #서류 1등은 무조건 합격이니 1부터 시작
  for i in range(n):
    apply.append(list(map(int,input().split())))
  
  apply.sort() #서류 기준으로 정렬

  for i in range(1,n):
    verity = i
    for j in range(i):
      if apply[i][1] < apply[j][1]: #서류 등수가 본인보다 높은 사람들 보다 면접 등수가 높으면 합격
        continue
      else:
        verity -= 1
    if verity == i:
      cnt+=1

  print(cnt)

 

지원자 N의 범위가 100,000명까지라는 걸 보고 시간초과를 걱정해야겠다고 생각했으나, 역시나 시간초과로 실패했다.

 

사실 이 문제를 이해하는 것도 좀 시간이 걸렸는데, 이해를 돕기 위해 예시를 들자면

 

서류 점수로 정렬

 

1 4 => 합격

2 5 => 서류 1등보다 면접 등수가 낮으니 불합격

3 6 => 서류 2등보다 면접 등수가 낮으니 불합격

4 2 => => 앞에 있는 모든 사람보다 면접 등수가 높으니 합격

5 7 => 서류 5등보다 면접 등수가 낮으니 불합격

6 1 => 앞에 있는 모든 사람보다 면접 등수가 높으니 합격

7 3 => 서류 6등보다 면접 등수가 낮으니 불합격

 

으로 총 3명이 합격하게 되는 것이다.

 

즉, 서류 등수로 정렬을 시켰을 때, 본인의 앞에 있는 사람들 전체보다 면접 등수가 높아야지만 채용이 된다는 것

 

따라서 2중 for문을 통해 이를 검증했고, 앞서 말한 것과 같이 시간초과로 실패했다.

 

2. 수정한 코드

t = int(input())

for i in range(t):
  n = int(input()) #지원자 수
  apply = []
  top = 0
  cnt = 1
  for i in range(n):
    apply.append(list(map(int,input().split())))
  
  apply.sort()

  for i in range(1,n):
    if apply[i][1] < apply[top][1]:
      top = i
      cnt+=1

  print(cnt)

아까와 동일한 알고리즘이나, for문을 한 번만 돌렸고, top이라는 변수를 새로 만들었다.

 

다시 아까의 예를 가지고 오면

 

1 4 => 합격

2 5 => top : 0 => [0][1]인 4보다 면접 등수가 낮으니 불합격, top은 변하지 않음

3 6 => top : 0 => [0][1]인 4보다 면접 등수가 낮으니 불합격, top은 변하지 않음

4 2 => top : 3 => [0][1]인 4보다 면접 등수가 높으니 합격, top은 index 3으로 변경 (즉, value는 2)

5 7 => [0][3]인 4보다 면접 등수가 낮으니 불합격, top은 변하지 않음

6 1 => [0][3]인 2보다 면접 등수가 높으니 합격, top은 index 5 로 변경 (즉, value는 1)

7 3 =>  [0][5]인 1보다 면접 등수가 낮으니 불합격, top은 변하지 않음

 

이 방식이 성립하는 이유는 

 

top의 값보다 면접 등수가 높다는 것은, 앞에 있는 사람들 모두보다 면접 등수가 높다는 것과 같기 때문이다(=최적의 해).

 

그리디 문제인 만큼 너무나 Greedy한 풀이 ㅠ_ㅠ

 

시간복잡도를 줄이는 방법을 많이 고민해봐야겠다.