오름차순 배열과 내림차순 배열을 동시에 적용하는 방법?

1. 문제

 

https://programmers.co.kr/learn/courses/30/lessons/42889

코딩테스트 연습 - 실패율

 

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다.

 

그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다.

 

원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

 

이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다.

 

역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다.

 

오렐리를 위해 실패율을 구하는 코드를 완성하세요.

 

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

 

전체 스테이지의 수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때,

 

실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return하도록 solution 함수를 완성하세요

 

 

 

2. 제한사항

 

스테이지의 개수 N은 1이상 500이하의 자연수

 

stages의 길이는 1이상 200000이하

 

stages에는 1이상 N+1이하의 자연수가 담겨있다

 

각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타냄

 

단, N+1은 마지막 스테이지(N번째 스테이지)까지 클리어 한 사용자

 

만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 함

 

스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의

 

 

3. 입출력 예시

 

그림1. 입출력 예시

 

4. 나의 풀이

 

def solution(N, stages):
    
    answer = []
    
    answer_list = []
    
    stages.sort()
    
    for stage in range(1,N+1):
        
        total = len(stages)
        
        if len(stages) == 0:
            
            while len(answer_list) != N:
                
                answer_list.append(0.0)
            
            break

 

stages.sort()를 통해 가장 낮은 스테이지에 도달한 사람부터 가장 높은 스테이지에 도달한 사람까지 순서대로 정렬시킨다

 

다음 1단계부터 N단계까지 for문을 이용해 스테이지 하나씩 실패율을 구할건데

 

total = len(stages)를 이용해 현재 stage의 도전자 수를 구하고

 

else:
    
    fail = 0
    
    while 1:
        
        if len(stages) == 0:
            break
            
        else:
            
            if stage < stages[0]:
                
                break
                
            else:
                if stage < stages[0]:
                    
                    break
                else:
                    stages.pop(0)
                    fail += 1
                    
    answer_list.append(fail/total)

 

실패한 사람의 수를 구하는데… stages가 정렬되어 있기 때문에 stages[0]과 현재 stage를 비교하여…

 

stages[0]이 stage보다 더 크면 현재 모든 사람들이 현재 stage는 전부 클리어했다는 말

 

stages[0]이 stage보다 작거나 같으면

 

stages[0] 사람은 현재 stage를 클리어하지 못했으므로 stages.pop(0)를 해서 0번째 원소는 제거하고 실패한 사람의 수에 1을 더해준다

 

물론 모든 사람이 현재 stage에 실패하면 stages의 길이가 언젠가는 0이 되므로 len(stages)가 0이 되면 탈출하도록 조건도 추가해준다

 

다음 반복문을 탈출하면 현재 stage의 실패율을 answer_list에 차례대로 append해준다..

 

stages.pop(0)를 통해서 stage가 올라갈수록 도달하지 못한사람들은 차례대로 제거될거임

 

이러다가 어느순간부터는 total값이 0이 되는 순간이 있을거임…

 

그러니까 도달하지 못한 사람들이 제거되면서 stages에 어떠한 원소도 남아있지 않은 경우

 

스테이지에 도달한 사람이 없으면 해당 스테이지의 실패율은 0으로 정의하므로.,...

 

answer_list의 길이는 N이 되어야하기에 그렇게 될때까지 0을 반복해서 집어넣으면 된다

 

def solution(N, stages):
    
    answer = []
    
    answer_list = []
    
    stages.sort()
    
    for stage in range(1,N+1):
        
        total = len(stages)
        
        if len(stages) == 0:
            
            while len(answer_list) != N:
                
                answer_list.append(0.0)
            
            break

 

이제 answer를 구성해야하는데

 

for _ in range(N):
    
    target = answer_list.index(max(answer_list))
    
    answer.append(target+1)
    
    answer_list[target] = -1
    
return answer

 

answer_list의 길이는 N이니까 N까지 for문을 돌건데…

 

여기서도 섬세한 점이 range(len(answer_list))보단 range(N)이 나을것 같은게 len때문에 시간 소요될것 같음..

 

answer_list에서 max값의 index를 찾은 뒤에 index에 1을 더하면 현재 max의 stage와 같다는 점을 이용

 

예를 들어 실패율의 max index가 0이면 실패율이 가장 큰 stage는 1단계라는 의미

 

max값을 answer_list에서 제거해버리면 index가 꼬여서 실패율의 최솟값이 0이라는 점을 이용해서 제거하는 대신에 -1로 대체함

 

실패율이 같으면 낮은 stage 번호가 먼저 오도록 해야하는데…

 

.index()함수가 왼쪽부터 먼저 index를 구해주므로 이러한 점도 고려되어 있다

 

 

 

5. 다른 풀이

 

시간 좀 나름대로 줄였다고 생각했는데.. 내 풀이가 시간이 상당히 걸리는거였네

 

def solution(N, stages):
    
    from collections import Counter
    
    fail_rate = {}
    
    total = len(stages)
    
    count_dict = Counter(stages)
    
    for stage in range(1,N+1):
        
        if total != 0:
            
            fail = count_dict[stage]
            
            fail_rate[stage] = fail / total
            
            total -= fail
            
        else:
        
            fail_rate[stage] = 0
            
    return sorted(fail_rate.keys(), key = lambda x : fail_rate[x], reverse=True)

처음에 total = len(stages)로 stage1 도전자 수와 count_dict=Counter(stages)를 이용해 각 stage에 도달한 사람 수를 만들어 놓는다

 

특히 count_dict가 가지는 의미는 각 stage를 클리어하지 못한 사람 수가 되는데 잘 생각해보면

 

stage1에 도달한 사람 수는 stage1을 클리어하지 못한 사람 수

 

stage2에 도달한 사람 수는 stage2를 클리어하지 못한 사람 수…

 

….

 

stage 1부터 N까지 for문을 이용해 하나씩 검사하는데…

 

stage1을 클리어하지 못한 사람 수는… 현재 stage1에 있는 사람 수니까 count_dict[1]을 fail에 넣으면 될거임

 

stage2,3,...에 도달한 사람들은 stage1을 클리어했거든

 

실패율을 구해서 fail_rate 사전에 넣고

 

그 다음에 total -= fail을 이용해 stage2부터 도전한 사람 수를 구해놓는거임

 

--------------------------------------------------------------------------------------------------------------------

다시 stage=2가 되면 fail=count_dict[2]는 stage2에 실패한 사람 수가 됨

 

애초에 stage=1에 있는 사람은 stage2에 도전조차 한게 아니니까 여기에 count되면 안됨 이걸 생각할 수 있느냐가 포인트네

 

다음에 실패율을 구해 사전에 넣고 total -= fail로 stage3에 도전한 사람 수를 구해놓는 거임

 

----------------------------------------------------------------------------------------------------------------------

 

이런식으로 하면 어떤 stage에는 도전한 사람 수가 존재하지 않을텐데 거기부터는 fail_rate[stage]=0으로 실패율을 0을 넣는거임

 

다음에 정렬을 하는게 대박이네

 

sorted(fail_rate.keys())를 통해서 fail_rate.keys()를 정렬을 하는데…

 

fail_rate.keys()는 stage번호임

 

key = lambda x: fail_rate[x]를 하면 fail_rate[x]는 실패율이잖아.. 실패율을 기준으로 fail_rate.keys() <stage 번호>를 정렬을 함

 

그런데 reverse=True로 실패율 내림차순으로 정렬을 함

 

근데 이제 파이썬 3.7부터는 dictionary의 key는 들어간 순서대로 생성이 된다는 점을 이용하면...낮은 스테이지 번호가 먼저 올수 있게 된다는거..

 

시간을 줄이는 요소로 total -= fail이나 Counter(stages)로 for문 밖에서 미리 집계해놓는거… 이런 섬세한 차이가 당락을 가른다

 

 

6. 되돌아보기

 

시간을 어떻게 줄이느냐가 관건이었는데… 생각보다 잘 했어

 

stages를 정렬한 다음에 pop(0)를 이용해 stages를 줄여나가는게 상당히 소름돋았다.?

 

pop을 이용해 원소를 제거해나가는 이런 기술은 많이 쓰이는 것 같다

 

이 문제의 또 다른 핵심은 실패율의 크기 순서대로 index를 배열하는데 실패율 값이 같으면 index가 낮은 순서가 앞에 오게 배열을 해야함..

 

(실패율,stage) 튜플을 리스트에 넣어서 내림차순으로 배열하면 실패율 크기 순서대로 배열을 하나…

 

문제는 실패율이 같으면 stage로 배열을 하게 되는데

 

내림차순으로 배열하느라 stage도 내림차순으로 배열해서 index가 낮은 순서가 앞에 오게 하는데 상당히 까다롭다

 

근데 이런 과정을

 

for _ in range(N):
    
    target = answer_list.index(max(answer_list))
    
    answer.append(target+1)
    
    answer_list[target] = -1
    
return answer

이런 식으로 처리했다는 점도 스킬로 기억하면 좋을 것 같다… 시간을 엄청 잡아먹는건 아닌듯..? 잡아먹을것 같기는 한디.,..?

 

시간 별로 안잡아먹는 줄 알았는데 더 멋진 풀이가 있었음

 

dictionary를 이용해서 낮은 번호부터 넣은 key를 정렬하는데 value 기준으로 내림차순 정렬하면 더 빨리 가능

 

            
    return sorted(fail_rate.keys(), key = lambda x : fail_rate[x], reverse=True)

 

if만 사용할건지 if와 else를 사용할건지.. 상당히 큰 차이가 있다

 

if만 사용하면 그 뒤의 문장도 그대로 수행하므로 그만큼 시간이 소요되는데 if~else를 사용하면 if나 else 둘 중 하나만 수행하니까 시간을 절약할 수 있다는 점

 

 for stage in range(1,N+1):
        
        total = len(stages)
        
        if len(stages) == 0:
            
            while len(answer_list) != N:
                
                answer_list.append(0.0)
            
            break

        else:

            fail = 0

            while 1:

                if len(stages) == 0:
                    break

                else:

                    if stage < stages[0]:

                        break

                    else:
                        if stage < stages[0]:

                            break
                        else:
                            stages.pop(0)
                            fail += 1

            answer_list.append(fail/total)

 

논리적으로 len(stage)가 0이 되는 순간부터는 answer_list에 0만 넣으면 되는데

 

만약 if else를 안쓰고 if만 쓴다면?

 

 

 for stage in range(1,N+1):
        
        total = len(stages)
        
        if len(stages) == 0:
            
            while len(answer_list) != N:
                
                answer_list.append(0.0)
            
            #break

        #else:

        fail = 0

        while 1:

            if len(stages) == 0:
                break

            else:

                if stage < stages[0]:

                    break

                else:
                    if stage < stages[0]:

                        break
                    else:
                        stages.pop(0)
                        fail += 1

        answer_list.append(fail/total)

 

 

answer_list에 0을 넣어서 answer_list의 길이가 N이 되면 for문을 탈출해야하는데… 

 

탈출하지 못하고 fail=0부터 answer_list.append(fail/total)을 또 수행해야해서 그만큼 시간이 소요됨

 

이 차이가 시간초과냐 시간초과가 아니냐를 또 만든다..

 

그 외에 다른 풀이에서 total = len(stages)로 미리 구해놓은 다음에 for문 안에서는 len()을 쓰지 않고 total -= fail로 시간을 줄이고

 

for문 안에서 stages.count(stage)가 아니라 Counter(stages)로 미리 집계해놓는다면? 시간을 더욱 줄일수 있다는거