[c++] Ugly number(세 수 비교하기), K진수 출력(stack)

Ugly number

 

내가푼코드

#include <iostream>
#include <vector>
#include <algorithm>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int a[1501];
int main() {
	//freopen("input.txt", "rt", stdin);
	int n, i, j, x, p1=1, p2=1, p3=1, min=2147000000;
	scanf("%d", &n);
	j=1;
	a[1]=1;
	i=1;
	while(i<=n){
		i++;
		if(a[p1]*2<=a[p2]*3 && a[p1]*2<=a[p3]*5){
				min=a[p1]*2;		
		}
		if(a[p2]*3<=a[p1]*2 && a[p2]*3<=a[p3]*5){
				min=a[p2]*3;	
		}
		if(a[p3]*5<=a[p1]*2 && a[p3]*5<=a[p2]*3){
				min=a[p3]*5;	
		}
		a[i]=min;
		if(a[p1]*2==min) {
			p1++;	
		}
		if(a[p2]*3==min) {
			p2++;
		}
		if(a[p3]*5==min) {
			p3++;	
		}
	}
	printf("%d", a[n]);
	return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int a[1501];
int main() {
	//freopen("input.txt", "rt", stdin);
	int n, i, p2, p3, p5, min=2147000000;
	scanf("%d", &n);
	a[1]=1;
	p2=p3=p5=1;
	for(i=2; i<=n; i++){
		if(a[p2]*2<a[p3]*3) min=a[p2]*2;
		else min=a[p3]*3;
		if(a[p5]*5<min) min=a[p5]*5;
		if(a[p2]*2==min) p2++;
		if(a[p3]*3==min) p3++;
		if(a[p5]*5==min) p5++;
		a[i]=min;
		//printf("a[i]: %d\n", a[i]);
	}
	printf("%d", a[n]);
	return 0;
}

투포인트 알고리즘을 응용한 3포인트 알고리즘이 사용된 문제이다.

내가 풀었던 코드에서는 하나씩 모두 비교를 했는데 

강의 코드에서는

a[p2]<a[p3] 일때 min=a[p2] 아니면 min=a[p3]으로해서

마지막에 min과 a[p5]만 비교해주었다.

 

 

K진수출력

stack을 직접 구현한 것

#include <iostream>
#include <vector>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int a[1501];
int stack[11];
int top=-1;
void push(int x){
	stack[++top]=x;
}
int pop(){
	int res;
	res = stack[top--];
	return res;
}
int main() {
	//freopen("input.txt", "rt", stdin);
	int n, k, i, x;
	char str[20]="0123456789ABCDEF";
	scanf("%d %d", &n, &k);
	i=n;
	while(1){
		x=i%k;
		push(x);
		i=i/k;
		if(i==0){
			break;
		}
	}
	
	
	for(i=top; i>=0; i--){
		printf("%c", str[pop()]);
	}
	return 0;
}

stack 메소드사용

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int a[1501];
int main() {
	//freopen("input.txt", "rt", stdin);
	int n, k, i, x;
	stack<int> s;
	char str[20]="0123456789ABCDEF";
	scanf("%d %d", &n, &k);
	i=n;
	while(i>0){
		x=i%k;
		s.push(x);
		i=i/k;
	}
	while(!s.empty()){
		printf("%c", str[s.top()]);	
		s.pop();
	}	
	return 0;
}

첫번째 코드는 stack자료구조를 직접 구현한 것이고 밑에있는 코드는 구현되어 있는 stack을 사용한 코드이다.

 

이 문제에서 헷갈렸던 부분은

++나 -- 연산자가 top의 앞에서 사용될때와 뒤에서 사용되는 경우 어떻게 다른가였다. 

코드로 예를 들어서 아래 코드를 설명하면

top=-1인 상태에서 

1. stack[++top]

- 먼저 top값을 증가시키고 stack에 있는 값을 출력하겠다.

--> 결과: stack[0];

2. stack[top--]

- stack에 있는 값을 출력한 후 top값을 감소시키겠다.

--> 결과: stack[-1];

 

 더 자세한 설명은 아래 포스팅 참고

soyeondev.tistory.com/196

[c++] ++a, a++ 전위연산자, 후위연산자 예제