'Programming Problems/Digits'에 해당되는 글 2건

Programming Problems/Digits

홀수와 짝수의 합이 같은 정수의 갯수 세기

제곧내. n  자릿수 보다 작은 홀수와 짝수의 합이 같은 정수의 갯수를 세보자.


DP를 사용해보자.


완전탐색에서 시작해 보자.


int countsame(int curr){

if(curr>n) return 0;

int ret = 0;

curr *= 10;

for(int i = 0 ; i < 9 ; i++){

if(isequal(curr+i)) ret = ret + 1 + countsame(curr+i);

else ret = countsame(curr+i);

}

return ret;

}


NlogN 알고리즘인듯. isequal이 logN짜리라서;


근데 저렇게 하면 중복이 있을꺼같다..


n자릿수 기준으로 만들어 보자


int countsame(int curr, int n , int odd, int even){

if(curr==n) return 0;

int ret = 0;

if(odd==even) ret++;

for(int i = 0 ; i < 10 ; i++){

if(curr%2==0){

ret += countsame(curr,n,odd+i,even);

}else{

ret += countsame(curr,n,odd,even+i);

}

}

return ret;

}


Programming Problems/Digits

주어진 숫자를 이어서 만들 수 있는 가장 큰 값은?

1 112 113 >> 1131121

9 918 917 >> 9918917


성질 탐구


대소관계가 정해진다.


3 34 어느게 먼저? 34.

3 32 어느게 먼저? 3


323 324 어느게 먼저? 324


32 324 어느게 먼저? 324


만약 긴쪽의 남은 부분에 더 큰게 하나라도 있으면 긴걸 먼저 쓴다. 물론 남기 전의 모든 값이 같을때 얘기다.

자릿수가 양쪽 다 있는 경우 큰게 먼저 나오는 쪽을 먼저 쓴다.


4 111 >> 4111

4 115 >> 4115

4 415 >> 4154 4415


32 323123


이거는 즉, 3123을 끝에 놓느냐 중간에 놓느냐로 비교를 해야겠다. 이때 반복되는 부분 32와 3123을 비교해야 한다.

그러면 32가 더 크다는 결론을 얻는다. 만약


32 323223 이었으면


>>32 32 3223


32 3223


>> 32 32 23


32 23


>> 32 > 23 (결과 나옴)


끔찍한 비교방법이 나왔다. 버린다.


그냥 두개를 비교하는 방법은 서로 앞뒤로 붙인걸 대소비교 하는 방법이다. 직접 안 붙이고 인덱스 순회로 가능할듯


그럼 대소비교가 O(M+N) 정도 되는데, 자릿수가 많이 다를 수 있으므로.. 퀵소트를 한다고 치면 비교 횟수는 대략 NlogN 회 정도이므로 O(LNlogN) 이 되겠다. (L은 평균 길이)


소트를 해서 쭉 이어버린다.


bool comparator(string s, string t){

int currs = 0;

int currt = 1000500;

// currs는 s에서 시작하고 currt는 t에서 시작한다.

while(currs<s.size()+t.size()){

if(currs>1000000 && currt>1000000 && s[currs-1000500]!=t[currt-1000500]){

return s[currs-1000500]>t[currs-1000500];

}else if(currs<=1000000 && currt>1000000 && s[currs]!=t[currt-1000500]){

return s[currs]>t[currt-1000500];

else if(currs>1000000 && currt<=1000000 && s[currs-1000500]!=t[currt]){
    return s[currs-1000500]>t[currt];

else if(currs<=1000000 && currt <= 1000000 && s[currs]!=t[currt]){

return s[currs]>t[currt];

}else{

if(currs==1000500+t.size()) currs = 0;

else if(currs==s.size()) currs = 1000500;

else currs++;

if(currt == 1000500+t.size()) currt = 0;

else if(currt==s.size()) currt = 1000500;

else currt++;

}

}

// completely same

return true;

}


string concatenate(vector<string> & data){

sort(data.begin(),data.end(),comparator);

string ret = "";

for(string x : data) ret += x;

return ret;

}


말한 대로, 시간 복잡도는 O(LNlogN) 이다.

공간 복잡도는 뭐 O(LN) 정도? 출력해야 하니까..