[알고리즘][Swift] #1. 프린터

안녕하세요! caution 입니다. '-'

알고리즘 문제 풀이 첫 포스팅이네요! 요새 한 주에 한 두 개씩 알고리즘 문제를 풀어보고 있어요.

알고리즘의 알자도 몰라서 일주일에 두 개 푸는 게 한계입니다!! 어렵게 풀어본 문제를 소개하면서 정리하려고 해요 :)

제 풀이가 정답은 아닙니다! 친절한 피드백은 언제나 감사드려요! '-')!!

---

알고리즘 문제는 주로 카카오 프로그래머스에서 풀어보고 있습니다! 

다양한 언어를 지원하고, 무엇보다 한국어니까요!!! 해석 안 해도 된다 만세!!!!

아무튼, 시작해볼까요!

(포스팅은 의식의 흐름과 제 시행착오를 기준으로 작성됩니다. 답변이 필요하신 분은 스크롤을 많이 내리셔야 할 겁니다!!)

오늘의 문제는 Level 2 프린터 입니다.

문제 설명

---

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

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로 표현합니다.

요약하자면, 문서 대기열에서 가장 중요도가 높은 순으로 문서를 출력할 것이며, 중요도가 낮은 문서는 대기열의 뒤로 보내집니다.

대기목록의 가장 앞에 있는 문서가 대기목록에서 꺼내지고, 중요도가 최고값이 아니라면 뒤로 보내진다는 말에서, Queue를 떠올리셨다면 성공하셨습니다! 대단합니다! 문제의 반은 푸셨습니다. 선입선출(FIFO)로 문서를 꺼내며(get) 다시 대기열의 뒤로 문서를 넣을(put) 수 있죠.

큐에 대한 설명은 다음에 별도 포스팅에서 정리해보도록 합시다! 큐의 기본 개념을 모르신다면 위키피디아를 참고해 주세요!

이 배열에는 순서가 있지만, 출력이 진행되면서 문서의 위치가 변하게 됩니다. 우리가 알 수 있는 건 현재 문서의 위치이고, 그 위치에 따른 중요도 값 만을 알 수 있습니다. 만일 주어진 배열이 Int 배열이 아니라 class 객체의 배열이었다면 원하는 문서의 위치를 손쉽게 찾을 수 있겠지만, Int 배열이기 때문에 중요도 만으로는 원하는 문서의 위치를 찾을 수 없습니다.

저는 이 문제를 총 두 번의 시행착오 끝에 풀었습니다. 부끄러우니까 첫 시행착오는 접어둘게요. 심심하시 분은 보셔요 ㅎㅎㅎㅎㅎ :0

첫 시행착오

처음에 저는 일단 제 문서의 중요도를 아니까, 어차피 이 중요도보다 높은 중요도를 가지는 녀석들을 모두 빠져나갈거기 때문에 마지막으로 빠져나가는 문서의 위치를 기준으로 내 문서의 위치를 비교해서 순서를 알아내려고 했어요. 이게 어떤 식이냐면,

1. 내 문서보다 중요도가 높은 배열을 필터한다.

2. 필터한 배열에서 가장 낮은 중요도를 구한다. (1,2,3,4,5 배열이고 내 문서가 3이면 4가 되겠죠)

3. 가장 낮은 중요도의 마지막 위치(locationB)를 구한다.

4. 이 위치값(locationB)과 내 위치값(locationA)을 비교해서,  locationB가 locationA보다 작으면, locationB와 locationA 사이에 존재하는 나와 중요도가 같은 문서의 수를 구하고 locationB가 locationA보다 크면, ...locationA 와 locationB ... 범위에서 나와 중요도가 같은 문서의 수를 구한다.

5. 1번에서 필터한 배열의 수와 4번에서 구한 값을 더해서 리턴한다.

입니다!!!!! 

이제 보니 좀 많이 비효율적이고 얼토당토 않긴 한데, 안되면 모르겠는데 제가 만든 테스트 케이스에서는 되더라구요 흑흑.

코드는 이러합니다.

제가 만든 테스트 케이스는 다음과 같습니다. (누락된 케이스 제보받습니다.)

하지만 프로그래머스에서는 코드 채점에 실패했습니다. ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

그래서 다른 방식으로 접근해 보도록 합니다.

문제해결

---

이 프린터의 가장 큰 문제는 문서 대기열의 순서가 계속해서 바뀌기 때문에, 출력되는 문서가 내 문서인지 남의 문서인지 알길이 없다는 것입니다. 내 문서인지 아닌지 판별할 수 있는 방법은 파라미터로 주어지는 내 문서의 '초기 위치값'과 그로인해 알 수 있는 '중요도' 값 뿐입니다.

그렇다면 현재 프린트되는 문서의 초기 대기열 위치값을 알 수 있다면 내 문서인지 아닌지 확인할 수 있겠죠?

그래서 제시된 해결방법은 다음과 같습니다. 변수 / 함수

1. 제시된 중요도 배열과 동일한 값을 저장할 priorityQueue 와, 중요도와 현재 위치를 함께 저장한 queue 를 선언한다. 또한 출력된 문서의 수를 저장할 변수 outputCount 도 선언한다.

2. for문으로 제시된 중요도 배열을 돌면서 priorityQueue와 queue에 값을 넣어준다.

3. priorityQueue를 중요도를 기준으로 내림차순 정렬한다.

- priorityQueue를 통해 현재 문서 대기열에서 가장 높은 중요도가 무엇인지 알 수 있습니다!

4. queue를 문서 대기열이라고 생각하고, queue의 첫 번째 값을 꺼내어(removefirst) priorityQueue 첫 번째 값과 중요도를 비교한다.

4-1. 두 중요도가 같다면, priorityQueue에서 첫 번째 값을 꺼낸다(removefirst). 문서 하나를 출력했으므로, outputCount 를 + 1 해준다. 이때 출력되는 문서의 초기 위치값과 내 문서의 초기 위치값이 같은지 비교하여 값이 같다면(내 문서를 출력한 것이므로) outputCount 를 리턴해준다,

4-2. 두 중요도가 다르다면, queue의 첫 번째 값을 제일 뒤로 추가(append)한다.

5. 4번의 작업을 queue가 빌 때까지 (문서 대기열이 빌 때까지) 계속 반복한다.

설명이 어렵지 않기를 빌어요!! 이미 풀었던 걸 정리하는 데도 말로 풀어쓰는게 쉬운 일이 아니네요.

작성된 코드는 다음과 같습니다.

와 이거 쓰는데 중간에 인터넷 끊겨서 지금 테더링으로 글 작성하고 있어요!!! 날아갔으면 진짜 울뻔 ㅠㅠ

알고리즘 문제는 최대한 간결하고 짧은 코드를 써보려고 하는데, 아직 많이 미숙하네요!

더 좋은 방법이 많을 거에용 :) 일단 저의 풀이는 여기까지 입니다!

감사합니다 '-')b caution이었습니다!

주의하세요!!!!