[python code review] 4주차 (회의실 배정, 통계학, 신입 사원)

[회의실 배정] (하)

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

1931번: 회의실 배정

1. 큐 사용 

from collections import deque

n = int(input())
time = [list(map(int, input().split())) for _ in range(n)]
# 종료 시간, 종료 시간이 같다면 시작 시간순으로 정렬
time.sort(key=lambda x:(x[1], x[0]))
deq = deque(time)
start, end = deq.popleft()
count = 1
while deq:
    next_start, next_end = deq.popleft()
    if end <= next_start:
        count += 1
        end = next_end
print(count)

2. for문 사용 

n = int(input())
time = [list(map(int, input().split())) for _ in range(n)]
# 종료 시간, 종료 시간이 같다면 시작 시간순으로 정렬
time.sort(key=lambda x:(x[1], x[0]))
count = 0
end = 0
for i in range(n):
    next_start, next_end = time[i]
    if end <= next_start:
        count += 1
        end = next_end
print(count)

전형적인 그리디, 정렬 문제이다. 

 

[통계학] (하)

1. 코드 (Counter 사용)

from collections import Counter

n = int(input())
nums = [int(input()) for _ in range(n)]
print(round(sum(nums)/n)) # 산술평균
nums.sort()
print(nums[n//2]) # 중앙값
# 최빈값 구하기
countDic = Counter(nums)
# 최빈값을 가지는 키 구하기
maxCntKey = [k for k, v in countDic.items() if max(countDic.values()) == v]
# 최빈값 구하기
if len(maxCntKey) >= 2:
    # 두번째로 작은 값 출력
    print(sorted(maxCntKey)[1])
else:
    print(maxCntKey[0])
print(max(nums)-min(nums)) # 범위

최빈값 조건 때문에 조금 애를 먹었다. 

 

2. 코드(defaultdict 사용)

from collections import defaultdict

n = int(input())
nums = [int(input()) for _ in range(n)]
print(round(sum(nums)/n)) # 산술평균
nums.sort()
print(nums[n//2]) # 중앙값
# 최빈값 구하기
countDic = defaultdict(int)
for n in nums:
    countDic[n] += 1
# 최빈값을 가지는 키 구하기
maxCntKey = [k for k, v in countDic.items() if max(countDic.values()) == v]
# 최빈값 구하기
if len(maxCntKey) >= 2:
    # 두번째로 작은 값 출력
    print(sorted(maxCntKey)[1])
else:
    print(maxCntKey[0])
print(max(nums)-min(nums)) # 범위

collections 모듈의 Counter랑 defaultdict 중에서 뭐가 더 빠를지 궁금해서 해봤는데 실행 속도는 비슷했다.

 

[신입사원] (하)

1. 코드

for _ in range(int(input())):
    n = int(input())
    scores = [list(map(int, input().split())) for _ in range(n)]
    scores.sort(key=lambda x:x[0]) #서류 순으로 줄 세우기
    count = 0
    goodInterview = 100001 # 합격한 사람 중 면접을 제일 잘 본 사람의 등수
    for i in range(n):
        s1, s2 = scores[i]
        if s2 < goodInterview:
            goodInterview = s2
            count += 1
    print(count)

scores = [list(map(int, input().split())) for _ in range(n)]
scores.sort(key=lambda x:x[0]) #서류 순으로 줄 세우기

 

scores = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:x[0])로 한번에 처리 가능

 

2. 시간 초과 발생한 코드

for _ in range(int(input())):
    n = int(input())
    scores = [list(map(int, input().split())) for _ in range(n)]
    scores.sort(key=lambda x:x[0]) #서류 순으로 줄 세우기
    passed = [] # 통과한 사람들의 성적 기록
    count = 0
    for i in range(n):
        check = True
        t1, t2 = scores[i]
        for p1, p2 in passed:
            # 서류도 면접도 합격한 사람에 비해 떨어지는 경우
            if p2 < t2:
                check = False
                break
        if check:
            passed.append([t1, t2])
            count += 1
    print(count)

 

우선 시험 성적대로 정렬하고, 시험에 합격한 사람들의 면접 등수를 비교하여 합격한 사람들의 면접 등수보다 뒤쳐지면 면접도 시험도 잘 못본거니까 탈락하게 되도록(ㅜㅜ) 구현하였다. 그런데 생각해보니 합격한 사람들의 면접 등수 중 가장 면접을 잘 본 사람보다 등수가 높으면 됐다. 그래서 합격한 사람들을 배열로 담지 않고 가장 면접 잘 본사람의 등수만 변수로 관리해주었더니 통과했다.