알고리즘/프로그래머스

[프로그래머스] #.42587 - 프린터

프린터

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

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

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

제한 조건

  • 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
  • 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
  • location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

입출력 예

priorities location return
[2,1,3,2] 2 1
[1,1,9,1,1,1] 0 5

문제 해결하기

Go 언어를 사용할 수 있는 Level 2 문제 중 첫 번째 문제다. 확실히 Level 1 문제와는 결이 좀 다른 느낌이다. 이 문제를 해결하기 위해서는 한 번 쯤은 종이에 풀이과정을 적는 것이 좋다.

규칙 파악하기

문제의 예시만으로는 문제를 바로 이해하기 어려우니 다른 예제를 사용해보기로 하자. [2,2,2,1,3,4] 라는 배열에 3 이라는 location 을 주면 6 이 반환되어야 하는데, 그 순서를 보면 다음과 같다. 여기서 location 3 에 해당하는 값은 1 이다. 여러 가지 방법이 있겠지만 나는 타겟 원소를 추적하는 방법을 떠올려냈다.

target = 3 (location)

[2,2,2,1,3,4] 에서 제일 처음 원소인 2 보다 우선순위가 높은 값인 3, 4 가 있으니 2를 맨 끝으로.
[2,2,1,3,4,2], target = 2
[2,1,3,4,2,2], target = 1
[1,3,4,2,2,2], target = 0
[3,4,2,2,2,1], target = 5
[4,2,2,2,1,3], target = 4

[4,2,2,2,1,3] 에서 4 보다 높은 우선 순위가 없으므로 큐에서 꺼내자.

[2,2,2,1,3], target = 3

[2,2,2,1,3] 에서 2 보다 높은 우선 순위가 있으므로 맨 끝으로.
[2,2,1,3,2], target = 2
[2,1,3,2,2], target = 1
[1,3,2,2,2], target = 0
[3,2,2,2,1], target = 4

[3,2,2,2,1] 에서 3 보다 높은 우선 순위가 없으므로 큐에서 꺼내자.
[2,2,2,1], target = 3
[2,2,1], target = 2
[2,1], target = 1
[1], target = 0

위와 같은 규칙에서 다음과 같은 사실을 알 수 있다.

1. target 은 큐에서 값을 뺄 때마다 -1 씩 감소한다.
2. target 은 큐의 맨 앞의 원소를 맨 뒤로 넘길 때마다 -1 씩 감소한다.
3. target 이 0 인 경우 큐의 맨 뒤의 인덱스로 이동한다.

변수 target 이 무엇을 위해 존재하는가, 문제에서 묻고 있는 것은 우리가 타겟으로 지정한 것이 몇 번째로 큐에서 빠져나갈 것에 대한 질문이다. 이 말은 큐에서 원소를 제외할 때마다 answer 를 증가시켜주면 된다는 이야기가 된다.

target = 3 (location), answer = 0

...
[4,2,2,2,1,3] 에서 4 보다 높은 우선 순위가 없으므로 큐에서 꺼내자.

[2,2,2,1,3], target = 3, answer = 1

...
[3,2,2,2,1] 에서 3 보다 높은 우선 순위가 없으므로 큐에서 꺼내자.

[2,2,2,1], target = 3, answer = 2
[2,2,1], target = 2, answer = 3
[2,1], target = 1, answer = 4
[1], target = 0, answer = 5

여기서 [1] 에서 1 이 큐에서 빠져나가는 것이 문제에서 말하는 '인쇄' 이므로 answer = 6 으로 처리해야 한다. 따라서 값을 반환할 때는 answer + 1 이 되어야 한다.

코드로 표현하기

위와 같은 규칙을 적용하여 코드로 표현하면 다음과 같다. 문제에서 이야기한 1, 2, 3 번에 대한 사항과 우리가 규칙 알아내기 부분에서 찾아본 규칙을 처리하는 부분이 나와있다. 사실상 코드를 작성하는 시간보다 문제를 이해하고 규칙을 찾아내는 시간이 더 걸리는 것이 일반적이다.

func solution(priorities []int, location int) int {
	var answer int

	queue := make([]int, len(priorities))
	copy(queue, priorities)

	target := location

Loop:
	for {
		for _, priority := range queue {
			if priority > queue[0] {
				// 큐의 맨 끝으로 보낸다.
				queue = append(queue, queue[0])
				queue = queue[1:]

				// 규칙에 의한 target 처리
				switch target {
				case 0:
					target = len(queue) - 1
				default:
					target--
				}

				// 이미 처리를 했다면 더 이상 진행할 필요가 없으므로 아래의 코드는 생략.
				continue Loop
			}
		}
		// 여기서 target 이 0 이 된다는 것은 큐에서 target 을 제외하고 모두 빠져나갔다는 의미다.
		if target == 0 {
			break Loop
		}
		// 큐에서 원소를 하나 제거하고 target, answer 처리.
		queue = queue[1:]
		target, answer = target-1, answer+1
	}

	return answer + 1
}

func TestSolution(t *testing.T) {
	cases := []struct {
		priorities []int
		location   int
		expect     int
	}{
		{[]int{2, 1, 3, 2}, 2, 1},
		{[]int{1, 1, 9, 1, 1, 1}, 0, 5},
		{[]int{1, 2, 3, 4, 5, 6, 7}, 4, 3},
		{[]int{1, 1, 1, 1}, 3, 4},
		{[]int{1, 1, 1, 2}, 1, 3},
		{[]int{2, 2, 2, 1, 3, 4}, 3, 6},
	}
	for _, c := range cases {
		if r := solution(c.priorities, c.location); r != c.expect {
			t.Errorf("priorities %#v; got %#v, want %#v", c.priorities, r, c.expect)
		}
	}
}

더 읽을거리

github.com/pronist/al.go/tree/main/programmers/_42587

programmers.co.kr/learn/courses/30/lessons/42587