조세퍼스 문제
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 13850 | 6939 | 5249 | 52.104% |
문제
조세퍼스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ M ≤ N ≤ 5,000)
출력
예제와 같이 조세퍼스 순열을 출력한다.
예제 입력 1
1
7 3
예제 출력 1
1
<3, 6, 2, 7, 5, 1, 4>
풀이
6개월 전 문제풀이 방법
다시 봤을 때는 왜 이딴식으로 풀었지?..란 생각을 했다..
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
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define IOFAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main(){
IOFAST();
int n, m, i,mm;
cin >> n >> m;
mm = m; //입력받은 m값 mm에 복사
queue<int> q; //입력과 계산을 위한 큐
vector<int> v; //출력을 위한 벡터
for (i = 1; i <= n; i++){
q.push(i); //큐에 데이터 입력
}
while (v.size()!=n){
int num;
if (m == 1){ //만약 입력받은 m값이 1이면 그냥 그대로 벡터에 넣어줌.
num = q.front();
q.pop();
v.push_back(num);
}
else{
for (i = 0; i < m - 1; i++){ //m값 전까지 팝해서 다시 푸쉬
int temp = q.front();
q.pop();
q.push(temp);
}
num = q.front(); //m번째 값은
q.pop();
v.push_back(num); //출력 벡터에 넣어줌.
}
if (q.size() < m){ //만약 큐사이즈가 m보다 작아지면
m = mm - q.size(); //출력 갯수를 세어줄 m데이터를 변경..
}
else{
m = mm;
}
}
cout << '<';
for (i = 0; i < n-1; i++)
cout << v[i] << ", ";
cout << v[n-1] << '>';
return 0;
}
지금의 문제풀이
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
38
39
40
41
42
//
// 1158_조세퍼스 문제.cpp
// AlgorithmCpp
//
// Created by 정경인 on 2018. 12. 10..
// Copyright © 2018년 kyoungin. All rights reserved.
//
#include <iostream>
#include <deque>
#define IOFAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main(){
IOFAST();
deque<int> dq,result ;
int i,n,val,temp;
cin >> n >> val;
for(i=1; i<=n;i++){
dq.push_back(i);
}
while(!dq.empty()){
for(i=1;i<val;i++){
temp = dq.front();
dq.pop_front(); //val번 전까지는 앞에서 빼서
dq.push_back(temp); //뒤로 다시넣어줌
}
temp = dq.front(); //val번은
dq.pop_front(); //앞에서 빼서
result.push_back(temp); //출력을 위해 result 덱에 넣어줌.
}
//출력
cout <<'<';
for(i=1;i<n;i++){
cout << result.front() << ", ";
result.pop_front();
}
cout << result.front() << ">\n";
}
비슷한 문제풀이이지만 가독성으로 봤을 때는 지금이 더 낫다고 생각하지만 시간은 6개월 전 코드가 더 적게 걸렸다.
그 이유를 생각해 보니 이 전 코드의
부분이 시간을 줄이는 데 효과가 있었다. 이 코드를 다시 봤을 때 , 이건 굳이 왜 쓴걸까? 라고 생각했는데 만약 제거 될 M값이 큐 사이즈N 보다 커지게 될 때 굉장히 효과적이다. 예를 들어서,
N이 4이고 M이 7이 된다면, 반복문을 7번 돌리면서 출력데이터를 뽑는 것과, 3번 돌리면서 출력데이터를 뽑는 것이 같은 결과를 가져온다는 것을 알 수 있다.(!!!!!!!!!)
6개월 전에 나는 나름.. 생각을 많이 하고 알고리즘을 풀었던 것 같다 ……^___^….