코딩 테스트 연습 문제 코딩테스트 연습에 공개된 문제는 (주)그렙이 저작권을 가지고 있습니다.(지문 하단에 별도 저작권 표시 문제 제외)코딩테스트 연습 문제의 지문, 테스트케이스, 풀이 등과 같은 정보는 비상업적, 비영리적 용도로 게시할 수 있습니다.다만 문제의 지문, 풀이 등과 같은 정보를 단순히 게시하는 것을 넘어, 이를 바탕으로 문제를 풀고 채점이 가능하도록 하는 등의 방식으로 활용하는 것은 제한됩니다. ※ 2020 KAKAO BLIND RECRUITMENT, Summer/Winter Coding 등의 문제는 기업 코딩 테스트에 나온 문제이나, 코딩테스트 연습에 공개된 문제이기 때문에 마찬가지로 비상업적, 비영리적 용도로 게시할 수 있습니다. (2021. 01. 08 업데이트)
문제 정보
- 프로그래머스
- python
- level 2
- 점수 : 3
- 문제 링크
문제
문제 설명
문제 설명 펼치기/접기
당신은 온라인 게임을 운영하고 있습니다. 같은 시간대에 게임을 이용하는 사람이 m명 늘어날 때마다 서버 1대가 추가로 필요합니다. 어느 시간대의 이용자가 m명 미만이라면, 서버 증설이 필요하지 않습니다. 어느 시간대의 이용자가 n x m명 이상 (n + 1) x m명 미만이라면 최소 n대의 증설된 서버가 운영 중이어야 합니다. 한 번 증설한 서버는 k시간 동안 운영하고 그 이후에는 반납합니다. 예를 들어, k = 5 일 때 10시에 증설한 서버는 10 ~ 15시에만 운영됩니다.
하루 동안 모든 게임 이용자가 게임을 하기 위해 서버를 최소 몇 번 증설해야 하는지 알고 싶습니다. 같은 시간대에 서버를 x대 증설했다면 해당 시간대의 증설 횟수는 x회입니다.
다음은 m = 3, k = 5 일 때의 시간대별 증설된 서버의 수와 증설 횟수 예시입니다.
| 시각 | 게임 이용자의 수 | 증설된 서버의 수 | 증설 횟수 |
|---|---|---|---|
| 0 ~ 1 | 0 | 0 | 0 |
| 1 ~ 2 | 2 | 0 | 0 |
| 2 ~ 3 | 3 | 1 | 1 |
| 3 ~ 4 | 3 | 1 | 0 |
| 4 ~ 5 | 1 | 1 | 0 |
| 5 ~ 6 | 2 | 1 | 0 |
| 6 ~ 7 | 0 | 1 | 0 |
| 7 ~ 8 | 0 | 0 | 0 |
| 8 ~ 9 | 0 | 0 | 0 |
| 9 ~ 10 | 0 | 0 | 0 |
| 10 ~ 11 | 4 | 1 | 1 |
| 11 ~ 12 | 2 | 1 | 0 |
| 12 ~ 13 | 0 | 1 | 0 |
| 13 ~ 14 | 6 | 2 | 1 |
| 14 ~ 15 | 0 | 2 | 0 |
| 15 ~ 16 | 4 | 1 | 0 |
| 16 ~ 17 | 2 | 1 | 0 |
| 17 ~ 18 | 13 | 4 | 3 |
| 18 ~ 19 | 3 | 3 | 0 |
| 19 ~ 20 | 5 | 3 | 0 |
| 20 ~ 21 | 10 | 3 | 0 |
| 21 ~ 22 | 0 | 3 | 0 |
| 22 ~ 23 | 1 | 0 | 0 |
| 23 ~ 24 | 5 | 1 | 1 |
모든 게임 이용자를 감당하기 위해 최소 7번 서버를 증설해야 하며, 이보다 적은 수의 서버 증설로는 모든 게임 이용자를 감당할 수 없습니다.
0시에서 23시까지의 시간대별 게임 이용자의 수를 나타내는 1차원 정수 배열 players, 서버 한 대로 감당할 수 있는 최대 이용자의 수를 나타내는 정수 m, 서버 한 대가 운영 가능한 시간을 나타내는 정수 k가 주어집니다. 이때, 모든 게임 이용자를 감당하기 위한 최소 서버 증설 횟수를 return 하도록 solution을 완성해 주세요.
제한사항
players의 길이 = 24- 0 ≤
players의 원소 ≤ 1,000 players[i]는i시 ~i+1시 사이의 게임 이용자의 수를 나타냅니다.
- 0 ≤
- 1 ≤
m≤ 1,000 - 1 ≤
k≤ 24
테스트 케이스 구성 안내
아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.
| 그룹 | 총점 | 추가 제한 사항 |
|---|---|---|
| #1 | 5% | m = 1, k = 1 |
| #2 | 7% | k = 1 |
| #3 | 88% | 추가 제한 사항 없음 |
입출력 예
| players | m | k | result |
|---|---|---|---|
| [0, 2, 3, 3, 1, 2, 0, 0, 0, 0, 4, 2, 0, 6, 0, 4, 2, 13, 3, 5, 10, 0, 1, 5] | 3 | 5 | 7 |
| [0, 0, 0, 10, 0, 12, 0, 15, 0, 1, 0, 1, 0, 0, 0, 5, 0, 0, 11, 0, 8, 0, 0, 0] | 5 | 1 | 11 |
| [0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 5, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1] | 1 | 1 | 12 |
풀이
풀이 코드
1
2
3
4
5
6
7
8
9
10
11
12
def solution(players, m, k):
active_servers = [0] * 24 # 시간대별 증설된 서버 수
count = 0 # 증설 횟수
for h, player in enumerate(players): # h : hour
required_servers = player // m # 지금 시점에 필요한 증설 서버 수
add = max(required_servers - active_servers[h], 0) # 이 시점에 증설할 서버 수
count += add # 증설 횟수에 추가
for j in range(k):
if h + j > 23:
break
active_servers[h+j] += add
return count
풀이 방식
- 시간대별 증설된 서버 수를 담는 배열을 만들어, 증설 현황과 이력을 볼 수 있게 한다.
- 각 시간대별로 반복을 수행하며 현재 증설된 서버와 증설되어야 할 서버의 개수를 비교한 뒤 증설한다.
리뷰
점수 리뷰
- 오랜만에 문제풀이를 하는거라 몸풀 겸 난이도가 높지 않은 문제를 선택했다.
- 그런데 3점이라니.. 정말 비효율적으로 풀었나보다
개선 포인트
개선해야 할 부분
- k번 반복 수행
1
2
3
4
for j in range(k):
if h + j > 23:
break
active_servers[h+j] += add
- 이 부분은 매 시간대마다 k번 반복을 수행한다.
- 실제로는 “구간 증가(range add)” 인데, 이를 매번 각 시간을 반복하며 더하고 있는 것이다.
- 따라서 O(24 $\cdot$ k) 의 시간복잡도를 가진다.
- 증설 서버 현황을 실제 값으로 관리함
1
2
3
4
5
6
7
8
active_servers = [0] * 24
...
add = max(required_servers - active_servers[h], 0)
...
for j in range(k):
if h + j > 23:
break
active_servers[h+j] += add
- 지금 증설한 서버가 앞으로 k시간 동안 영향을 미친다는 사실을 매 시간대마다 미리 계산해 저장하는 방식
| 문제의 이유 | 개선점 |
|---|---|
| 현재 필요하지 않은 미래의 정보를 미리 계산함 | “지금 활성화된” 증설 서버 개수가 몇개인지만 필요 |
| 같은 서버 증설 정보가 k번 중복 저장됨 | 논리적으로는 서버 n대가 h부터 h+k-1까지 유지된다라는 사실만 있으면 됨 |
개선 방법
- 누적합 + 차분 배열의 방식으로 개선한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(players, m, k):
diff = [0] * 25 # 차분 배열 (h+k 처리용)
active = 0 # 현재 활성화된 증설 서버 수
count = 0 # 증설 횟수
for h, player in enumerate(players):
active += diff[h] # 현재 활성화된 증설 서버 수 업데이트
required = player // m # 지금 필요한 증설 서버 수
add = max(required - active, 0) # 이 시점에 증설할 서버 수
if add > 0: # 신규 증설 정보가 있을 때에만 수행
count += add
active += add # 추가 증설 서버 수 업데이트
if h + k < 25:
diff[h+k] -= add # 미래에 종료되는 증설 서버 기록
return count
- O(24 $\cdot$ k) 의 시간 복잡도가 O(24)로 개선된다.
- 증설 서버 현황(active_servers)에서 인덱스로 값을 조회하는 작업이 사라진다.
Comments