사용 언어: python 3.7.4

❓ Problem

문제 설명

프로그래머스 프린터

🚩 Solution

1. 접근법

자료구조 큐를 떠올렸다.

로케이션은 실시간으로 바뀐다.

로케이션으로 정한 원소가 제자리에 배치됐을 때, 그 위치를 리턴하고 종료한다.

[구체적 과정]

1. (반복 시작) 큐의 첫 번째 원소 p(리스트의 맨 왼쪽)를 꺼낸다.
2. p와 대기목록에 있는 값의 대소를 비교한다.
3. 대기 목록에 p보다 더 큰 값이 있다면
   1. p를 큐의 맨 뒤로 보낸다.
   2. 로케이션이 0이였으면, 로케이션 값을 len-1로 변경한다.
   3. 로케이션이 0이 아니였으면, 로케이션 값을 -1한다.
   4. (반복 시작)으로 돌아가서 다시 첫 번째 원소를 꺼내는 작업부터 반복한다.
4. 대기 목록에 p보다 더 큰 값이 없다면
   1. p를 큐에서 빼내고, 완성된 인쇄 순서를 저장하는 리스트 arr에 삽입한다.
   2. 로케이션 값이 0이였으면, arr의 길이(정답)를 리턴하고 종료한다.
   3. 로케이션 값이 0이 아니였으면, 로케이션 값을 -1한다.
   4. (반복 시작)으로 돌아가서 다시 첫 번째 원소를 꺼내는 작업부터 반복한다.

아래는 코드를 짜기 전, 위 과정을 먼저 수도 코드로 짠 것이다.

#반복
    (1)처음 거를 뽑는다
    대기열 확인
    if 더 큰 값이 있으면
        현재값을 가장 뒤로 보냄
        if 로케이션이 0이였으면 len-1로 변경
        else 로케이션 -1

    else 더 큰 값이 없으면

        pop,완성 리스트에 삽입
        if 로케이션이 0이였으면
            완성된 리스트 길이를 리턴하고 종료
        else
            로케이션 -1
            다시 (1)로 돌아감

2. 코드

from collections import deque
def solution(priorities, location):
    arr = []
    queue = deque(priorities)

    while True:
        p = queue[0]
        big = 0 # big 초기화
        for i in range(1, len(queue)):
            if(p < queue[i]):
                big = 1
                break

        if big == 1:
            queue.append(p)
            queue.popleft()
            if location == 0:
                location = len(queue) - 1
            else:
                location -= 1
            continue

        else:
            arr.append(queue.popleft())
            if location == 0:
                answer = len(arr)
                return answer
            else:
                location -= 1
                continue

3. 결과

채점 결과

correct

시간 복잡도 분석

📕 피드백

1. 검색한 내용

1. 큐, 덱을 쓰려면 collections 모듈을 import한다. from collections import deque
2. 파이썬 덱(deque) 사용법: https://excelsior-cjh.tistory.com/96

2. 실수

big 초기화를 안해서 무한 루프에 빠졌었다.

3. 발전 방향

1. for문 대신 any()로 더 큰 값이 있는지 조사할 수 있다.

any()는 하나라도 True가 있으면 True를 반환한다.(반대로 모두 True여야 True를 반환하는 all()이 있다.)

2. 튜플끼리 대소비교할 수 있다. 대소비교는 첫 번째 요소부터 한다.

3. arr에 따로 저장하지 않고, 위치가 정해지면 answer+1할 수도 있다.

나중에 arr길이를 리턴하는 것보다 anwer를 1씩 더하는게 메모리 관리에서 효율적이다.

아래는 다른 사람의 풀이를 print하며 어떻게 돌아가는지 확인한 코드이다.

def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    print("초기 큐:",queue)

    answer = 0

    while True:
        print("<while 내부>")
        cur = queue.pop(0)
        print("cur =",cur)
        print("팝한 후 큐 =", queue)

        if any(cur[1] < q[1] for q in queue):
            print("큰 값 있음, 맨 뒤로 보내기")
            queue.append(cur)
        else:
            print("큰 값 없음, 위치 확정")
            answer += 1
            print("answer = ", answer)
            if cur[0] == location:
                print("location의 위치. 정답")
                return answer
        print()

print(solution([1,1,9,1,1,1],0))

4. 느낀점

25~30분 동안 아이디어를 생각했다.

공책에 문제를 푸는 과정을 펜으로 적으면서 어떻게 풀면 좋을지 생각해나갔다. 수도 코드를 짠 뒤, 내 수도 코드가 원하는 답을 얻어내는지 과정을 따라가며 검토를 끝내고 코드 짜기로 넘어갔다.

코드로 옮기는 시간은 30분 넘어 걸렸다.

일단, 파이썬에서 큐랑 덱을 어떻게 사용하는지 몰라서 import부터 검색했다. 그리고 C++로 큐를 쓸 때와 pop()의 동작 과정이 다르다고 어디서 들어본 바가 있어서 push, pop의 리턴값이나, 어느 위치의 값에 접근하는지 등 알아보는 시간도 필요했다.

미리 공부해놓고 풀면 좋았을텐데, 하는 생각이 들었다.

프로그래머스 레벨2 문제를 빨리 다 풀어버리고 싶다.

어떻게 하면 아이디어를 더 빨리 떠올릴 수 있을까?

일단 문제를 많이 풀면서 다른 사람 코드를 열심히 분석해봐야겠다.