youngmin.log

• [ 장르 ] Sort

• Code

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> citations) {
    sort(citations.begin(), citations.end(), greater<int>());

    for (int i = 0; i < citations.size(); ++i) {
        if (citations[i] < i + 1) {
            return i;
        }
    }

    return citations.size();
}

" H-Index 란 무엇인가 ? "

[ CheckPoint ]

• 문제에대한 이해가 왠만한사람은 잘못된 길로 갈 가능성이 큰 문제다.
• [ 3,0,6,1,5 ] 일때 내림차순을 통해 [ 6,5,3,1,0 ] 에서 '3'일때 자기보다 크거나같은 요소는 3개, '3'보다 작은 수는 자기를 제외하고 2개니깐 답이 '3'이 ! 아니라, 이는 표를 통해 확인하자.

총 인용 수 ( 내림차순 )	순위
6	1
5	2
3	3
1	4
0	5

일때, 총 인용 수 < 순위이기 바로 직전 순위가 바로 "H-Index"이다. 애초에 Index하니깐 Index가 답이지 어떤 값이 정답이 되는게 아닌 듯하다.

다른 예로, [ 1,7,0,1,6,4 ] 가 있다 치자.

총 인용 수 ( 내림차순 )	순위
7	1
6	2
4	3
1	4
1	5
0	6

일때, 여기서 H-Index는 '3' 이다.

H-index 정의를 가져오자면, "피 인용수( Citation ) 가 논문의수( Index,No. ) 와 같아지거나 작아지기 시작하는 No.( = Index ) 가 H-Index이다.

이를 의미적으로 접근하면,예로들어 전체 논문의 수가 5편이고, H-Index가 3 이라함은 그 중, "3편의 논문은 3회이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 떄문에 H-Index는 3입니다." 이다.

• [ Question ]

[ Problem ] #42746 가장큰수

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

programmers.co.kr

• Version 1 ( 정렬기준을 정확히 설계해놓지 않았을 경우, 볼 필요 X )

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<int> numbers) {
    string answer = "";
    vector<int> Highest_digit;
    vector<int> priority;
    int tmpDigit,tmpNum;
    string str;
    for(int i = 0 ; i < numbers.size(); i++)
    {
        if(numbers[i] / 1000 != 0)
            Highest_digit.push_back(numbers[i] / 1000);
        else if(numbers[i] / 100 != 0)
            Highest_digit.push_back(numbers[i] / 100);
        else if(numbers[i] / 10 != 0)
            Highest_digit.push_back(numbers[i] / 10);
        else
            Highest_digit.push_back(numbers[i]);  
    }
    for(int i = 0 ; i < Highest_digit.size()-1; i++)
    {
        for(int j = 0 ; j < Highest_digit.size()-1 ; j++)
        {
            if(Highest_digit[j] < Highest_digit[j+1])
            {
                tmpDigit = Highest_digit[j];
                Highest_digit[j] = Highest_digit[j+1];
                Highest_digit[j+1] = tmpDigit;
                tmpNum = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = tmpNum;
            }
            else if( Highest_digit[j] == Highest_digit[j+1])
            {
                if(numbers[j] < numbers[j+1] && (numbers[j] / 1000 + numbers[j] / 100 % 10 + numbers[j] / 10 % 10 + numbers[j] % 10)  != (numbers[j+1] / 1000 + numbers[j+1] / 100 % 10 + numbers[j+1] / 10 % 10 + numbers[j+1] % 10) )
                {
                    tmpNum = numbers[j];
                    numbers[j] = numbers[j+1];
                    numbers[j+1] = tmpNum;
                }
            }
        }
    }
    for(int i = 0 ; i < numbers.size(); i++)
    {
        str = to_string(numbers[i]);
        answer += str;
    }
    return answer;
}

• 반성하고 다시 짠 코드 ( 정렬 기준을 무엇으로 !! ) 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(string a,string b)
{
    return a + b > b + a;
}
string solution(vector<int> numbers) {
    string answer = "";
    vector<string> tmp;		// 숫자 벡터 요소들을 문자열로 바꾼 벡터

    for(int i = 0 ; i < numbers.size(); i++)
        tmp.push_back(to_string(numbers[i]));	// to_string()으로 숫자->문자열로
    sort(tmp.begin(),tmp.end(),compare);	// 정렬한다 ( 따로 정의한 compare()함수 기준으로 )
    for(auto i : tmp)	
        answer += i;	// 정답 문자열 변수에 정렬된 문자열벡터요소하나씩 붙이기
    if(answer[0] == '0')	// 모든 수가 "0" 일 경우
        return "0";
    return answer;
}

" 문제를 보고 !!정렬의 기준!! 을 어떻게 설정할지 고민하라. "

• [ CheckPoint ]

1.  to.string( 정수 ) 를 기억하자.
   = 정수를 문자열로 반환해주는 함수 ( #include <string> 필요 )
2. C++반복문은 ( 일반적 반복문, iterator이용, auto방식 3가지 정도는 기억 )
3. 나는 정렬의 기준을 깔끔하게 잡지 못하고, 숫자벡터의 요소들의 최고자리수를 먼저 구해서 정렬시키고, 최고자리수가 같은 경우 원래 숫자벡터끼리 모든 자리수를 구한 값이 같으면 그대로 두는 식....( 내가 설명하고도 뭔소린지 이해 못한다..) (생략)
4.  결론적으로, 숫자벡터를->문자열벡터로 변환한 벡터가지고서 각 원소들끼리 반복하면서 앞뒤 숫자끼리만 바꿔보면서 더 큰 숫자가 만들어지면 Swap하는 식으로 정렬한 다음, 정답 벡터에 넣어주면 끝나는 문제였다.

[ 참고자료 ]