[그리디] 백준 신입 사원 1946번 with Python3

 

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

1946번: 신입 사원

 

문제

정답 풀이

import sys

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

for i in range(0,T):
    Cnt = 1
    people = []
    
    N = int(input())
    for i in range(N):
        Paper, Interview = map(int,sys.stdin.readline().split())
        people.append([Paper, Interview])

    people.sort() # 서류 기준 오름차순 정렬
    Max = people[0][1]
    
    for i in range(1,N):
        if Max > people[i][1]:
            Cnt += 1
            Max = people[i][1]

    print(Cnt)

출처:https://kyoung-jnn.tistory.com/entry/%EB%B0%B1%EC%A4%801946%EB%B2%88%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EC%8B%A0%EC%9E%85-%EC%82%AC%EC%9B%90

해석

서류 기준으로만 오름차순 정렬을 하고 나서 비교해서 살아남을 때마다 그 값을 갱신해주기만 하면 됬다니...

 

교집합 까지 생각햇던 내가 바보같다. 

 

문제를 풀어가며 느끼는 점은, 그리디 알고리즘은 일종의 정렬에 가깝다는 점이다. 내가 올바른 순서로 선택할 수 있게끔 정렬을 하고, 탐욕의 기준을 지속적으로 적절하게 유지 시키는게 관건 같다.

내 풀이

import sys
input = sys.stdin.readline

case = int(input())
ans = []

for _ in range(case):

    # 입력
    n = int(input())
    rank = [[0]*2 for _ in range(n)]
    check = 0
    chk2 = 100001
    for i in range(n):
        a, b = map(int, input().rstrip().split())
        if a == 1 and b == 1:
            check = 1
            break
        elif a == b:
            chk2 = min(chk2, a)
        elif a == 1:
            resume_1st = b
        elif b == 1:
            interview_1st = a
        rank[i][0] = a
        rank[i][1] = b
    # a = 1차 서류심사 순위. b = 2차 면접심사 순위.

    if check == 1:
        ans.append('1')
        continue
    else:
        cnt = 0
        for i in range(n):
            if rank[i][0] == 1 or rank[i][1] == 1:
                cnt += 1

            elif resume_1st > rank[i][1] and interview_1st > rank[i][0]:
                if rank[i][0] == rank[i][1] and rank[i][0] > chk2:
                    continue
                cnt += 1

        ans.append(f'{cnt}')

print('\n'.join(ans))

# # 1차 서류심사 순위 기준 정렬
# rank.sort()
# # 1차 서류심사 1등 대비 2차 면접 순위 상위권자 + 1차 1등
# survive1 = rank[0: int(interview_1st[0])]
# # 2차 면접 순위 기준 정렬
# rank.sort(key=lambda x: x[1])
# # 2차 면접심사 1등 기준 1차 면접순위 상위권자 + 2차 1등
# survive2 = rank[0: resume_1st[1]]

# # set로 변환하는 과정
# for i in range(len(survive1)):
#     c, d = map(int, survive1[i])
#     survive1[i] = str(f'{c} {d}')

# for i in range(len(survive2)):
#     c, d = map(int, survive2[i])
#     survive2[i] = str(f'{c} {d}')

# temp1 = set(survive1)
# temp2 = set(survive2)

# #교집합 = ans
# ans = temp1 & temp2

# print(len(ans))

해설

1등의 각각 면접 서류 순위를 반대로 이길 수만 있으면 무조건 답이라고 생각했다.

 

실제로 예제도 잘 통과 되었고... 근데 결과적으론 아주아주 잘못 생각했다.