알못에서 잘알까지

    4번 문제   

www.acmicpc.net/problem/1966

    내가 풀이한 답   

  문제에서 문서의 인덱스를 기준으로 문서를 찾아야 하기 때문에 <int, int> 쌍의 queue 자료구조와 문서의 중요도를 확인하기 위해 priority_queue 자료구조를 사용하였다. priority_queue의 첫 번째 요소와 queue의 중요도가 같지 않으면 queue의 첫 번째 요소를 뒤로 보내고 만약 priority_queue의 첫 번째 요소와 queue의 중요도가 같고 문서의 인덱스와 주어진 문제의 인덱스(m)와 같으면 종료하고 그렇지 않으면 priority_queue의 첫 번째 요소와 queue의 첫 번째 요소를 제거한다. 

//#include <bits/stdc++.h>
#include <iostream>
#include <queue>
using namespace std;

int main() {
	//freopen("input.txt", "rt", stdin);
	int t, i, n, m, j, a, idx, imp, cnt;
	cin >> t;
	for(i=0; i<t; i++){
		cnt=0;
		queue<pair<int, int> > q;
		priority_queue<int> pq;
		
		cin >> n >> m;
		for(j=0; j<n; j++){
			cin >> a;
			q.push({j, a});
			pq.push(a);
		}
		
		while(true){
			idx = q.front().first;
			imp = q.front().second;
			
			if(imp == pq.top()){
				cnt++;
				if(idx==m) break;
				q.pop();
				pq.pop();
			}
			else {
				q.push({idx, imp});
				q.pop();
			}
		}
		cout << cnt << endl;
	}

	return 0;
}

    3번 문제   

www.acmicpc.net/problem/11866

    내가 풀이한 답   

  k번째 까지 원소를 뒤로 넣은 다음 k번째 원소를 제거하는 행위를 원소가 하나 남을 때까지 이 과정을 반복하였다.

//#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
	//freopen("input.txt", "rt", stdin);
	queue<int> q;
	vector<int> v;
	int n, k, i;
	
	cin >> n >> k;
	
	for(i=1; i<=n; i++){
		q.push(i);
	}
	
	while(true){
		if(q.size()==1) {
			v.push_back(q.front());
			break;	
		}
		for(i=1; i<k; i++){
			q.push(q.front());
			q.pop();
		}
		v.push_back(q.front());
		q.pop();
	}
	
	cout << "<";
	for(i=0; i<v.size()-1; i++){
		cout << v[i] << ", ";
	}
	cout << v[v.size()-1] << ">";
	return 0;
}

    2번 문제   

www.acmicpc.net/problem/2164

    내가 풀이한 답   

  기본적인 큐를 사용하는 문제이다. 큐의 함수들을 안다면 쉽게 풀 수 있는 문제이다. 

//#include <bits/stdc++.h>
#include <iostream>
#include <queue>
using namespace std;

int main() {
	//freopen("input.txt", "rt", stdin);
	queue<int> q;
	int n, temp=0;
	cin >> n;
	
	for(int i=1; i<=n; i++){
		q.push(i);
	}
	
	
	while(true){
		if(q.size()==1) break;
		q.pop();
		temp = q.front();
		q.pop();
		q.push(temp);
	}
	
	cout << q.front();
}

    1번 문제   

    내가 풀이한 답   

 Stack 자료구조를 사용하였다. 이 문제를 풀 때 주의해야 할 점은 두 가지가 있는데 첫 번째는 while문에서 종료 조건문을 n이 k진수보다 작을 때 종료해야 한다는 점과 16진수에서 10이상 15이하의 숫자는 A~F로 표현된다는 점이다. 

//#include <bits/stdc++.h>
#include <iostream>
#include <stack>
using namespace std;

int main() {
	//freopen("input.txt", "rt", stdin);
	
	int n, k;
	char a[6] = {'A', 'B', 'C', 'D', 'E', 'F'};
	cin >> n >> k;
	stack<int> s;
	
	while(n>k-1){
		s.push(n%k);
		n = n/k;
 		if(n<k) {
 			s.push(n);	
		}
	}
	
	
	while(!s.empty()){
		if(k==16) {
			if(s.top()>=10) {
				cout << a[s.top()-10];
				s.pop();
			}
			cout << s.top();
			s.pop();	
		}
		else {
			cout << s.top();
			s.pop();	
		}	
	}
	
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int stack[100], top=-1;

void push(int x){
	stack[++top]=x;
}
int pop(){
	return stack[top--];
}

int main(){
	freopen("input.txt", "rt", stdin);
	int n, k;
	char str[20]="0123456789ABCDEF";
	scanf("%d %d", &n, &k);
	while(n>0){
		push(n%k);
		n=n/k;
	}
	while(top!=-1){
		printf("%c", str[pop()]);
	}	
	return 0;
}




#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;		
int main(){
	freopen("input.txt", "rt", stdin);
	int n, k;
	stack<int> s;
	char str[20]="0123456789ABCDEF";
	scanf("%d %d", &n, &k);
	while(n>0){
		s.push(n%k);
		n=n/k;
	}
	while(!s.empty()){
		printf("%c", str[s.top()]);
		s.pop();
	}	
	return 0;
}