[baekjoon]python #1946 신입사원

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

#1946 신입사원

신입사원이 되고싶은 마음에 제목보고 푼 문제!

---

1946번: 신입 사원

 

 

🍕처음에 푼 푼 코드 -- 시간초과...

import sys
T = int(sys.stdin.readline())
for tc in range(T):
    N = int(sys.stdin.readline())
    arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
    arr.sort()


    fail = []
    def employment(interview,idx):
        global fail
        for j in range(idx,N):
            if arr[j][1]>interview:
                if arr[j][1] not in fail:
                    fail.append(arr[j][1])

    for i in range(N):
        employment(arr[i][1],i)

    print(N-len(fail))

---

import sys
T = int(sys.stdin.readline())
for tc in range(T):
    N = int(sys.stdin.readline())
    arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
    arr.sort()

    fail=set()
    def employment(interview,idx):
        global fail
        for j in range(idx,N):
            if arr[j][1]>interview:
                fail.add(arr[j][1])


    for i in range(N):
        employment(arr[i][1],i)
    print(N-len(fail))

🎈 arr배열을 sort해주면 1번 인덱스만 비교해서 탈락자들의 수를 구할 수 있다.

🎈 나는 함수를 만들어서 함수 인자로 interview 점수와 index를 넣어 다음 값을 비교해 interview보다 크다면 탈락이기 때문에 배열에 넣는 식으로 했다. 이렇게 하다보면 중복이 되는 경우가 생겨 set을 이용해 중복을 제거했다.

🎈 하지만 불필요한 중복 과정이 많고 결국 for문안에 2중 for문이 되어 시간복잡도 면에서 엄청나게 손해였다. 그래서 시간초과로 채점이 되지 않았다.

 

🍔통과한 코드

import sys
T = int(sys.stdin.readline())
for tc in range(T):
    N = int(sys.stdin.readline())
    arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
    #documnet전형을 기준으로 sort
    arr.sort()

    hire=1 #arr[0][1]은 확실한 합격자니까 
    		#( document전형에서 arr[0]보다 작은 수는 없기 때문)
    winner = arr[0][1] 
    for i in range(N):
    	#winner보다 작으면 합격자
        if arr[i][1]<winner:
            winner=arr[i][1]
            hire+=1
    print(hire)

🎈불필요한 코드를 제거하고 winner를 갱신해 arr[i][1]을 비교해주는 방법을 택했다.

🎈이중 for문을 사용하지 않기 때문에 시간복잡도면에서 훨씬 효율적이고 간결한 코드로 바뀌었다.

 

❕관련 ALGORITHM 이론

2022.05.13 - [Problem Solving/ALGORITHM] - 그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘(Greedy Algorithm)