[파이썬]코딩테스트 05 정렬_실패율

문제

프로그래머스

---

실패율

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

• 실패율은 다음과 같이 정의한다.
  • 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

제한사항

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.
• stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
  • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
  • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

입출력 예

N stages result

5	[2, 1, 2, 6, 2, 4, 3, 3]	[3,4,2,1,5]
4	[4,4,4,4,4]	[4,1,2,3]

입출력 예 설명

입출력 예 #1

1번 스테이지에는 총 8명의 사용자가 도전했으며, 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 1번 스테이지의 실패율은 다음과 같다.

• 1 번 스테이지 실패율 : 1/8

2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 2번 스테이지의 실패율은 다음과 같다.

• 2 번 스테이지 실패율 : 3/7

마찬가지로 나머지 스테이지의 실패율은 다음과 같다.

• 3 번 스테이지 실패율 : 2/4
• 4번 스테이지 실패율 : 1/2
• 5번 스테이지 실패율 : 0/1

각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.

• [3,4,2,1,5]

입출력 예 #2

모든 사용자가 마지막 스테이지에 있으므로 4번 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0이다.

• [4,1,2,3] </aside>

---

•  ex ) 3번 스테이지 참가 (n=3)
  • 성공 → 3+1 = 4 (n+1)
  • 실패 → 3 (n)

---

• 문제 읽으면서 대충 해보니 + 약간 규칙이 있다
• → 마치 수열 문제처럼 쭉 해보면서 이런 규칙이 있구나를 알면 된다.
• ex) 1, 3, 5, 7, 9. 11, … → 2씩 커지는 것 같은데?
  • an = a(n-1) + 2, a1 = 1

---

• 문제의 핵심 : 실패율을 정의대로 구해서 내림차순하세요
  • 정렬의 기준 : 실패율
    • def = 스테이지 실패자 수/ 스테이즈 도전자 수
    • case by case
      • 도전자 수 == 0 : 실패율 0 정의
      • 도전자 수 ≠ 0 : 정의대로 계산
  • 정렬의 순서
    • 실패율(내림차순) → 스테이지번호 (오름차순) ⇒ 이름 - 성적 정렬과 유사
    • 정렬을 하기 위한 정보
      • 스테이지번호
      • 실패율
  • 입력 :
    • N : 전체 게임 스테이지 수
    • stages
      • 게임에 참가한 유저들 정보 (리스트)
      • 길이 1 ~ 20000
      • 값 범위 1 ~ N+1
      • 값 의미 : 지금 유저가 하고 있는 게임 스테이지 클리어 아님
  • 출력
    • 실패율 계산 → 정렬 → 스테이지 번호만 + 리스트 제출

---

• 정렬을 위한 자료 정리
  • [(스테이지 번호, 실패율), (스테이지 번호, 실패율), ….]
• 정렬 기준
  • 1기준 : 실패율 → 내림차순
  • 2기준 : 스테이지번호 → 오름차순
  • ⇒ 각기 기준별로 방향이 다름 : +/- 부호로 표현
    • sorted()/ .sort() + key lambda 정렬 기준 표현+ (+/-)
    • [ (1,0.125), (2, 0.42), (3,0.5), (4, 0.5), (5, 0)] --> sort/key/lambda --> [(3,0.5), (4, 0.5), (2, 0.42) ,(1,0.125) , (5, 0)]
• 참고 ) 정렬에 대한 대상이 오로지 리스트만은 아님
  • ex) dict로 해당하는 stage/실패율 정리를 하고자 함
    -> key: 스테이지 번호, val : 그 스테이지 실패율

    t = {1:1/8, 2:3/7, 3:2/4, 4:1/2, 5:0}
    ​

    

    
    

    

    
    

    b=[]
    for i in temp:
    	b.append(i[0])
    	b
    ​

---

• 실패자수 : 전체 참가자 정보 대상으로 필터링 +카운팅
• m1) 리스트의 잡다한 기능 : count()

  a = [2, 1, 2, 6, 2, 4, 3, 3]
  a
  ​

• 2번 스테이지 실패자 수

  a.count(2)
  ​

• m2) 필터링 +카운팅 : LC

  cnt = 0
  a = [2, 1, 2, 6, 2, 4, 3, 3]
  for i in a:
      if i == 2:
          cnt += 1
  print(cnt)
  ​

• m3) 꾸역 돌려가며서…for + if
• +참고) dict에 새로운 값들을 추가하는 방법
  • ⇒ 신규 등록 vs 기등록에 대한 값을 갱신

    a_dict = {}
    a.dict
    ​

    a_dict["a"] = 100 # key 중심 신규 등록
    a_dict
    
    a_dict["a"] = 200 # 기 key 중심 신규 등록
    a_dict
    
    a_dict["b"] = 99
    a_dict
    ​

---

전체 코드 작성

def solution(N,stages):
	answer = []
	###
	#1) 필요한 정보 세팅
	#1-1) 정렬을 위한 기본정보 처리 : Dict -> k: 스테이지번호, v: 실패율
	fail_dict = {}
	#1-2) 최초 도전자 수에 대한 정보 : 각 스테이지 돌아가면서 참가자 활용
	num_people = len(stage)

#2) 큰 틀 : 최종 stage 번호 -> 각 스테이지를 롤링 ! 1~N -> range
for i_stage in range(1, N+1):	#1,2,3, ..., N
	#i번째 스테이지에서 할 일
	#2-1) i_s 실패자수 : 카운팅 + 필터링 -> .count
	fail_num = stages.count(i_stage)
	#2-2) 실패율 계산...case by case
	if num_people > 0 : #참가자가 1명 이상 -> 계산해야함
		fail_dict[i_stage] = fail_num / num_people
		#list로 하려면
		#fail_list.append([i_stage, fail_num/num_people])
	else: #참가자가 0명인 경우 -> 정의 = 0
		fail_dict[i_stage] = 0
		#list로 하려면
		#fail_list.append([i_stage, 0])
		
	#2-3) 다음 라운드에 진출할 참가자 정보 : 갱신
	num_people -= fail_num #num_people = numpeople - fail_num
	# --> {1:1/8, 2:3/7, 3:2/4, 4:1/2, 5:0}
  # --> [[1,1/8], [2, 3/7], [3, 2/4], [4, 1/2], [5,0] ]
  # 번외 [ 1/8, 3/7, 2/4, 1/2, 0] ===> enumerate(a) --> sort
	
	#3) 출력을 위한 정렬 & 정리
	# --> 정렬 1기준: 실패율 & 내림차순
	# --> 정렬 2기준: 번호 & 오름차순
	# fail_dict.items() : {1:1/8, 2:3/7, 3:2/4, 4:1/2, 5:0}
	# --> [[1,1/8], [2, 3/7], [3, 2/4], [4, 1/2], [5,0] ]
	fail_list = sorted(fail_dict.items(), key=lambda x:(-x[1],x[0]))
	#--> [[3, 2/4], [4, 1/2], [2, 3/7],[1,1/8],  [5,0] ]
	
	#4) 최종본 : 스테이지번호 + 리스트화
	answer = [fail_info[0]  for fail_info in fail_list]
    # [3,4,2,1,5]
    return answer

---

• 리스트로도 해보고, dict로도 해보자
• 단, 이제는 이런 심플한 문제 보다는 복잡한 경우로 제시함
• 직접 이런 것들을 해보면서 규칙/관계들 찾아보자