[Python] BOJ 1946 : 신입 사원

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

요구사항

1. 시간 제한 2초
   1. N <= 100,000 이니 O(N**2) 미만
2. 메모리 제한 256MB
   1. 100,000 * 4 = 40MB / 리스트당 
3. 다른 모든 지원자와 비교했을 때, 서류 심사 성적과 면접 시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않으면 합격.

설계 1

1. 회의실 배정처럼 정렬하였지만 실패

구현 1

import sys
input = lambda: sys.stdin.readline().rstrip()

test_case = int(input())

def employment(candidate):
    maginot_line = 0
    successful_candidate = 0

    candidate = sorted(candidate, key=lambda x: (x[1], x[0]))
    for document_score, interview_score in candidate:
        if document_score > maginot_line:
            maginot_line = interview_score
            successful_candidate += 1
    return successful_candidate


for _ in range(test_case):
    total_candidate = int(input())
    for _ in range(total_candidate):
        candidate_list = [list(map(int, input().split()))] 
    print(employment(candidate_list))

실수 1 : [지원자 정보를 입력 받는 부분의 오류]

• for _ in ragne(total_candidate): 각 지원자의 정보를 리스트에 잘못 추가하고 있다.
• 아래 소스 코드처럼 바꾸어 해결

for _ in range(test_case):
    total_candidate = int(input())
    candidate_list = []
    for _ in range(total_candidate):
        candidate_list.append(list(map(int, input().split())))
    print(employment(candidate_list))

실수 2 : [비교 기준 오류]

• 현재는 면접 점수를 기준으로 정렬한 뒤 면접 점수가 같으면 서류 점수를 기준으로 정렬하고 있다.
• 따라서 서류 점수가 뒤에 오는 서류 점수보다 크면 합격할 수 있도록 해줘야 한다. 

def employment(candidate):
    maginot_line = 0
    successful_candidate = 0

    candidate = sorted(candidate, key=lambda x: (x[1], x[0]))
    for document_score, interview_score in candidate:
        if document_score > maginot_line:
            maginot_line = interview_score
            successful_candidate += 1
    return successful_candidate

• 위 소스 코드에서 n가지를 바꿔야 한다.
• maginot_line 를 매우 큰 수로 만든다. 
  • maginot_line = sys.maxsize or float('inf')
• if document_score > maginot_line 의 부호를 바꿔야 한다. < 로 
• maginot_line = document_score 로 바꾼다.

구현 2

import sys
input = lambda: sys.stdin.readline().rstrip()

test_case = int(input())

def employment(candidate):
    maginot_line = sys.maxsize
    successful_candidate = 0

    candidate = sorted(candidate, key=lambda x: (x[1], x[0]))
    for document_score, interview_score in candidate:
        if document_score < maginot_line:
            maginot_line = document_score
            successful_candidate += 1
    return successful_candidate


for _ in range(test_case):
    total_candidate = int(input())
    candidate_list = []
    for _ in range(total_candidate):
        candidate_list.append(list(map(int, input().split())))
    print(employment(candidate_list))

구현 2 리팩토링

• 첫 번째 for문에서 interview_score 사용되지 않고 있다. 
• 두 번째 for문은 리스트컨프리헨션으로 간략하게 표현 가능하다.
• 또한, 현재는 list 로 받고 있지만, tuple로 받을 수 있다.
  • 불변성 : 한 번 생성된 튜플은 값을 변경할 수 없다.
  • 메모리 효율성 : 튜플은 리스트보다 메모리를덜 사용한다.
• 정렬 하는 부분에서 복잡하게 하지말고, 특정 점수를 기준으로 오름차순 정렬을 한 뒤, 다른 점수와 비교해서 작으면 되기 때문에 정렬 로직을 간단하게 바꿔줄 수 있다. 
• 두 번째 for문 또한 main 함수에 넣어 돌려줄 수 있다. 

import sys
input = sys.stdin.readline

def count_successful_candidates(candidates):
    candidates.sort()  # 서류 점수 기준으로 정렬
    max_interview_score = float('inf')
    successful_count = 0

    for _, interview_score in candidates:
        if interview_score < max_interview_score:
            max_interview_score = interview_score
            successful_count += 1

    return successful_count

def main():
    test_case = int(input())

    for _ in range(test_case):
        num_candidates = int(input())
        candidates = [tuple(map(int, input().split())) for _ in range(num_candidates)]
        print(count_successful_candidates(candidates))

if __name__ == "__main__":
    main()

• 아래 사진을 보면 리팩토링한 결과 시간,공간 복잡도 측면에서 성능이 향상된 것을 볼 수 있다.