[BOJ] 1946번 신입 사원 / 사용언어 : 파이썬(python)

※ 문제링크 

1946번: 신입 사원

해당 문제는 그리디 알고리즘과 관련된 문제로, 브루스포트 알고리즘을 접목해서 해결할 수 있는 문제였다. 문제에서 제시된 조건은 서류와 면접성적 중 1가지는 반드시 다른 지원자들보다 높은 성적이어야 합격이 가능하다는 점이었다. 서류심사 성적 또는 면접성적을 오름차순으로 정렬하여 반복문을 돌리면 1가지 성적만 가지고도 비교가 가능했기에 서류심사 성적을 오름차순으로 정렬한 후 그리디 알고리즘을 활용하여 모든 경우의 수를 비교하며 문제를 해결하였다.

처음 풀때는 2차원 배열을 활용하여 해결하였으나, 1차원의 형태로도 구현이 가능하다 판단하여 수정을 해보았다. 결과값은 모두 통과가 가능했으나, Python기준 1차원 배열의 속도와 메모리의 차이가 거의 2배 가까이 나는 것을 확인하였고, PyPy3로는 그보다 심하게 차이가 나는 것을 확인할 수 있었다. 자세한 문제풀이 방법과 코드는 아래와 같다. 

1. 입력받은 값의 수만큼 반복문을 수행할 수 있게 코드를 작성하고, 입력받은 값들을 리스트의 형태로 저장한다.

2. 2차원 배열의 경우 서류심사 순위를 기준으로 오름차순으로 정렬한 후 면접심사 성적을 차례대로 비교하고, 1차원 배열의 경우엔 입력받은 때 서류심사 성적을 기준으로 오름차순 순서대로 리스트에 저장하여 반복문을 돌려준다.

3. 조건 만족시 ans의 값에 +1을 해주고, 반복문 종료 후 결과값을 출력해준다.(시간 및 메모리 절감을 위해 sys를 사용하였습니다.)

 

# 2차원 배열 사용
import sys
# input = sys.stdin.readline
T = int(input())
for _ in range(T):
    N = int(input())
    ranks = []
    for _ in range(N):
        ranks.append(list(map(int, input().split())))
    ranks.sort() # 서류심사 성적을 오름차순으로 정렬
    ans = 1
    cp_values = [ranks[0][0], ranks[0][1]]
    for i in range(1, N): # 서류심사 1등은 조건 체크를 안해도 됨.(무조건 선발)
        # 서류심사 성적은 오름차순으로 정렬 후 체크를 하기때문에 무조건 뒤에 나오는 값들은 순위가 낮게 됨.
        # 면접심사 성적이 기존의 최고 랭크보다 높으면 선발, 아니면 탈락(선발시, 최고 순위 갱신)
        if ranks[i][1] < cp_values[1]:
            ans += 1
            cp_values[1] = ranks[i][1]
    print(ans)  
    
# 1차원으로 구현
import sys
# input = sys.stdin.readline
T = int(input())
for _ in range(T):
    N = int(input())
    ranks = [0 for _ in range(N)]
    for _ in range(N):
        inputValue = list(map(int, input().split()))
        ranks[inputValue[0]-1] = inputValue[1]
    ans = 1
    cp_values = ranks[0]
    for i in range(1, N): # 서류심사 1등은 조건 체크를 안해도 됨.(무조건 선발)
        # 서류심사 성적은 오름차순으로 정렬 후 체크를 하기때문에 무조건 뒤에 나오는 값들은 순위가 낮게 됨.
        # 면접심사 성적이 기존의 최고 랭크보다 높으면 선발, 아니면 탈락(선발시, 최고 순위 갱신)
        if ranks[i] < cp_values:
            ans += 1
            cp_values = ranks[i]
    print(ans)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.