DailyBread

의식의 흐름대로 짠 소스

개선점 : 모든 케이스를 모두 디버깅 하기 힘듬 

#include <iostream>
#include <vector>
using namespace std;

int main(){
	string inputPat;
	string inputStr;
	vector<string> result;
	
	int cntStr;
	int checked;
	
	cin >> cntStr;
	cin >> inputPat;
	 
	for (int i=0;i<cntStr;i++){
		cin >> inputStr;
		
		int fi=0;
		int pi=0;
		int si=0;
		
		//check front pattern
		for (;fi<inputPat.length() && fi<inputStr.length() && inputPat[fi]!='*';fi++){
			if ( inputPat[fi] == inputStr[fi]) {
					checked = 1;
			} else {	
			 checked = 0;
			 break;
			}
		}
		if (inputPat[fi] !='*') checked = 0;
				
		//check last pattern
		if ( checked ==1 && inputPat[fi]=='*' ){
			pi = inputPat.length()-1;
			si = inputStr.length()-1;
			
			for (; inputPat[pi]!='*' && pi>0 && si>0 && si>=fi ; pi--, si-- ){
				if ( inputPat[pi] == inputStr[si]) {
					checked = 1;
				} else {
					checked = 0;
					break;
				}
			}
			if (inputPat[pi] !='*') checked = 0;
		}
		
		if (checked == 1) result.push_back("DA");
		else result.push_back("NE");
	}
	
	for (auto a : result) cout << a << "\n";

	return 0;									
}

std 를 사용해서 조금더 간략화

개선점 : 가장 큰 조건을 먼저 처리하자 > 그리고 나서 세부 조건을 처리

           여러 레벨의 조건을 간략화 하

#include <iostream>
#include <vector>
using namespace std;

int main(){
	string inputPat;
	string frontPat;
	string endPat;
	
	vector<string> result;
	
	int cntStr;
	int checked;
	int stari;
	
	cin >> cntStr;
	cin >> inputPat;
	
	stari = inputPat.find("*");
	frontPat = inputPat.substr(0,stari);
	endPat = inputPat.substr(stari+1,inputPat.length()-1);
	
	for (int i=0;i<cntStr;i++){
		string inputStr;
		cin >> inputStr;
		
		string frontStr;
		string endStr;
		checked = 0;
		
		//check front pattern
		if (inputStr.length()>=frontPat.length()){
			frontStr = inputStr.substr(0,stari);
			if (frontStr == frontPat){
				inputStr.erase(0,stari);	
		
				//check last pattern
				if (inputStr.length()>=endPat.length()){
					endStr = inputStr.substr(inputStr.length()-endPat.length(), endPat.length() );
					if (endStr == endPat) {
						checked = 1;	
					}
				}
			} 
		}
		if ( checked ==1 ) result.push_back("DA");
		else result.push_back("NE");
	}	
	
	for (auto a : result) cout << a << "\n";

	return 0;									
}

불필요한 검사 제거

#include <iostream>
#include <vector>
using namespace std;

int main(){
	string inputPat;
	string frontPat;
	string endPat;
	
	vector<string> result;
	
	int cntStr;
	int checked;
	int stari;
	
	cin >> cntStr;
	cin >> inputPat;
	
	stari = inputPat.find("*");
	frontPat = inputPat.substr(0,stari);
	endPat = inputPat.substr(stari+1,inputPat.length()-1);
	
	for (int i=0;i<cntStr;i++){
		string inputStr;
		cin >> inputStr;

		checked = 0;
		
		//check front pattern
		if ( inputStr.length() >= frontPat.length()+endPat.length()) {
			if ( (frontPat == inputStr.substr(0, frontPat.length())) &&
				 (endPat == inputStr.substr(inputStr.length()-endPat.length())) ) 
				 	checked = 1;
		}
		
		if ( checked ==1 ) result.push_back("DA");
		else result.push_back("NE");
	}	
	
	for (auto a : result) cout << a << "\n";

	return 0;									
}

#

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

using namespace std;

//초기화 하고나서, push_back하면 뒤에 들어감 
//vector<int> target(10);

vector<int> target;
vector<int> selected;

int find100sum(vector<int> dwarfHeight, int num){

	if ( num == 7 )	{
		if ( accumulate(target.begin(), target.end(), 0) == 100 ) {
			sort(target.begin(), target.end());
			for (int i=0; i<target.size();i++ ) cout << target[i] << "\n";
			return 1;
		}
		return 0;
	}
	
	for (int i=num;i<dwarfHeight.size();i++){
		
		target.push_back(dwarfHeight[i]);
		if ( find100sum(dwarfHeight, num+1) == 1 ) return 1;
		target.pop_back();
	}
	
	return 0;
}

int main(){
	
	vector<int> dwarfHeight(9);
	
	for (int i=0;i<9;i++) cin >> dwarfHeight[i];
	
	find100sum(dwarfHeight, 0);
	
	return 0;	
}

• upper_bound - return the position of exceeding value from key
• lower_bound - return the position of same or first larger value than key
• Target array or vector shall be in sorted condition.

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

using namespace std;

int main(){
	vector<int> v;
	int a[5] = {1,2,2,2,3};
	for (int i=0; i<5; i++){
		v.push_back(a[i]);
	}
	int x=2;
	int c=(int)(upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x));
	int f=(int)(lower_bound(v.begin(), v.end(), x) - v.begin());
	int t=(int)(upper_bound(v.begin(), v.end(), x) - v.begin());
	
	int f2= *lower_bound(v.begin(), v.end(), x);
	int t2= *upper_bound(v.begin(), v.end(), x);
	printf(" %d count : %d, starting : %d, ending : %d\n", x, c, f, t);
	printf(" lower bound start : %d, upper bound start : %d\n", f2, t2);
	
	c = (int) (upper_bound(a,a+5,x) - lower_bound(a,a+5,x));
	f = (int) (lower_bound(a,a+5,x) - a);
	t = (int) (upper_bound(a,a+5,x) - a);
	f2 = *lower_bound(a,a+5,x);
	t2 = *upper_bound(a,a+5,x);

	printf(" %d count : %d, starting : %d, ending : %d\n", x, c, f, t);
	printf(" lower bound start : %d, upper bound start : %d\n", f2, t2);
	
	return 0;
}

Prime number only can be devided by 1 and itself. ( only two 약수 )

1 is not a prime number or not a composition number.

#include <iostream>
#include <vector>
using namespace std;

vector<int> era(int mx_n){
	vector<int> v;
	vector<int> che(mx_n+1);
	
	for (int i=2; i<=mx_n; i++){
		if (che[i]) continue;
		for (int j=2*i; j<=mx_n; j += i) {
			che[j] = 1;
		}
	}
	
	for(int i = 2; i <= mx_n; i++) {
		if(che[i] == 0) v.push_back(i);		
	} 
	return v;
}

int main(){
	vector<int> result;
	
	result = era(100);		
	for (auto a : result) cout << a << " ";
	
	return 0;
}

순열 : n개의 집합에서 대상 r을 순서 있게 배열하는 가짓수

https://practice.geeksforgeeks.org/problems/permutations-of-a-given-string2041/1/

class Solution
{
	public:
	vector<string> buffer;
	string b;
	
	void loop_permutation(string s, vector<int> &check, int level){
	    if (level == s.length() ){
	    	buffer.push_back(b);
	        return;
	    }
	    
	    for (int i=0;i<s.length();i++) {
	        if ( check[i] == 1 ) continue;
	        else {
	            check[i] = 1;
	            b.push_back(s[i]);
                
                //recursive call
	        	loop_permutation(s, check, level+1);
                
                //back track
	            check[i] = 0;
	            b.pop_back();
	        }
	    }
	}
	
	vector<string> find_permutation(string S)
	{
	    vector<int> check(S.length()+1);
	    loop_permutation(S, check, 0);
	    sort(buffer.begin(), buffer.end());
	    return buffer;
	}
};

문제점 : check와 b라는 별도 공간을 사용

https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

조합 : n개에서 r개를 순열로 뽑은 다음에, 순서는 상관없으니 r개 뽑은 대상들의 가짓수를 제외함

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int n = 5;
int k = 3;
int a[5] = {1, 2, 3, 4, 5};
vector<int> b;

void print(vector<int> b){
	for(int i = 0; i < b.size(); i++){
		cout << b[i] << " ";
	}
	cout << endl;
}

void combi(int start, vector<int> b){

	if (b.size()==k){
		print(b);
		return;
	}
	
	for ( int i=start+1; i<n;i++){
		cout << " i:" << i <<"\n";
		b.push_back(a[i]);
		combi(i,b);
		b.pop_back();
	}
	
	return;

}

int main() {
	combi(-1, b);
	return 0;
}