[1946번] 백준 신입사원 문제 파이썬 풀이 시간초과이슈..

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

1946번: 신입 사원

오늘도 문제하나를 풀어보았다.

그리디문제지만 정렬이 이문제의 키라고 생각한다.

 

입력개수가 최대 10만개에 시간제한이 2초이내이니 시간복잡도는 nlog(n)이하로 짜야 통과할 수 있다.

 

처음 제출한 답안은 시간복잡도가 n^2이라 시간초과가 떴다(2중for문 쓰면안되는거알지만 그냥 일단 최대한 최적화생각해가면서 풀면 통과뜰수도 있을거란생각이었으나 어림도없었다)

아래는 시간초과한 코드

import sys
num=int(input())
while(num>0):
    n=int(input())
    rate=[]
    for i in range(n):
        temp=list(map(int,sys.stdin.readline().split()))
        rate.append(temp)
    
    rate.sort(key = lambda x:x[1])
    rate.sort(key = lambda x:x[0])
    
    staff=0
    Pass=False
    
    
    for i in range(len(rate)):   
            ########  자기자신과 비교 할 필요가 없다 ########
        for j in range(len(rate)):
            if j == i:
                continue
            
            ########## 1등인게 하나라도있다면 합격자다 ###########
            elif rate[i][0]==1:
                Pass=True
                break
            
            ######### 탈락자 조건체크, 해당시 Pass는 False이며 for문 탈출 ########
            if rate[i][0]>rate[j][0]:
                if rate[i][1]>rate[j][1]:
                    Pass=False
                    break
                
            ######## 루프를 끝까지 돌았는데 break가 안되었다면 합격이니 Pass는 True #####
            if j == len(rate)-1: 
                Pass=True
        
        ###### 참가자 합불 판단 ########        
        if Pass == True:
            staff+=1        
    print(staff)
    num-=1

 

 

위에서 말했지만 핵심은 정렬이었다. 정렬후 문제를 읽고 곰곰이 생각해서 답을 찾아야하는 문제다.

코테문제는 가끔 국어문제같기도하다..

 

아래는 맞은 코드입니다

import sys
num=int(input())
while(num>0):
    n=int(input())
    rate=[]
    for i in range(n):
        temp=list(map(int,sys.stdin.readline().split()))
        rate.append(temp)
    
    rate.sort()
    
    staff=1
    
    cmp=rate[0][1]
    for i in range(1,len(rate)):
        if cmp>rate[i][1]: 
            staff+=1
            cmp=rate[i][1]            
        
 
    print(staff)
    num-=1

 

◆  문제를 풀고나서....

• 언제나 느끼는거지만 문제를 정확히 읽고 이해하는게 중요하다. (문제도 오해의소지없이 최대한 친절했으면한다..)
• Sort의 중요성을 다시한번 느낀 문제였다. 소팅은 이 문제뿐만이아니고 연산속도와 최적화에 밀접한 관련이 있다라는걸느낌

 

※ 문제 풀이시 정답이더라도 파이썬으로 제출할땐, 입력수가 많은 경우 sys의 sys.stdin.readline()을 input()대신 사용해야 시간초과가 나지않습니다.