[Inflearn] 공주 구하기(Queue)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - 3을 외친 왕자가 제외

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

배열로 풀어보았던 문제이다.

저번에 queue 를 이용해서도 풀어보았는데,

다시 풀어봅세!

동일하게 N = 8, K = 3 이 입력될 때,

먼저 Queue 에 왕들을 앉힌다.

Queue

1 2 3 4 5 6 7 8

//////////////////////////////////////////// 망 풀이

tmp

out

번호를 외치면서 3번째 번호를 외치는 왕들은 out queue 에 넣어준다.

Queue

4 5 6 7 8

tmp

1 2

out

3

다음 단계, 

Queue

7 8

tmp

1 2 4 5

out

3 6

다음 단계에서

7 8 을 tmp Queue 에 push하면 queue 가 비어있는 상태가 된다. 

이 때, tmp 를 Queue 에 복사하고 tmp 는 비워준다.

Queue

tmp

1 2 4 5 7 8

out

3 6

위 상태에서

Queue

2 4 5 7 8

tmp

out

3 6 1

그 다음 

Queue

7 8

tmp

2 4

out

3 6 1 5

...

Queue

tmp

out

3 6 1 5 2 8 4 7

3 6 1 5 2 8 4 순서로 왕이 제외된다.

아래 코드는 그림을 그리면서 짜나간 코드이다.

while(!q.empty())

{

for(i=0;i<2;i++)

{

tmp.push(q.front());

q.pop();

if(q.empty())

q = tmp;

whlie(!tmp.front()) tmp.pop();

}

out.push(q.front());    // 세 번째 왕은 out queue 에 push

q.pop();

}

마지막에 tmp queue 의 제일 마지막 원소를 반환하면 마지막으로 남은 왕자 번호가 나오게 된다.

////////////////////////////////////////////

아니 왜 이렇게 편한 queue 를 가지고 복잡하게 풀어나갔던거지?

후아.. 분발, 생각 좀 하자!!!

Queue

1 2 3 4 5 6 7 8

Out

세 번째 번호를 부르는 왕자만 Out 큐에 넣어주고 

그렇지 않은 왕자들은 뒤로 다시 넣어주면 된다..

while(!q.empty())

{

for(i=1;i<=2;i++

{

x = q.front();

q.pop();

q.push(x);

}

x = q.front();

q.pop()

out.push(x);

}

이렇게나 간단하게 풀 수 있는데 

왜이렇게 복잡하게 생각한거지?!

자료구조의 특성을 잘 생각해보고 풀자!!

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <cstdio> #include <vector> #include <queue> #include <algorithm>   using namespace std;   int main(void) {     //freopen("input.txt", "rt", stdin);       int n, k, i, x;       scanf("%d %d", &n, &k);     queue<int> q, out;       for (i = 1; i <= n; i++)         q.push(i);       while (!q.empty())     {         for (i = 1; i <= k - 1; i++)         {             x = q.front();             q.pop();             q.push(x);         }           x = q.front();         q.pop();         out.push(x);     }       printf("%d\n", out.back());       return 0; } Colored by Color Scripter

cs

ㅇ간결하게 다시 짠 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include <cstdio> #include <vector> #include <queue> #include <algorithm>   using namespace std;   int main(void) {     //freopen("input.txt", "rt", stdin);       int n, k, i;       scanf("%d %d", &n, &k);     queue<int> q;       for (i = 1; i <= n; i++)         q.push(i);       while (q.size() != 1)     {         for (i = 1; i < k; i++)         {             q.push(q.front());             q.pop();         }           q.pop();     }       printf("%d\n", q.back());       return 0; } Colored by Color Scripter

cs

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

#include<stdio.h> #include<vector> #include<queue> #include<algorithm> using namespace std;   int main(){     int n, k, i;     queue<int> Q;       scanf("%d %d", &n, &k);     for(i=1; i<=n; i++){         Q.push(i);     }       while(!Q.empty()){         for(i=1; i<k; i++){             Q.push(Q.front());             Q.pop();         }         Q.pop();         if(Q.size()==1){             printf("%d\n", Q.front());             Q.pop();         }     }       return 0; }

cs

line 18~19) front 한 원소를 저장할 변수를 따로 만들지 않고, 바로 queue 에 push 하고 pop 해주었다.

line 21) rst queue 를 따로 만들지 않고 queue 에 원소하 하나 남을 때까지 반복하므로 뺀 원소를 따로 저장할 필요가 없었다.

line 22~25) queue 에 원소가 하나 남았을 경우, 남은 원소를 출력하고 pop 해주게 되면 queue 가 빈 상태가 되어 while 문이 종료된다.

제외된 왕들을 따로 저장할 필요가 없이 queue.size() 를 활용했으면 훨씬 효율적이게 구현할 수 있었는데..

아직도 한참이구먼..

정신차리자아ㅏㅏ

#. Result

  - Input --------------------------------------------------------

8 3

------------------------------------------------------------------

  - Output --------------------------------------------------------

7

------------------------------------------------------------------