[PY] 1946 : 신입사원

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

그리디 알고리즘을 활용 할 수 있는 문제 중 하나이다.

내 생각엔 이렇게 했다 :

1. 전체 입력을 받고, 정렬을 좌측 점수에 대해 한 것, 우측 점수에 대해 한 것 두 가지로 나누어 둔다. 각 정렬은 오름차순이다.
2. 그리고 각 정렬의 첫번째 아이템은 어쨌든 1등일 것이니, 그 값을 기반으로 갱신이 이루어지도록한다.
3. 여기서부터 생각이 조금 복잡했는데, 자료구조 set을 쓰면 중복을 방지 할 수 있다고 한다. 혹시나 양쪽에서 빠질 수 있는 연산이 우려되어.. (양 쪽 분야에 대해 등수가 둘 다 꼴찌면 수가 두 번빠지는 상황 염려, 왜냐하면 조건에 안맞으면 하나씩 빼는 루틴을 생각해서) 이렇게 적어보니 괜찮은 아이디어라고 생각했다.
4. 그렇게 해서 set에 모인 갯수 만큼 result에서 뺀게 답이다. 라고 생각했으나 틀렸습니다. 가 나타났다.

pivot 갱신이 가끔 일어나야한다는 점이 좀 걸렸다. 그리고 파일럿 코는 동시에 좌측 정렬을 끝낸 상태에 오른쪽 비교를 하길 권했다.

엔터는 누르지 말걸 ㅈㅅ

이게 첫 아이디어로 출발한 코드이다.

# 신입사원 기존 백업코드

import sys
input = sys.stdin.readline

testCaseCnt = int(input())
result = 0

for i in range(testCaseCnt):
    applyCnt = int(input())
    result = applyCnt
    pairs = set()
    originData = []
    for j in range(applyCnt):
        leftRank, rightRank = map(int, input().split())
        originData.append([leftRank, rightRank])

    sortedByL = sorted(originData, key=lambda x: x[0])
    sortedByR = sorted(originData, key=lambda x: x[1])

    LpivotL = sortedByL[0][0]
    LpivotR = sortedByL[0][1]

    RpivotL = sortedByR[0][0]
    RpivotR = sortedByR[0][1]
    for j in range(1, len(originData)):
        if(LpivotL < sortedByL[j][0] and LpivotR < sortedByL[j][1]):
            pairs.add((sortedByL[j][0], sortedByL[j][1]))

        if(RpivotL < sortedByR[j][0] and RpivotR < sortedByR[j][1]):
            pairs.add((sortedByR[j][0], sortedByR[j][1]))


    result -= len(pairs)
    print(result)

상당히 개선된 코드. 이건 꽤 재밌는 문제였다고 생각한다!!

import sys
input = sys.stdin.readline

testCaseCnt = int(input())

for i in range(testCaseCnt):
    applyCnt = int(input())
    result = 1
    originData = []
    for j in range(applyCnt):
        leftRank, rightRank = map(int, input().split())
        originData.append([leftRank, rightRank])

    sortedByL = sorted(originData, key=lambda x: x[0])
    
    LpivotR = sortedByL[0][1]
    for j in range(1, len(originData)):
        if(LpivotR > sortedByL[j][1]):
            result += 1
            LpivotR = sortedByL[j][1]


    print(result)