프린터(programmers 문제) python 풀이

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

입력으로 각 프린트 순서의 우선 순위가 들어가 있는 배열 priorities와 우리가 구하려는 프린트의 위치가 적혀있는 location이 인풋으로 들어왔을 때, location에 해당하는 프린트가 몇 번째로 인쇄가 되는지 구하는 문제이다.

다만, 아래와 같은 3가지 방식으로 인쇄가 진행이 된다.

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

내 풀이

1. 첫 번째

난 문제를 보고 가장 큰 값을 기준으로 왼쪽의 블록들을 전부 오른쪽의 끝에 붙이고 가장 큰 값을 제거하는 과정을 반복하면 되겠다고 판단했다.

def solution(priorities, location):
    answer = 1

    length = len(priorities)

    while 1:
        idx_max_priorities = priorities.index(max(priorities))
        
        ## 옮기기
        left_max = priorities[:idx_max_priorities]
        
        # 가장 큰 값 왼쪽에 있는 경우
        if location < idx_max_priorities:
            location += (length - len(left_max))
        # 가장 큰 값 오른쪽에 있는 경우
        elif location >= idx_max_priorities:
            location -= len(left_max)
            
        # 왼쪽 항목 제거 후, 왼쪽 배열을 오른쪽에 붙임
        del priorities[:idx_max_priorities]
        priorities += left_max
        
        if location == 0:
            break
        else:
            location -= 1
            del priorities[0]

        answer += 1

    return answer

따라서 위의 코드와 같이 진행을 했는데,

1. 배열 안에 있는 가장 큰 값을 확인한다.
2. 가장 큰 값을 기준으로 왼쪽에 위치한 값들을 오른쪽으로 옮긴다. 이때, location 값도 변경을 진행해준다.
3. 1,2번 과정을 거친 후에 location이 0번이라면 break를 진행해주고, 0번이 아니라면 현재 가장 앞에 있는 프린트를 인쇄해주고(제거해주고) location값에서 -1를 해준다.

다시 한번 설명을 하자면 위의 과정을 while문으로 감싸 진행했다.

결과

테스트 케이스는 모두 통과를 했지만, 실제 결과는 많이 처참했다...

다른 사람 풀이

다른 사람은 어떤식으로 해결했는지 살펴보았다.

def solution(priorities, location):
    answer = 0
    m = max(priorities)

    while True:
        v = priorities.pop(0)
        if m == v:
            answer += 1
            if location == 0:
                break
            else:
                location -= 1
            m = max(priorities)
        
        else:
            priorities.append(v)
            if location == 0:
                location = len(priorities) - 1
            else:
                location -= 1

    return answer

내가 생각한 알고리즘보다 간단했다...
나의 경우 max값을 기준으로 왼쪽의 블록을 오른쪽으로 옮겨서 푸는 방식을 사용했는데 내가 가져온 풀이의 경우 그냥 priorities의 맨 앞에 있는 값이 max값과 동일하면 인쇄를 해서 answer에 +1을 해주고, 그렇지 않는 경우는 priorities의 맨 뒤로 값을 보낸다. 이 작업을 반복하다가 location이 0이되면 break를 걸어 리턴을 해준다.

결과