[백 준 1946번] 파이썬 - 신입 사원

문제 참고 https://www.acmicpc.net/problem/1946

1946번: 신입 사원

 

문제 이해부터 조금 난해한 문제였다.. 결론은 서류 성적과 면접 성적 중 그 누구와 비교해도 두 성적 모두 낮지만 않으면 된다.

 

브루트포스와 같이 2중 for문을 통한다면 정말 쉽게 구할 수 있을 줄 알았다.

# 시간초과 1
    #입력받은 성적을 순회하며 두 성적 모두 떨어진다면 제외
    for j in range(len(grade)):
        for k in range(len(grade)):
        # 서류, 면접 성적 중 하나라도 성적이 높다면 다음 사람과 비교.
        # 탈락조건이 되면 다음 사람으로 이동
        # 숫자가 크면 성적이 낮다 - 등수를 일컫음
            if grade[j][0] == 1 or grade[j][1] == 1:
                pass_num.append(grade[j])
                break
            if grade[j][0] > grade[k][0] and grade[j][1] > grade[k][1]:
                break
                # 마지막 사람과 비교가 끝났다면 리스트에 추가
            elif k == len(grade)-1:
                pass_num.append(grade[j])

    print(len(pass_num))
    
    
    
    # 시간초과 2
    grade.sort()
    docu = []
    inter = []
    cnt = 1
    for i in range(len(grade)):
        docu.append(grade[i][0])
        inter.append(grade[i][1])

    for j in range(1,len(inter)):
        for k in range(j):
            if inter[j] > inter[k]:
                break
            if inter[j] < inter[k]:
                if k == j-1:
                    cnt+=1
                    break
    #print(inter)
    print(cnt)

역시나 그리디 문제는 앵간하면 2중 for문이 아닌 다른 접근방식을 찾아보는 것이 맞는 것 같다.

만약 코딩 테스트였다면 많은 시간을 허비했을 것이다!! 미련 같지말고 안 풀릴때는 다시 처음부터 생각해보는 습관을 들이자.

 

이 문제 또한 서류 성적에 대해 오름차순 정렬을 해주고 면접 성적에 대해서만 비교해주는 방법으로 다시 접근하였다.

하지만 함정은 단순히 서류 성적이 낮다고 면접 성적에 관해서만 비교를 해준다면 오류가 생길 수 있는 것을 볼 수있었다.

 

예를 들면 1-5, 2-2, 3-3의 성적을 받은 세 면접자를 보자.

서류성적 1등을 기준으로 면접 성적을 비교한다면 3번째 면접자의 경우 면접 성적이 1등 면접자보다 높기 때문에 면접 통과가 된다.

하지만 2등 참가자와 비교를 하니 서류 , 면접 성적 모두 낮아 탈락이였다.

이를 위해서 비교 기준을 계속 바꿔주었고 아래 코드를 이용해 통과하였다.

 

 

통과 코드

import sys
sys.stdin = open('input.txt')

# 1946 신입사원

# 1차 서류, 2차 면접 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발
# A의 서류심사, 면접심사 성적 모두 B에 비하여 떨어진다면 탈락
# 신입 사원의 최대 인원 출력


# 첫줄 테스트 케이스
T = int(input())

# 지원자의 숫자
for tc in range(T):
    N = int(input())
    # 서류 , 면접 순으로 입력받고 1위부터 N위까지 동석차 없이 결정
    # N명의 지원자 성적 기입
    pass_num = []
    grade = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    # 이중 for문 쓰니 시간초과
    # 전체를 순회하는게 아니라 정렬 후 자신보다 등수가 높은 사람과만 비교하면 된다.
    # sorted 함수를 이용하여 서류심사 오름차순
    grade.sort()
    # 서류심사 1등은 무조건 통과이므로 카운트 1로 시작하고 비교값으로 선언
    cnt = 1
    pass_standard = grade[0][1]
    for i in range(1, N):
        # for문을 돌면 이미 서류심사는 앞 사람에게 지므로 면접 등수가 높아야한다
        # 1등의 면접 등수보다 높은 사람이 나오면 다시 기준으로 정해준다
        # ex) 1,5  2,2 3,3 인 경우 2등의 면접순위= 2, 1등의 면접순위= 5 이므로 기준 2,2로 해준다.
        # 그러면 3등의 면접순위 = 3 이므로 1등보다는 잘한 것 같지만 2등의 등수에는 못미치므로 탈락이다.
        # 기준을 새로 세워주지 않는다면 1등보다 등수가 높다고 나오므로 2등과 비교하기위한 for문을 하나 더 써주어야한다.
        if grade[i][1] < pass_standard:
            pass_standard = grade[i][1]
            cnt+=1

    print(cnt)

 

항상 여러 방면으로 열어두고 코딩을 시작해야 될 것같다. 한 가지만 생각하고 밀어붙이다가 통과를 못했을 때는 이미 많은 시간이 지나가는 것같다. 조건의 수가 크지 않다면 브루트 포스가 가장 쉽게 코드를 짤 수 있었지만, 수가 커지니 죄다 시간 초과에 걸려버렸다.