[백준] 1946 신입 사원 (실버1)

문제요약

나의 코드 및 설명 01 - 이중 for문으로 한 명의 성적을 나머지의 성적과 비교 (시간초과)

import sys

t = int(input())
for test_case in range(1,t+1):
    n = int(input())
    result = []
    for _ in range(n):
        result.append(list(map(int, sys.stdin.readline().split())))

    cnt = 0
    for i in range(n): #한 명의 서류, 면접 성적을 뽑는다.
        check = True 
        for j in range(n): #나머지와 서류, 면접 성적을 비교한다.
            if j == i: #만약 비교 대상이 본인이라면
                continue #다음 사람과 비교
            #만약 나머지의 성적과 비교했을 때, 한 번이라도 서류와 면접 순위 둘 다 뒤에 있다면
            if result[i][0] > result[j][0] and result[i][1] > result[j][1]:
                check = False #check 변수에 False 저장하고 반복문을 탈출한다.
                break
        if check: #끝까지 반복이 진행되었다면, 합격이므로
            cnt += 1 #합격자를 카운트한다.

    print(cnt)

나의 코드 및 설명 02 - 정렬 : 서류 성적 오름차순으로 정렬 후 면접 성적 살펴봄 (틀림)

import sys

t = int(input())
for test_case in range(1,t+1):
    n = int(input())
    result = []
    for _ in range(n):
        result.append(list(map(int, sys.stdin.readline().split())))
    result.sort(key = lambda x:x[0])

    bool_cnt = 0
    for i in range(n-1, 0,-1): 
        #조건을 잘못 써서 틀렸다. 이전 사람과만 비교했기 때문에 정확한 답이 아니다.
        if result[i][1] > result[i-1][1]:
            bool_cnt += 1
    print(n - bool_cnt)

나의 코드 및 설명 03 - 정렬 : 탈락하는 조건을 달리하여 문제해결 (맞음)

• 이미 서류 성적은 오름차순 정렬되어 있으므로, 면접 성적만 확인하면 된다.
• 만약 면접 성적이 이전 사람보다 후순위라면(크다면), 불합격이다.
• 만약 면접 성적이 이전 사람보다 전순위라면(작다면), 합격이다. 
• 그리고, 주의할 점은 다음 사람의 면접 성적을 이전 사람과 비교할 때, 합격한 사람 기준으로 면접 성적을 비교해야 하므로(왜냐면 이미 불합격한 사람은 면접 성적을 비교할 필요가 없다.) check 변수에 합격한 사람의 면접 성적을 갱신하여 저장한다.

import sys

t = int(input())
for test_case in range(1,t+1):
    n = int(input())
    result = []
    for _ in range(n):
        result.append(list(map(int, sys.stdin.readline().split())))
    result.sort(key = lambda x:x[0]) #서류 성적 오름차순으로 정렬

    bool_cnt = 0 #불합격 사람 수 카운트
    check = result[0][1] 
    for i in range(1, n):
        if result[i][1] > check:
            bool_cnt += 1
        else:
            check = result[i][1]
    print(n - bool_cnt)

피드백

여러 번의 제출 끝에 정답 판정을 받을 수 있었다. 처음에 이중 for문으로 각 사람의 성적을 다른 사람과 비교하여 소스 코드를 작성했는데, 시간초과가 발생했다. 고민하다가 서류 성적을 오름차순 정렬로 고정해보고 풀면 for문을 한 번만 사용할 수 있을 것 같았고, 다행히도 맞는 풀이 방법이었다. 처음 문제를 보았을 때 이해하기 쉽지 않았었는데 그래도 잘 이해하고 문제를 해결한 것 같아서 기분이 좋다.