1946번 - 신입 사원

1. 신입 사원

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😅 1차 시도 (실패 - 시간초과)

"""
Date    : 2021.11.28
Update  : 2021.11.28
Source  : 1946.py
Purpose : 1차 성적으로 정렬하고, 이전 1차 성적보다 순위가 낮은 경우 2차 성적으로 올라가면서 비교했다.
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""

for tc in range(int(input())):
    n = int(input())
    array = []
    second_test_min = 0
    max_count = 1

    for i in range(n):
        array.append(list(map(int, input().split())))

    array.sort(key=lambda x:x[0])
    second_test_min = array[0][1]

    for i in range(1, n):
         for j in range(i-1, -1, -1):
             if array[i][1] > array[j][1]:
                 max_count -= 1
                 break

    print(max_count)
    # answer.append(max_count)

# print(*answer, sep='\n')

b. 😊 2차 시도 (성공)

"""
Date    : 2021.11.28
Update  : 2021.11.28
Source  : 1946.py
Purpose : 1차 성적 또는 2차 성적이 다른 사람보다 높은 신입사원만 채용하는 코드를 작성하라.
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""

# 1차 성적으로 정렬하고, 1차 성적 1등의 2차 성적을 저장한다.
# 1차 성적 2등부터 꼴등까지 개인별 2차 성적과 2차 성적 최솟값을 비교한다.
# 만약, 2차 성적 최솟값보다 크다면, 탈락
# 2차 성적 최솟값보다 작다면, 합격

for tc in range(int(input())):
    n = int(input())
    array = []
    # 2차 성적 최솟값 저장
    second_test_min = 0
    # 1차 성적 1등은 어떤 경우에도 합격이기 때문에, 초기값을 1로 초기화함.
    max_count = 1

    for i in range(n):
        array.append(list(map(int, input().split())))

    # 1차 성적으로 오름차순 정렬한다.
    array.sort(key=lambda x:x[0])
    # 1차 성적 1등의 2차 성적을 저장한다.
    # 추후 이 값과 비교하여 합격 여부를 판단한다.
    second_test_min = array[0][1]

    # 1차 성적 1등을 제외한 나머지 지원자들을 비교
    for i in range(1, n):
        # 2차 성적 최소값보다 작다면, 합격 그리고 2차 성적 갱신
        if array[i][1] < second_test_min:
            max_count += 1
            second_test_min = array[i][1]

    print(max_count)


c. 🙄 회고

내 풀이

  • 처음에는 문제를 이해하는데 시간이 오래걸렸다.
  • 문제를 이해하고 풀었는데 시간초과가 발생했다.
    • 아무래도 O(테스트 케이스 * n * n)라서 그런 것 같다.
  • 단순하게, 2차 성적 최솟값을 갱신하면서 비교하는 방법을 사용했다.

반성

  • 테스트 케이스가 인자값으로 따로 주어질때는 빅오 표기법을 고민하며 풀어야겠다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

참고문헌

baekjoon. 1946번: 신입 사원 (acmicpc.net). Baekjoon. (accessed Nov 28, 2021)

이 글이 도움이 되었나요?

0 minutes ago
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.