Greedy(9)_신입사원(1946)

작성일 | In

BJO 1946 신입사원

기업에서 채용을 함. 1차와 2차 총 두번의 시험을 걸치며 지원자 A와 B를 비교했을 때, 1차와 2차 성적 중 적어도 하나다 다른 지원자보다 떨어지지 않는 다만 선발한다는 원칙. 즉 A의 성적이 다른 어떤 지원자의 B성적에 비해 모두 떨어진다면 결코 선발 x

이러한 조건을 만족시키면서, 이번 채용에 선발할 수 있는 최대 인원수를 구하는 프로그램 작성

첫째 줄 테스트케이스 수 그 다음 줄, 지원자의 숫자가 N이 주어진다. 둘째 줄부터 N객의 줄에 지원자의 서류심사 성적 면접 성적의 순위가 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정.

아이디어

  1. [회의실_배정]https://scarletbreeze.github.io/articles/2019-07/Greedy(3)1931 문제처럼, 튜플을 넣은 다음, 정렬을 2번해서 사용할 순 없을까? 그럼 그저 1차 성적 정렬, 2차 성적 정렬 밖에 되지 않는다.

  2. for문을 돌면서 튜플 값을 비교하도록 해보자.

코드

import sys
T = int(sys.stdin.readline())
for i in range(T):
    N = int(sys.stdin.readline())
    # 리스트에 튜플 담기
    arr = []
    for i in range(N):
        a, b = map(int, sys.stdin.readline().split())
        arr.append((a, b))
    # 튜플 하나씩 꺼내서 비교
    cnt = 0
    for i in range(N):
        for j in range(N):
            if(arr[i][0] > arr[j][0] and arr[i][1] > arr[j][1]):
                cnt += 1
                break
    print(N-cnt)

  1. 시간초과가 떴다. 입력값을 보니 시간 제한이 2초다. 질문들을 몇개 찾아보니 NlogN의 정렬 알고리즘을 사용하여야 한다고 한다. for문이 두개면 안되나 보다.

  2. 다시금 1번의 풀이방법으로 돌아가자.

    서류심사성적으로 오름차순으로 정렬한 뒤, 면접 결과를 보고 카운트해서 판단하면 for문을 한번만 써도 된다. 지금은 바로 옆에 껏만 비교하고 있는데, 사실

import sys
T = int(sys.stdin.readline())
for i in range(T):
    N = int(sys.stdin.readline())
    # 리스트에 튜플 담기
    arr = []
    for i in range(N):
        a, b = map(int, sys.stdin.readline().split())
        arr.append((a, b))

    # arr.sort() 해도 첫번째로 정렬된다.
    arr = sorted(arr, key=lambda num: num[0])

    cnt = N
    for i in range(1, N):
        if(arr[i-1][1] < arr[i][1]):
            cnt -= 1
    print(cnt)

답이 틀렸다고 나온다. ㅠㅠ 결국 다른 분들의 풀이를 볼 수 밖에 없었다. 1차 성적으로 지원자들을 정렬한 뒤 지원자들의 2차 성적들 중 가장 최고 순위와 비교하여 그 순위보다 낮으면 채용한다. 즉 옆하고 비교하는게 아니라 최고순위와 비교해야한다.

1 4 <- 다음에 올 사람은 면접성적이 4위보다 좋아야 함 (count : 1)
2 5 <- Pass
3 6 <- Pass
4 2 <- 다음에 올 사람은 면접성적이 2위보다 좋아야 함 (count : 2)
5 7 <- Pass
6 1 <- 다음에 올 사람은 면접성적이 1위보다 좋아야 함 / 불가능 (count : 3)
7 3 <- Break

답안

import sys
T = int(sys.stdin.readline())
for i in range(T):
    N = int(sys.stdin.readline())
    # 리스트에 튜플 담기
    arr = []
    for i in range(N):
        a, b = map(int, sys.stdin.readline().split())
        arr.append((a, b))

    # arr.sort() 해도 첫번째로 정렬된다.
    arr = sorted(arr, key=lambda num: num[0])

    ans = 1
    temp = arr[0][1]
    interviewRank = arr[0]
    for i in range(1, N):
        if(arr[i][1] < temp):
            ans += 1
            temp = arr[i][1]
            if(temp == 1):
                break

    print(ans)

알게 된 사실

  1. enumerate : 반복문 사용시 몇 번쨰 반복문인지 확인이 필요할 수 있 다. 이 때 사용하며, 인덱스 번호와 컬렉션의 원소를 tuple의 형태로 반환한다.

참고자료 [예시답안]https://daimhada.tistory.com/39?category=810236 [enumerate]https://wikidocs.net/16045 [답안참고 블로그]https://debuglog.tistory.com/158

0%