BOJ 2014 소수의 곱

2014번: 소수의 곱

 

문제를 어렵게 생각하지 않는 것 이 중요한 문제다.

각 소수마다 계산해야 하는 대상이 달라질 수 있는데, 그 대상을 새롭게 탐색하지 않는 부분에 포인트를 맞추어 구현했다.

 

 

---

 

최초에 정답 확인용 리스트에 1을 넣은 채로 시작하도록 하자.

파란 사각형은 입력으로 주어진 소수들을 의미하고, 파란 사각형 밑에 붙을 흰색 작은 사각형은 각 소수의 연산 대상이라고 생각하면 된다. 자세한 내용은 아래에 기술한다.

 

---

각 소수 별로 다른 우선순위 큐 를 이용하는 방법을 이용해 정답을 찾아보자.

 

규칙은 아래와 같다.

• (규칙 A) 정답 리스트의 가장 마지막 값을 각 소수를 담당한 큐 에 넣어준다.
• (규칙 B) 각 소수들을 순회하며 큐의 최솟값 * 해당 소수의 값을 임시 답으로 계산한다.
  • (규칙 B-1) 이때, 만약 임시 답이 정답 리스트의 마지막 값과 같다면 해당 임시 답을 pop 한 뒤 바로 다시 구한다.
• (규칙 C) 모든 임시 답을 구하면 그중 가장 작은 값을 정답 리스트에 넣고 해당 임시 답은 pop 한다.
• (규칙 D) 정답 리스트의 개수가 구하고자 하는 크기가 될 때까지 반복한다.

 

위의 규칙을 따라 문제에서 주어진 예시인 2, 3, 5, 7을 이용해 19번째 답을 구해보자.

 

 

 

최초, 1을 정답 리스트에 넣어주고 시작했으므로 규칙 A에 의해 위와 같은 상태가 된다.

 

 

 

이후 규칙 B를 적용하여 각 소수 별 임시 정답인 2, 3, 5, 7을 구한다.

 

 

 

규칙 C에 의해 임시 정답 중 가장 작은 값은 2 이므로 2를 정답 리스트에 넣어두고 소수 2에 해당하는 큐에서 1을 삭제한다.

 

 

 

규칙 D에 의해 반복을 시행하며, 규칙 A에 의해 모든 소수의 큐에 정답 리스트의 가장 마지막 값인 2가 넣어진 모습이다.

 

 

 

이를 반복하여 순차적으로 진행한다.

 

 

 

 

 

 

 

 

 

이때, 규칙 B-1에 의해 3*2 인 6은 바로 큐에서 삭제되고 3*3인 9가 소수 3의 임시 답이 된다는 점 만 주의하면 된다.

 

 

 

 

 

 

 

 

사실 공간 복잡도를 매우 낭비한 해법이다.

공간을 아끼기 위해서는 메모리에 정답 리스트만 가진 채로, 각 소수에서 정답 리스트를 탐색하는 커서를 하나씩 가지면 된다.

알고리즘은 동일하게 가되, 임시 답을 자기 자신 * 커서의 값으로 처리하고 pop 절차를 커서 이동으로 구현해도 동일한 시간 복잡도가 나올 수 있다.

(오히려 우선순위 큐에 삽입, 삭제 시간이 줄어듦으로 빨라질 것이다)

 

이렇게 구현한 이유는 코딩 테스트를 대비하고자 시간제한(30분) 내에 풀기 위해서 구현상 더 간단한 방법을 취했기 때문이며  (사실상 처음 생각난 방법을 그대로 구현했기 때문이며) 위 방법이 매우 올바른 해법이 아님을 주의해야 한다.

 

---

 

code

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지

 

오랜만에 포스팅을 올린다.

평소 문제를 풀 때, 알고리즘을 간단히 정리하고 (본문에서의 '규칙'이라고 표현하는 부분을 끄적여 둔다) 구현을 하는 편이다. 그런데 시간이 며칠 지난 뒤 포스팅을 해보니 내 알고리즘 or 구현의 멍청한 부분이 잘 보이는 게 신기하다.

 

나 자신의 멍청한 점을 더 정확히 보기 위해 포스팅을 할 때 구현한 뒤 2~3일이 지난 문제를 포스팅하는 게 좋겠다.