실패율, 문자열 압축

김성수·2020년 4월 16일

알고리즘

목록 보기

3/5

2020-04-14 알고리즘 문제풀이 스터디

학습시간: 18:30 ~ 21:00. 약 2시간 30분
풀이한 문제 수: 1
문제풀이 사이트: 프로그래머스
(출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges)
난이도: Level 1

문제 정의

문제 풀이

코드

from queue import PriorityQueue

def solution(N, stages):
    que = PriorityQueue()

	hash_stages = {}
    hash_rate = {}

    for i in range(1, N+2):
        hash_stages[i] = 0

    for i in stages:
        hash_stages[i] += 1

    for i in range(1, N+1):
        hash_rate[i] = 0
        clears = hash_stages[i]
        
        if clears == 0:
            que.put((-0, i))
            continue
            
        if i == 1:
            clears = len(stages)
            hash_rate[i] = hash_stages[i] / float(clears)
        else:
            for j in range(i+1, N+2):
                clears += hash_stages[j]
            hash_rate[i] = hash_stages[i] / float(clears)
         
        que.put((-hash_rate[i], i))

    result = []
    while not que.empty():
        result.append(que.get()[1])

	return result

코드 with 주석

from queue import PriorityQueue

def solution(N, stages):

	# 실패율과 스테이지를 담는 우선순위 큐 인스턴스
    que = PriorityQueue()

    # 스테이지 별 머물고 있는 유저의 수를 담는 dictionary
    hash_stages = {}
    
    # 스테이지 별 실패율을 담는 dictionary
    hash_rate = {}

	# hash_stages 초기화
    for i in range(1, N+2):
        hash_stages[i] = 0

    # 해당 스테이지에 머물고 있는 유저에 따라 +1 한다.
    for i in stages:
        hash_stages[i] += 1

	# 스테이지 순회 (1 ~ N)
    for i in range(1, N+1):
 		실패율 dictionary 초기화
        hash_rate[i] = 0
        
        # 스테이지를 클리어 했거나 머물고 있는 유저들. 
        # 먼저 현재 도전 중인 유저들의 수를 넣는다.
        # 실패율 = 머물고 있는 유저의 수 / clears
        clears = hash_stages[i]
        
        # 현재 스테이지에 머물고 있는 유저가 없으면 queue에 넣고 for문 넘김.
        # 만약 clears가 0이면 division 에러가 난다.
        if clears == 0:
            que.put((-0, i))
            continue
            
        # 1번 스테이지의 경우
        # 실패율 = 머물고 있는 유저의 수 / 전체 유저 수
        if i == 1:
            clears = len(stages)
            hash_rate[i] = hash_stages[i] / float(clears)

		
            # i번 째 스테이지별 실패율 = 머물고 있는 유저의 수 + 그 위 스테이지에 있는 사람들 
        else:
        	# 현재보다 위 스테이지에 있는 사람들을 구한다.
            for j in range(i+1, N+2):
                clears += hash_stages[j]
                
            hash_rate[i] = hash_stages[i] / float(clears)
         
        # 실패율과 스테이지를 queue에 담는다.
        # que.put((요소1, 요소2))
        # - 는 내림차순으로 넣음.
        que.put((-hash_rate[i], i))

    result = []

    while not que.empty():
        result.append(que.get()[1])

    # 담기 정렬 (퀵 정렬?)
    # 비율 순으로 정렬
    # 비율이 똑같을 경우에는 스테이지 번호 순으로 정렬해야 한다. 

    answer = result
    return answer

후기

풀이 방식이 너무 복잡했다.
해쉬 맵으로 접근하다 보니 키 에러를 자주 냈다.
정렬에서 헤멨다. 아주 많이.
다른 사람의 풀이를 보니 굉장히 간단하게 접근할 수 있는 부분들이 많았다.
list.count() 를 몰랐다.
그리고 sorted 함수를 몰랐다.
알고리즘 배경지식도 얕았고, 파이썬 언어 자체에 대한 이해도도 낮았다.
나만 풀이에 이렇게 주석을 많이 써?!

추후 공부

우선순위 큐
lambda
한 줄 for문
list.sorted

문제 정의

문제 풀이

코드

def compress(s, unit):
    comps = s[:unit]
    compressed = ''

    unitlen = len(s) // unit

    for i in range(0, unitlen):
        front = s[i*unit:(i+1)*unit]
        back = s[(i+1)*unit:(i+2)*unit]
        if front == back:
            comps += back
        elif front != back:
            if len(comps) // unit >= 2:
                compressed += str(len(comps) // unit) + comps[:unit]
            else:
                compressed += comps
            comps = back
    compressed += s[unit * unitlen:]
    # print("unit:",unit, "last: ", s[unit * unitlen:])
    return compressed


def solution(s):

    lens = len(s)
    compressedMax = s
    unit = 0

    if len(s) <= 1:
        return len(s)

    possibleUnit = len(s) // 2
    print(possibleUnit)

    for i in range(1, possibleUnit+1):
        if lens >= i * 2:
            unit = i
            compressed = compress(s, unit)
            if len(compressed) < len(compressedMax):
                compressedMax = compressed


    answer = len(compressedMax)
    return answer

코드 with 주석

def compress(s, unit):
    comps = s[:unit]
    compressed = ''

    unitlen = len(s) // unit

    for i in range(0, unitlen):
        front = s[i*unit:(i+1)*unit]
        back = s[(i+1)*unit:(i+2)*unit]
        if front == back:
            comps += back
        elif front != back:
            # 압축할 수 있는 문자열들이 있으면
            if len(comps) // unit >= 2:
                compressed += str(len(comps) // unit) + comps[:unit]
            # 없으면 그냥 압축 하지 않고
            else:
                compressed += comps
            comps = back
    # 압축단위에 끼지 못하고 남은 문자열 붙임
    compressed += s[unit * unitlen:]
    # print("unit:",unit, "last: ", s[unit * unitlen:])
    return compressed


def solution(s):

    # 문자열 개수
    lens = len(s)
    # 압축된 문자열
    compressedMax = s
    unit = 0

    if len(s) <= 1:
        return len(s)

    # 가능한 단위도 구해야 했어..
    possibleUnit = len(s) // 2
    print(possibleUnit)

    for i in range(1, possibleUnit+1):
        if lens >= i * 2:
            unit = i
            compressed = compress(s, unit)
            # 해당 단위로 압축한 길이가 최대 압축 길이보다 짧으면
            if len(compressed) < len(compressedMax):
                compressedMax = compressed


    answer = len(compressedMax)
    return answer