[프로그래머스] 프린트 (python)

문제설명

 문제링크: https://programmers.co.kr/learn/courses/30/lessons/42587

---

Idea

1. 우선 순위마다 id 부여
2. 첫번째 우선순위부터 뒤 우선순위 비교
3. 우선순위 별 아웃풋 정리하여 주어진 location에 해당하는 순서 출력

고려조건

• 첫번째 우선순위보다 높은 우선순위가 있다면 첫번째 우선순위를 가장 마지막으로 변경
• 첫번째 우선순위보다 높은 우선순위가 없다면 첫번째 우선순위를 가장 먼저 출력

---

Solution

def solution(priorities, location):
    priorities = [(i, p) for i, p in enumerate(priorities)]
    outputs = []
    while priorities:
        j = 1
        while j < len(priorities):
            if priorities[0][1] < priorities[j][1]:
                p = priorities.pop(0)
                priorities.append(p)
                j = 0
            j += 1
        outputs.append(priorities.pop(0))
    return [x[0] for x in outputs].index(location)+1

(고유id, 우선순위) 형식으로 우선순위 배열을 초기화합니다. (고유id는 배열 인덱스로 설정)

이후 첫번째 우선순위보다 큰 우선순위가 있는지 여부를 판단합니다.

비교 시 고려해야하는 조건은 총 2가지 입니다.

1. 

priorities[0]에 우선순위 값보다 큰 우선순위가 존재한다면, 문제 정의에 따라 priorities[0] 값을 가장 마지막으로 옮겨야 합니다.

priorities.pop(0), priorities.append()를 이용하여 위 조건을 수행합니다.

2.

priorities[0] 우선순위보다 큰 우선순위가 없다면 priorities[0] 값을 outputs에 넣습니다.

priorities.pop(0), outputs.append()를 이용하여 위 조건을 수행합니다.

위 2가지 경우를 고려하여 만들어낸 outputs는 리스트 안에 (고유id, 우선순위)로 구성되어 있습니다.

location에 해당하는 고유 id를 찾아서 해당 idx에 +1을 하는 방식으로 문제를 풀었습니다.

※ 문제에서는 0번째 인덱스를 1로 해석하기 때문에 코드에서 +1을 해주었습니다.

import timeit
avg_time = 0.
tests = [[[2, 1, 3, 2], 2],
         [[1, 1, 9, 1, 1, 1], 0],
         [[1, 1, 1, 1, 1, 1], 3],
         [[1, 2, 3, 4, 5], 3]]
for t in tests:
    avg_time += timeit.timeit(lambda: solution(*t), number=10000)
print(f'avg_time: {avg_time / len(tests)}')

제가 푼 방식은 대략 0.058초 정도 걸리는 것으로 파악되었습니다.

---

Refactoring 01

def solution(priorities, location):
    queue = [(i, p) for i, p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer

Solution과 동일하게 (고유id, 우선순위) 형식으로 우선순위 배열을 queue로 초기화합니다.

이후 첫번째 우선순위보다 큰 우선순위가 있는지 여부를 판단합니다.

비교 시 고려해야하는 조건은 총 2가지 입니다.

1. 

queue[0]에 우선순위 값보다 큰 우선순위가 존재한다면, 문제 정의에 따라 queue[0] 값을 가장 마지막으로 옮겨야 합니다.

queue.pop(0), queue.append()를 이용하여 위 조건을 수행합니다.

2.

queue[0] 우선순위보다 큰 우선순위가 없다면 answer을 1 증가시키고 해당 우선순위가 찾고자하는 location인지 판단합니다.

※ 문제에서는 location에 해당하는 값이 우선순위 별로 정리했을 때 몇번째로 출력되는지를 묻기 때문에 answer은 가장 큰 우선순위를 찾을때마다 1씩 증가시켜, location에 해당하는 값을 찾았을 때 answer을 반환하는 형식으로 문제를 풀었습니다.

import timeit
avg_time = 0.
tests = [[[2, 1, 3, 2], 2],
         [[1, 1, 9, 1, 1, 1], 0],
         [[1, 1, 1, 1, 1, 1], 3],
         [[1, 2, 3, 4, 5], 3]]
for t in tests:
    avg_time += timeit.timeit(lambda: solution(*t), number=10000)
print(f'avg_time: {avg_time / len(tests)}')

위 방식은 대략 0.045초 정도 걸리는 것으로 파악되었습니다.

---

Refactoring 02

def solution(priorities, location):
    N = len(priorities)
    answer = 0
    cursor = 0
    while True:
        idx = cursor % N
        if max(priorities) == priorities[idx]:
            priorities[idx] = 0
            answer += 1
            if idx == location:
                break
        cursor += 1
    return answer

위 코드는 priorities 최대값이 priorities 어디에 위치하는지 찾아내어 answer을 1 증가시킵니다.

이후 찾아낸 priorities 최대값이 location에 해당하면 answer을 반환합니다.

location에 해당하지 않으면 priorities 최대값을 0으로 변경한 뒤 그 다음 priorities 최대값을 찾습니다.

찾아낸 priorities 최대값이 location에 해당하는지를 반복적으로 탐색합니다.

※ 저는 우선순위를 pop()하여 새로운 배열을 만들었는데 위 코드는 인 메모리에서 값을 변경하는 방식으로 프로세스 처리 속도를 단축했습니다.

import timeit
avg_time = 0.
tests = [[[2, 1, 3, 2], 2],
         [[1, 1, 9, 1, 1, 1], 0],
         [[1, 1, 1, 1, 1, 1], 3],
         [[1, 2, 3, 4, 5], 3]]
for t in tests:
    avg_time += timeit.timeit(lambda: solution(*t), number=10000)
print(f'avg_time: {avg_time / len(tests)}')

위 방식은 대략 0.014초 정도 걸리는 것으로 파악되었습니다.

리펙토링을 통해 기존 0.058초에서 0.014초로 대략 314% 정도 성능이 개선되었습니다.

전체 코드는 아래 깃허브에서 확인 가능합니다.

https://github.com/daewoonglee/programmers/blob/master/lev2/%ED%94%84%EB%A6%B0%ED%84%B0.py