ITwork

www.acmicpc.net/problem/2751

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

2750문제에서 array size만 1000000로 변경하였다. 

/*baekjoon 2751 수 정렬하기2 */
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX 1000001

int main()
{
	int data[MAX];
	int i,j, N;
	int tmp, exchg;

	vector<int> v;

	//input data size
	cin >> N;

	//input data
	for(i=0; i<N; i++) {
		cin >> data[i];
		v.push_back(data[i]);
	}

	sort(v.begin(), v.end());
	for(vector<int>::iterator it=v.begin(); it<v.end(); it++)
		printf("%d\n", *it );
		
	return 0;
}
/*baekjoon 2751 수 정렬하기2 */

www.acmicpc.net/problem/2750

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

풀이 방법 : 

-입력 받고 

-단순 sorting함수 이용해서 풀면 되는 간단한 문제 

/*baekjoon 2750 수 정렬하기*/
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX 1001

int main()
{
	int data[MAX];
	int i,j, N;
	int tmp, exchg;

	vector<int> v;

	//input data size
	cin >> N;

	//input data
	for(i=0; i<N; i++) {
		cin >> data[i];
		v.push_back(data[i]);
	}

	sort(v.begin(), v.end());
	for(vector<int>::iterator it=v.begin(); it<v.end(); it++)
		printf("%d\n", *it );
		
	return 0;
}
/*baekjoon 2750 수 정렬하기*/

이제 좀 코딩 연습을 하고 나서 다시 작성한 내용입니다. 

2021.6.26

  1 /*baekjoon 2750 수 정렬하기*/
  2 #include <iostream>
  3 #include <algorithm>
  4 using namespace std;
  5 #define MAXN 1001
  6 
  7 int N;
  8 int Data[MAXN+10];
  9 
 10 void InputData(){
 11     cin >> N;
 12     for(int i=0; i<N; i++){
 13         cin >> Data[i];
 14     }
 15 }
 16 void Solve(){
 17     for(int i=0; i<N; i++){
 18         cout << Data[i] << endl;
 19     }
 20 }
 21 int main()
 22 {
 23     InputData();
 24     sort(Data, Data+N);
 25     Solve();
 26     return 0;                                                                          
 27 }   
 28 /*baekjoon 2750 수 정렬하기*/

www.acmicpc.net/problem/10866

문제

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

dequeue를 기본 api 확인하는 문제이다. 

/*baekjoon 10866 dequeue*/
#include <iostream>
#include <deque>
#include <cstring>

using namespace std;
#define MAX_N 100

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


    int n,i,dt;
    char str[20];
    cin >> n;

    deque<int> dq;


    for(i =0; i < n; i++ ){

        cin >> str;

        if( !strcmp(str, "push_front") ){
            cin >> dt;
            dq.push_front(dt);
        }else if( !strcmp(str, "push_back") ){
            cin >> dt;
            dq.push_back(dt);
        }else if( !strcmp(str, "pop_front") ){
            if(!dq.empty() ){
                cout << dq.front() << '\n';
                dq.pop_front();
            }else{
                cout << "-1" << '\n';
            }
        }else if( !strcmp(str, "pop_back") ){
            if(!dq.empty() ){
                cout << dq.back() << '\n';
                dq.pop_back();
            }else{
                cout << "-1" << '\n';
            }
        }else if( !strcmp(str, "size") ){
            cout << dq.size() << '\n';
        }else if( !strcmp(str, "empty") ){
            cout << dq.empty() << '\n';
        }else if( !strcmp(str, "front") ){
            if(!dq.empty() ){
                cout << dq.front() << '\n';
            } else {
                cout << "-1" << '\n';
            }
        }else if( !strcmp(str, "back") ){
            if(!dq.empty() ){
                cout << dq.back() << '\n';
            } else {
                cout << "-1" << '\n';
            }
        }
    }

    return 0;
}

www.acmicpc.net/problem/11866

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

예 

(7, 3)

1 2 3 4 5 6 7

3번째  제거  3

4 5 6 7 1 2

3번째 제거  6

4 5 6 7 1 2

3번째 제거 2

7 1 2 4 5

3번째 제거 7

4 5 7 1

3번째 제거 5

 1 4 5

3번째 제거 1

1 4

나머지 남은 건

4

[키 포인트]

큐는 FIFO인 특성을 잘 이해하고 풀면 될 것 같습니다. 

front를 빼서 다시 push하면 loop를 돌면서 저장되는 특성이 있는 걸 이해하면 쉽게 풀 수있을 것 같습니다. 

[풀이 ]

loop( queue가 빌때까지 ){

  K-1 만큰 front를 다시  queue에 저장 

  K번째는 front해서 print하고 나서 pop해서 제거 

}

/*baekjoon 11866 queue*/
#include <iostream>
#include <queue>

using namespace std;
queue<int> q;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	int i=0,j=0;
	int N; // N명 
	int K; //K번째 제거 
	cin >> N;
	cin >> K;



    for(i =1; i <= N; i++ ){
        q.push(i);
    }

    cout << "<";
    while( !q.empty() ){
        for(i=0; i<K-1; i++){
            q.push( q.front() );
            if(!q.empty()){  q.pop(); }
            j++;
        }

        j++;
        if( !(j%K) ) {

            if(q.size() != 1)
                cout << q.front() << ", ";
            else if(q.size() == 1)
                cout << q.front();

            if(!q.empty()){
                q.pop(); }
        }
    }

    cout << ">" << endl;


	return 0;
}

www.acmicpc.net/problem/2164

N=4일 경우 

1 2 3 4

규칙 : 아래 반복 

맨 위 카드 버림 --> 맨 위 카드를 맨 아래로 이동 --> 맨 위카드 버림 --> 맨 위카드를 맨 아래로 이동 

1 2 3 4

맨 위 카드 버림

2 3 4

맨 위 카드 맨 아래 

3 4 2

맨 위 카드 버림

4 2

맨 위 카드 맨 아래로

2 4

맨 위 카드 버림

4

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
#define MAX_N 100
queue<int> q;


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	int i,n,tmp;
	cin >> n;



	for(i =1; i <= n; i++ ){
		q.push(i);
	}

	while( 1 ){
		if( q.size() ==1)
			break;

		q.pop();
		tmp = q.front();	
		q.pop();
		q.push(tmp);
	}

	cout << q.front();
		
	return 0;
}