. 신입사원 장그래는 정규직이 될 수 없다 (백준 1946 : 신입사원)
본문 바로가기
프로그래밍 공부/백뚠

신입사원 장그래는 정규직이 될 수 없다 (백준 1946 : 신입사원)

by 불냥이_ 2021. 1. 3.

이 드라마가 포스터처럼 희망찬 내용이었나?

몇 년전에 우리네의 회사 생활을 대변해주고 위로해주는 미생이라는 드라마가 세간의 화제가 되었던 적이 있었다.

나는 웹툰으로밖에 안봤지만, 당시 신입사원이었던 나에게 많은 공감이 되었고 신입사원으로서의 마음가짐을 심게해 준 미생이었는데.

 

신입사원 장그래는 결국에는 정규직이 되지 못하였지만 (스포인가?)

사실 청년실업자가 넘쳐나는 이 시대에는 비정규직 장그래조차 되기힘든게 현실아니겠는가

(백수가 되어버린 나를 포함하여 ㅠㅡㅠ)

 

 

그런데 심지어 이번 문제에서는 우리는 인사담당자가 되어서 실날같은 희망을 가지고 지원한 수 많은 청년들을 떨어뜨려야한다.

 

 

하지만 어쩌겠는가.

취직이 잘 되는 사회를 만들던가! (속이 뻥)

 

 

어쩔수 없다. 눈물을 머금고 칼춤을 춰 손에 피를 묻히자.

인사 담당자도 그저 한낱 월급쟁이에 불과하니깐.

 

까라면 까야지

 

 

1946번: 신입 사원 (acmicpc.net)

 

1946번: 신입 사원

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성

www.acmicpc.net

문제가 어려울 수도 있는데, 최종합격자들은 다른 합격자들에 비해서 면접점수나 서류점수 하나는 높아야 된다는 것이다.

 

예제를 보자.

1번 예제는 (3,2) (1,4) (4,1) (2,3) (5,5) 이다.

 

 

(서류심사 순위, 면접심사 순위) 인데,

여기서 중요한 것은 각 숫자는 점수가 아니라 '순위'라는 것이다. (조금 있다가 중요한 복선으로 작용한다. 기억해두자)

 

 

이 예제에서 결과부터 말하면, 합격자는 (3,2) (1,4) (4,1) (2,3) 이다.

 

각각의 합격자는 다른 합격자에 비해서 서류든 면접이든 한가지는 우수하다.

첫번째 합격자 (3,2)를 보자. 이 합격자는 (1,4)과 (2,3) 에 비해서 면접이 우수하다. (4,1)에 비해서는 서류 순위가 높다.

 

다른 합격자들도 마찬가지인데, 불쌍한 (5,5)만 다른 합격자들에 비해서 서류도 심사도 다 미비하기 때문에 뜨거운 합격을 받게되었다. (내 이야기를 보는 것 같아 슬프네 ㅜ.ㅜ)

 

 그럼 1번 예제의 경우에는 4명이 되는 것이다.

 

 

 

 

" 오옹? 그러면 완전탐색으로 비교해도 되지 않을까요? "

 

 

 

그렇게 생각할 수도 있겠지만, 백준은 그리 만만한 상대는 아니다.

시간 제한 2초임에도 불구하고 테스트 케이스가 최대 20개, 각 지원자 수가 10만이기때문에 (곱하면 200만개의 입력을 받아야 된다는 것이다!)

 

여유롭진 않다.

 

실제로 필자는 그냥 완전탐색에 가깝게 풀었다가 심사위원님께 많이 혼났다.

 

 

니들은 이런거 하지마라

 

 

우선 로직의 뼈대는 지원자 점수를 받아서 어딘가에 저장해놔야한다.

그리고 우선 서류순으로 오름차순으로 정렬을 한뒤, 그 다음 하나하나 비교해나가면서 서류와 면접 둘 다 미비한 지원자들을 떨어뜨려야 한다.

 

 

말로만 하면 어려우니 두번째 예제로 설명하겠다.

두번째 예제의 지원자 수는 7명이고, 이를 서류심사 오름차순으로 정렬하면 다음과 같다.

(오름차순으로 정렬하는 이유는 한 가지가 일등이면 무조건 뽑히게 되기 때문에 좋은 비교 기준이 된다.)

 

 

(1,4) (2,5) (3,6) (4,2) (5,7) (7,1) (7,3)

 

 

우선 (1,4) 의 경우는 서류가 1등이므로 무조건 합격이다. (축하드립니다)

그렇다면 다른 참가자들은 면접 순위가 4등 안에 들어야한다. 

 

왜 그런지는 다음 지원자를 보자. (이 친구는 딱 알맞게 좋은 예가 되어버렸다.)

 

 

(2,5) 는 (1,4)에 비해서 아쉽게도 서류 심사도 바로 뒤이고 면접도 바로 뒤이다.

안타깝게도 평균으로 따진다면 상위권일 수도 있지만, 다른 합격자보다 둘 다 뒤쳐진다면 채용할 수 없다는 인사 채용 원칙을 어길수는 없다.

(구제해주고 싶지만 우리는 한낱 월급쟁이다. ㅠ.ㅠ)

 

 

똑같이 (3.6)도 제외된다. 하지만 그 다음(4,2)는 어떨까.

이 친구는 서류 1등인 친구에 비해서 면접 점수가 높다. 그렇기 때문에 합격할 수 있다.

 

 

다음 지원자는 (5,7). 

 

음....

이 친구는 (4,2)보다 둘 다 떨어진다. 

 

 

 

'다음번에 좋은 인연으로 다시 만날 수 있으면 좋겠습니다 ^^'

 

어림도 없지 컷!

 

 

 

 

그런데 잠깐,

 

여기가 중요 포인트이다!

갑자기 기준이 서류심사 1등의 면접 순위 4등(1,4)에서 면접 순위 1등(4,2)으로 바뀐 것에 주목하자.

 

다시 한번 합격 기준을 상기시키면 "합격자들은 다른 합격자보다 서류심사 순위와 면접심사 순위 모두 낮아서는 안된다." 인데, 우선 서류심사 오름차순으로 정렬했으므로, (4,2) 보다 뒤에 있는 사람들은 무.조.건. 서류심사 순위는 낮다.

 

그렇다면 면접 순위라도 높아야 하는데, 원래는 (1,4)의 4등이 기준이었지만, 서류심사는 1보다 낮지만 면접 순위가 4보다 높은 (4,2)가 등장했다.

 

그러면 이제 남은 후보자들은 면접순위가 2등 보다 높아야 된다는 것이다. (1등밖에 안남았다.)

 

이것을 기억하며 계속 진행해보자.

 

 

 

다음 지원자는 (6,1)

딱 그 후보자가 나왔다.

 

면접 1등이다. 무조건 합격

 

1등이 최종 순위이기 때문에 이 다음 후보자들은 어떠한 면접 순위를 가지고 있던간에 안타깝지만 탈락하게 된다.

 

 

그렇다면 (1,4) (4,2) (6,1) 이 세명이 최종합격자가 된다.

마지막으로 정리하면, 처음 (1,4) 를 만난 뒤로는 합격 기준이 면접 순위 4등 이내였는데,

(4,2)를 만난 뒤로는 면접 순위 2등 이내가 기준이 되어버렸다.

 

즉, 면접 순위가 기준이 되는 면접 순위보다 높은 친구를 만나면, 그 친구는 합격이 되고 면접 기준은 그 높은 친구가 기준이 되는 것이다.

 

 

이 논리를 기반으로 코드를 구현해보자.

 

우선 테스트 케이스가 여러개 있으므로, 테스트 케이스마다 구분해주기 위해서 다음처럼 입력(T)를 받아준다.

그리고 반복되는 심사과정은 method fresh() 로 실행해주자. 

T = int(sys.stdin.readline().rstrip())
for t in range(T):
    fresh()

 

그리고 method fresh의 입력부는 다음과 같이 구성된다.

def fresh():
    
    N = int(sys.stdin.readline().rstrip())
    waiting = []
    for n in range(N):
        a, b = map(int,sys.stdin.readline().split())
        waiting.append([a,b])
    waiting.sort()

N은 지원자의 수를 입력받고, waiting은 지원자의 서류심사순위(a), 면접심사순위(b)를 저장하게 된다.

그리고 서류심사순위를 오름차순으로 정렬한다.

 

    cnt = N
    minimum = waiting[0][1]
    for i in range(1,N):
        if minimum < waiting[i][1]:
            cnt -= 1
        else:
            minimum = waiting[i][1]
    print(cnt)

그리고 cnt는 최종 합격자의 수를 말하는데, 만약 심사기준보다 낮은 순위를 가진 지원자를 탈락시키면서 cnt를 하나씩 감소시킬 것이다.

 

minimum은 현재 기준이 되는 면접심사 순위가 되며(이미 서류심사 순위 오름차순으로 정렬한 것을 기억하자.),

for 문을 1에서 (waiting[0]은 서류심사에서 1위를 했기 때문에 무조건 합격이다.) N까지 돌리면서 판별한다.

 

 

만약, 어느 지원자의 면접 순위가 현재 기준(minimum)보다 낮으면 탈락(cnt 1감소)할 것이며, 높다면 그 친구는 합격시키고 등락 기준 면접순위는 그 친구의 면접 순위가 될 것이다. (else문)

 

그래서 완성 코드는 다음과 같다.

 

import sys

def fresh():
    
    N = int(sys.stdin.readline().rstrip())
    waiting = []
    for n in range(N):
        a, b = map(int,sys.stdin.readline().split())
        waiting.append([a,b])
    waiting.sort()

    cnt = N
    minimum = waiting[0][1]
    for i in range(1,N):
        if minimum < waiting[i][1]:
            cnt -= 1
        else:
            minimum = waiting[i][1]
    print(cnt)


T = int(sys.stdin.readline().rstrip())
for t in range(T):
    fresh()

 

그래서 결과를 보면 다음과 같다.

일이 끝났으니 퇴근하자~

속도가 조금 큰 것 같지만 뭐 합격했으니 장땡아닌가?

 

그럼, 인사과분들 늦었지만 퇴근해주세요~~

안뇽~~~~

 

 

 

 

 

 

 

하고 싶지만...

 

 

좋은 이야기의 기준 중 하나는 복선을 깔끔하게 회수한다는 것이라고 필자는 생각하는데,

필자가 아까 독자 분들에게 복선을 하나 던져준 것이 기억나시는가?

 

위에 있는 문장을 독자들에게 다시 보여드리겠다.

 

이 문장을 기억하시는가? 필자는 이미 복선으로 깔아두었다.

 

"??? 이게 무슨 복선이라는 거죠?"

 

 

들어보시라.

점수와 순위의 차이는 무엇일까?

 

점수는 50점, 76점, 80점 이렇게 연속적인 숫자가 아닐 수도 있지만, 

순위의 가장 중요한 요소는 1부터 시작하여 연속적으로 이어진다는 것이다. (동 순위가 없다면, 1등, 2등, 3등 다음에는 무조건 4등이다.)

 

 

그런데 자료 구조의 요소 중에 순위와 똑같이 무.조.건 연속적인 숫자로 이루어진 것이 있다.

 

 

 

바로 리스트의 '인덱스'이다.

 

 

 

즉, 순위를 리스트의 인덱스로 활용할 수 있다는 것이다.

 

waiting이 [서류심사 순위, 면접심사 순위]의 이차원 배열로 이루어졌던 것을 기억하는가?

그런데 서류심사 순위를 인덱스로 활용하면 우리는 waiting을 1차원 배열로 바꿀 수 있다.

 

 

def fresh():
    
    N = int(sys.stdin.readline().rstrip())
    waiting = []
    for n in range(N):
        a, b = map(int,sys.stdin.readline().split())
        waiting.append([a,b])
    waiting.sort()

    cnt = N
    minimum = waiting[0][1]
    for i in range(1,N):
        if minimum < waiting[i][1]:
            cnt -= 1
        else:
            minimum = waiting[i][1]
    print(cnt)
def fresh():
    
    N = int(sys.stdin.readline().rstrip())
    waiting = [0]*(N)
    for n in range(N):
        a, b = map(int,sys.stdin.readline().split())
        waiting[a-1] = b

    cnt = N
    minimum = waiting[0]
    for i in range(1,N):
        if minimum < waiting[i]:
            cnt -= 1
        else:
            minimum = waiting[i]
    print(cnt)

 

같은 method fresh() 부분이지만, 위는 2차원 배열을 사용했을 때, 아래는 서류심사 순위를 인덱스로 활용했을 때이다.

 

어떤 차이가 보이는가?

waiting에 지원자의 정보를 집어넣을 때, 위는 [서류심사 순위(a), 면접심사 순위(b)]를 넣었지만

아래에서는 waiting[서류심사 순위] (index는 0부터 시작하기 때문에 a-1로 했다.) = 면접심사 순위로 바뀌어져 있다.

 

 

그 다음엔 어떤 차이가 있는가?

 

아랫부분에서는 sort가 보이지 않는다.

왜냐면 리스트의 index는 이미 오름차순으로 정렬되어있기 때문에, 서류심사 기준을 인덱스로 활용하면 자동으로 정렬이 되는 것이다. 

 

이 부분만으로 크게 속도를 끌어올릴 수 있을거라고 기대되는데, 직접 결과로 증명하자.

 

붉은 색으로 칠한 것도 아닌데 3배 빨라졌다.

원래는 6212ms 였지만, sort를 지우고, 1차원 배열로 바꾸니 2184ms 로 약 3배가량 빨라진 것이 보이는가?

놀라울 정도의 향상이다. (뿌듯 ^-^. 실제로 얼마나 뿌듯했는지 독자분들은 아실랑가.)

 

 

조금만 더 생각을 해보고 코드를 개선해본 결과, 속도가 3배나 빨라졌다.

이 덕분에 인사 담당자들은 야근하지 않고 기분 좋게 칼퇴를 할 수 있을 것이다. 

 

 

 

 

그들이 기분좋게 칼퇴하는 사이에 합격되지 못한 자들은 오늘도 씁쓸하게 밤을 보내겠지만...

 

 

 

 

그래도 다들 돈 많이 주고, 좋은 회사에 합격하기 바라면서, 이 글을 이만 끝내겠다.

나를 비롯한 전국 백만 취준생들 파이팅!

 

아자아자!

 

댓글