NIRVANA
[level 1] 실패율(성공!!!) 본문
문제
슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.
이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.
- 실패율은 다음과 같이 정의한다.
- 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.
제한사항
- 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
- stages의 길이는 1 이상 200,000 이하이다.
- stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
- 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
- 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
- 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
- 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.
문제 풀이 접근법1
1) 배열의 길이를 확인하여 참가자가 몇 명인지 확인한다.
2) stage 배열에 유저들이 막힌 스테이지가 어디어디인지 확인 및 딕셔너리로 정의 (counter 함수 사용)
3) 각 Stage의 실패율을 구한다. 이때, 플레이어의 수는 이전 스테이지를 클리어하지 못한 사람은 제외 되어야 하므로 플레이어 수에서 해당 스테이지에서 막힌 유저의 수만 큼을 빼주어 업데이트 한다.
4) 만약 유저가 막힌 스테이지가 주어진 스테이지의 개수(N)보다 크다면, 해당 유저가 거친 스테이지의 실패율을 따로 구해준다.
5) 만약 유저들이 막힌 스테이지가 다 같다면 이전 스테이지들은 실패율 0으로 정해준다.
6) 내림차순 정렬 후 반환한다.
from collections import Counter
def solution(N, stages):
fail = {}
s = 0
situ = dict(sorted(dict(Counter(stages)).items()))
player= len(stages)
for i in list(situ):
if i <= N:
fail[i] = situ[i]/ player
player -= situ[i]
elif i > N:
fail[i-1] = (situ[i] - situ[i]) / player
player -= situ[i]
if len(situ) == 1:
for key in fail.keys():
s = key
for i in range(s):
fail[i+1] = 0
sorted_situ = dict(sorted(fail.items(), key=lambda x:x[1], reverse=True))
return list(sorted_situ)8, 16, 17, 18, 19, 20, 21, 22번 테스트 케이스를 제외하고는 다 실패했다.
사실 놀랄 것도 없음 4번이랑 5번이 너무 논리적 허점이 많아서...반례 400개 나올듯
문제 풀이 접근법2
1) 배열의 길이를 확인하여 참가자가 몇 명인지 확인한다.
2) stages 배열에 유저들이 막힌 스테이지와 해당 스테이지에 있는 유저 수를 구한다.
3) 만약 situ의 길이가 1 이상이면 fail 딕셔너리의 i에 (i=스테이지) situ[i] (클리어를 하지 못한 유저의 수) / palyer 수로 실패율을 정의한다.
4) 이후 player 수에서 situ[i](클리어를 하지 못한 유저의 수)를 빼주어서 스테에지에 도달한 플레이어의 수를 업데이트한다.
5) 3번과 4번 상황에서 if를 한 번 더 사용하여 i가 situ에 있는지 없는지를 확인한다. 있자면 위의 방식 그대로, 없다면 해당 스테이지 보다 큰 스테이지를 구한다.
6) 큰 스테이지를 클리어한 사람수를 빼주어 그 다음 스테이지에 도달하지 못한 플레이어 수를 빼고, 실패율은 0으로 정의 한다.
7) 만약 situ의 길이가 1이하이면, 해당 스테이지 이전의 스테이지는 실패율을 0으로 선언하고, 해당 스테이지의 실패율은 플레이어 수 / 플레이어 수로 정의 한다.
8) 실패율을 기준으로 스테이지를 sorting하여 반환한다.
from collections import Counter
def solution(N, stages):
fail = {}
s = 0
situ = dict(sorted(dict(Counter(stages)).items()))
player= len(stages)
if len(situ) > 1:
for i in range(len(list(situ))):
level = i+1
if level in list(situ):
fail[level] = situ[level]/ player
player -= situ[level]
else:
big_stages = [k for k in list(situ) if k > level]
for j in big_stages:
fail[level] = 0 / player
player -= situ[j]
else:
key = list(situ)[0]
value = situ[key]
for i in range(key):
level = i+1
fail[level] = 0 / player
fail[key] = value / player
sorted_situ = dict(sorted(fail.items(), key=lambda x:x[1], reverse=True))
return list(sorted_situ)8, 17, 18, 19, 20, 21, 22, 27 빼고 틀렸다...ㅎ
생각해보니까 전체 스테이지 수보다 큰 레벨에 있는 사람은 게임을 올클했다는 뜻이니까
반복문도 N만큼만 돌려야하고, 만약 사람들이 멈춰있는 스테이지가 N보다 작으면 사람들이 멈춘 스테이지 ~ N까지의 스테이지에 대한 실패율도 추가해주어야 했다.
문제 풀이 접근법3
for 반목문을 N만큼 반복으로, 만약 사람들이 멈춰있는 스테이지가 N보다 작으면 사람들이 멈춘 스테이지 ~ N까지의 스테이지에 대한 실패율도 0으로 추가했다.
from collections import Counter
def solution(N, stages):
fail = {}
s = 0
situ = dict(sorted(dict(Counter(stages)).items()))
player= len(stages)
max_stages = max(list(situ))
if len(situ) > 1:
for i in range(max_stages-(max_stages-N)):
level = i+1
if level in list(situ):
fail[level] = situ[level]/ player
player -= situ[level]
else:
big_stages = [k for k in list(situ) if k > level]
for j in big_stages:
fail[level] = 0 / player
player -= situ[j]
else:
key = list(situ)[0]
value = situ[key]
if key >= N:
for i in range(key):
level = i+1
fail[level] = 0 / player
else:
for i in range(key, N):
level = i+1
fail[level] = 0 / player
fail[key] = value / player
sorted_situ = dict(sorted(fail.items(), key=lambda x:x[1], reverse=True))
return list(sorted_situ)1, 6, 7, 9, 10, 11, 12, 13, 14, 23, 24, 26이 실패했다...ㅎ
생각해보니까 마지막에 유저들이 다 같은 스테이지에 멈춰 있는데, 해당 스테이지가 N보다는 작지만 첫번째 스테이지가 아닐 경우가 빠졌다. 그러니까 해당 코드에 반례는
N = 3
stages = [2, 2, 2, 2]일때다.
기대값은 [2 ,3, 1]인데
실제 값은 [2, 3]이 나왔다.
문제 풀이 접근법4
from collections import Counter
def solution(N, stages):
fail = {}
s = 0
situ = dict(sorted(dict(Counter(stages)).items()))
player= len(stages)
max_stages = max(list(situ))
if len(situ) > 1:
for i in range(max_stages-(max_stages-N)):
level = i+1
if level in list(situ):
fail[level] = situ[level]/ player
player -= situ[level]
else:
big_stages = [k for k in list(situ) if k > level]
for j in big_stages:
fail[level] = 0 / player
player -= situ[j]
else:
key = list(situ)[0]
value = situ[key]
if key >= N:
for i in range(key):
level = i+1
fail[level] = 0 / player
else:
for i in range(key):
level = i+1
fail[level] = 0 / player
for i in range(key, N):
level = i+1
fail[level] = value / player
fail[key] = value / player
sorted_situ = dict(sorted(fail.items(), key=lambda x:x[1], reverse=True))
return list(sorted_situ)3이랑 똑같이 틀림
아놔 질문하기에서 스테이지에 도달한 사람이 없는 스테이지는 실패율을 0으로 선언한다.
라는 걸 잘 생각해야 한다고 해서 보니까 max_stage가 N보다 작은 경우에 대한 게 없다는 걸 알았다.
문제 풀이 접근법5
유저들이 도달한 스테이지가 전체 스테이지 보다 작은 경우 해당 스테이지들의 실패율을 0으로 정의하게 했다.
from collections import Counter
def solution(N, stages):
fail = {}
s = 0
situ = dict(sorted(dict(Counter(stages)).items()))
player= len(stages)
max_stages = max(list(situ))
if len(situ) > 1:
for i in range(max_stages-(max_stages-N)):
level = i+1
if level in list(situ):
fail[level] = situ[level]/ player
player -= situ[level]
else:
big_stages = [k for k in list(situ) if k > level]
for j in big_stages:
fail[level] = 0 / player
player -= situ[j]
if N> max_stages:
for i in range(max_stages, N):
level = i+1
fail[level] = 0
else:
key = list(situ)[0]
value = situ[key]
if key == N:
for i in range(key):
level = i+1
fail[level] = 0 / player
else:
for i in range(key):
level = i+1
fail[level] = 0 / player
for i in range(key, N):
level = i+1
fail[level] = 0
fail[key] = value / player
sorted_situ = dict(sorted(fail.items(), key=lambda x:x[1], reverse=True))
return list(sorted_situ)1, 10, 11, 12, 14, 26만 틀렸다.
이중에 1, 10, 11, 12는 런타임 에러임...ㅋ
런타임 에러가 난 이유를 드디어 알아냄!! 첫번째 샘플 케이스의 스테이지 5처럼, 깬 사람은 있지만 현재 멈춰 있지 않은 곳에서 내가 플레이어의 수를 빼서 그 다음에 실제 멈춰 있는 스테이지의 실패율을 구할 때, player의 수가 0명이 되어서 그랬던 거였다... ㅎㅎ
문제 풀이 접근법6
실패율만 0으로 정의하고, 사람수는 안빼도록 주석처리 해주었다...ㅎ
from collections import Counter
def solution(N, stages):
fail = {}
s = 0
situ = dict(sorted(dict(Counter(stages)).items()))
player= len(stages)
max_stages = max(list(situ))
if len(situ) > 1:
for i in range(N):
level = i+1
if level in list(situ):
fail[level] = situ[level]/ player
player -= situ[level]
else:
big_stages = [k for k in list(situ) if k > level]
for j in big_stages:
fail[level] = 0 / player
#player -= situ[j]
if N> max_stages:
for i in range(max_stages, N):
level = i+1
fail[level] = 0
else:
key = list(situ)[0]
value = situ[key]
if key == N:
for i in range(key):
level = i+1
fail[level] = 0 / player
else:
for i in range(key):
level = i+1
fail[level] = 0 / player
for i in range(key, N):
level = i+1
fail[level] = 0
fail[key] = value / player
sorted_situ = dict(sorted(fail.items(), key=lambda x:x[1], reverse=True))
return list(sorted_situ)런타임 에러가 나지 않던 14, 26에서만 오류가 났다...
근데 이제 진짜 모르겠음...
너무너무 친절하신 분이 알려주셨다!
유저들이 스테이지를 다 클리어 했을 때(즉, 유저들이 멈춘 스테이지 > N)의 실패율을 정해주지 않아서였다.
문제 풀이 접근법7(성공!!)
from collections import Counter
def solution(N, stages):
fail = {}
situ = dict(sorted(dict(Counter(stages)).items()))
player= len(stages)
max_stages = max(list(situ))
if len(situ) > 1:
for i in range(1, N+1):
level = i
if level in list(situ):
fail[level] = situ[level]/ player
player -= situ[level]
else:
big_stages = [k for k in list(situ) if k > level]
for j in big_stages:
fail[level] = 0 / player
#player -= situ[j]
if N> max_stages:
for i in range(max_stages+1, N+1):
level = i
fail[level] = 0
else:
keys = list(situ)[0]
value = situ[keys]
if keys > N:
for i in range(1, keys):
fail[i] = 0 / player
elif keys == N:
for i in range(1, keys+1):
level = i
fail[level] = 0 / player
fail[keys] = value / player
else:
for i in range(1, keys+1):
level = i
fail[level] = 0 / player
for i in range(keys+1, N+1):
level = i
fail[level] = 0
fail[keys] = value / player
sorted_situ = dict(sorted(fail.items(), key=lambda x:x[1], reverse=True))
return list(sorted_situ)
진짜 거짓말 안하고... 나흘 동안 고민했다...
그래도 구글링 안하고 해결한 내가 너무 대견해요....
내 코드 눈감아 니가 아무리 비효율적이여도 넌 최고의 코드야(겠냐...)
테스트 22 18.41ms 나왔는데 이정도면 평타...인건가?
시간 복잡도 다시 공부하자...^_^
https://yeomss.tistory.com/110
Python 딕셔너리 키/값을 기준으로 정렬하기
HTML 삽입 미리보기할 수 없는 소스 Document 내장 함수 — Python 3.10.0 문서 내장 함수 파이썬 인터프리터에는 항상 사용할 수 있는 많은 함수와 형이 내장되어 있습니다. 여기에서 알파벳 순으로 나
yeomss.tistory.com
https://jsikim1.tistory.com/218
Python List 배열 요소 중복 횟수 구하는 방법 (count duplicates in list)
Python List 배열 요소 중복 횟수 구하는 방법 (count duplicates in list) Python 에서 배열안에 요소들의 중복되는 횟수를 구하는 방법을 알려드리도록 하겠습니다. 목차 - List 안에 모든 요소들의 중복 횟
jsikim1.tistory.com
[알고리즘] Time Complexity (시간 복잡도) - 하나몬
⚡️ Time Complexity (시간 복잡도) Time Complexity (시간 복잡도)를 고려한 효율적인 알고리즘 구현 방법에 대한 고민과 Big-O 표기법을 이용해 시간 복잡도를 나타내는 방법에 대해 알아봅시다. ❗️효
hanamon.kr
'Coding test(Python3) > Programmers' 카테고리의 다른 글
| [level 1] 기사단원의 무기 + 약수 구하기 복습 (0) | 2023.08.25 |
|---|---|
| [level 1] 덧칠하기(진짜 진짜 다시) (0) | 2023.08.25 |
| [level 1] 소수 찾기(에라토스테네스의 체 다시) (0) | 2023.08.09 |
| [level 1] 소수 만들기 (0) | 2023.08.09 |
| [level 1] 모의고사(240708 풀이방법 업데이트) (0) | 2023.08.08 |
