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입니다." 이다.

• [ 장르 ] STACK
• [ 문제 ]

[#42584] 주식가격

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

programmers.co.kr

• My Code

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int NoDownDuring;		// 해당시점 이후, 주식가격 낮아지기까지 시간체크
    
    answer.assign(prices.size(), 0);		// 주식 수 만큼 정답 벡터 0으로 초기화
    for(int i = 0 ; i < prices.size(); i++)
    {
        NoDownDuring = 0;		// 시간측정은 현 시점부터 0부터 시작
        for(int j = i + 1; j < prices.size(); j++)	
        {
            NoDownDuring++;
            if(prices[i] > prices[j])	// 현 시점 주식에서 뒤에 주식중에 현 시점 주식보다 낮은 시점
                break;
        }
        answer[i] = NoDownDuring;		// 현 시점에서 주식이 낮아지기까지 시간 벡터에 삽입
    }
    return answer;
}

• Another Code

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> prices)
{
    vector<int> answer(prices.size());
    stack<int> s;
    int size = prices.size();

    for (int i = 0; i<size; i++)
    {
        // 스텍이 차있으면서 가격이 떨어지기 시작하면
        while (!s.empty() && prices[s.top()] > prices[i])
        {
            answer[s.top()] = i - s.top();
            s.pop();
        }

        // 가격이 올라갈때동안 스텍에 넣음
        s.push(i);
    }

    // 스텍에 남은것들을 계산해줌
    while (!s.empty())
    {
        answer[s.top()] = size - s.top() - 1;
        s.pop();
    }

    return answer;
}

[ CheckPoint ]

• 문제 의도만 파악하면, 문제는 어렵지 않은 문제다.
• 주된 장르는 스택인데, 나는 풀고나니 스택을 안았다. 스택을 써야하는 발상이 나지 않았다.
• 풀고나서보니, 최악의 상황 prices 벡터크기가 10000개이고, 모든 주식 가격이 같다면, 총 실행시간은 O(n^2)시간이 될 수 있다. 이는 굉장히 비효율적일 수 있는데, 이 문제는 이 사항은 수용하기로 했나보다.
• 다른 사람의 코드를 보면, 반복문이 2개가지만, 스택을 잘 활용해서 적어도 O(n^2)의 시간은 걸리지 않다는 것을 알 수있다.

• [ 장르 ] Queue
  [ Question ]

[#42583] 다리를 지나가는 트럭

모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

programmers.co.kr

• My Code

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0,cur_Weight = 0,truck_Count;
    queue<int> Crossed;		// 지나간 트럭
    queue<int> Passing;		// 다리위에 트럭
    vector<int> waitBridge;	// 다리위 대기중인 각 트럭당 대기시간

    truck_Count = truck_weights.size();	// 초기 트럭수 변수에 저장
    while(true)
    {
        answer++;		// 단계 카운트
        if(!waitBridge.empty())	// 다리위에 트럭이 있으면
            for(auto iter = waitBridge.begin(); iter != waitBridge.end(); iter++)
                *iter -= 1;		// 다리위에 트럭큐에 끝까지 대기시간 -1감소

        while((!waitBridge.empty()) && waitBridge.front() == 0)	// 다리위에 트럭이있고, 다리끝까지 왔다면 ( == 대기시간 다 됬다면 )
        {
            Crossed.push(Passing.front());		// 현재 다리위에 맨 앞에 트럭, 다리를 건넜음큐에 push 
            cur_Weight -= Passing.front();		// 현재 다리위에 중량무게 이제 나갈 트럭무게만큼 차감 업데이트
            Passing.pop();						// 이제서야 다리위에 맨 앞 트럭 pop
            waitBridge.erase(waitBridge.begin());	// 대기시간 벡터도 맨앞에요소 하나삭제
        }
        if(Crossed.size() == truck_Count)	// 초기의 다리건너기전 트럭수랑, 건넌 트럭수 큐의원소의 수가 같으면 탈출
            break;
        if((!truck_weights.empty()) && weight >= cur_Weight + truck_weights.front())	// 매 단계마다, 다리를 건너기 전 트럭이 존재하고, 현재 다리위에 있는 트럭의 무게의 합과 지금 들어갈
        {																				// 트럭의 무게를 합한 것이, 다리의 하중보다 작거나 같다면 
            Passing.push(truck_weights.front());	// 다리위에 트럭추가
            cur_Weight += truck_weights.front();	// 추가된 트럭 무게만큼 총 무게 증가
            truck_weights.erase(truck_weights.begin());	// 다리건너기전 트럭원소는 삭제
            waitBridge.push_back(bridge_length);	// 새로 대기시간 (다리길이만큼) 벡터에 맨뒤에 삽입
        }
    }
    return answer;
}

[ CheckPoint ]

• 문제를 풀다 마주친 첫번째 고민은, 다리위에 적재된 트럭마다 다리길이만큼 대기시간을 가지게되고, 각각 들어온 시점이 다를 수 있는데 이걸 어떻게 컨트롤 해야할까 ?
• 두번째 고민은, 오류에서 발견 됬는데, 다리위에 있던 트럭을 다리를 끝까지 다와서 건너간트럭큐에 push하거나, 다리에 적재되기전에 기존의 트럭 vector에 트럭을 다리위에 적재할때  vector에 트럭이 존재하는지를 먼저 체크를하고 뭔가를 해서 잘못된
  IndexError를 피할 수 있다.

• [ 장르 ] Stack / Queue
• [ Question ]

[#42586] 기능개발

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

programmers.co.kr

• My Code

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int CurFrontIndex = 0;	// 현재 제일 앞 우선순위 인덱스
    int releaseCount = 0;	// 현 시점 배포할 작업 수

    while(true)
    {
        while(progresses[CurFrontIndex] < 100)	// 현재 우선순위 인덱스 작업이 100% 될때까지
        {
            for(int i = CurFrontIndex ; i < progresses.size(); i++)	// 모든 작업, 스피드만큼 증가
                progresses[i] += speeds[i];
        }
        
        while(progresses[CurFrontIndex] >= 100 )	// 현재 우선순위 인덱스의 작업이 일단 100%끝난 시점에서 다음 작업으로 넘어가면서 다른 100%끝난 작업이 있는지 전진
        {
            releaseCount++;
            CurFrontIndex++;
            if(CurFrontIndex >= progresses.size())
                break;
        }
        if(releaseCount != 0)	// 한번 순회하면서 100% 완성된 작업 수 카운트를 정답 벡터에 push !
        {
            answer.push_back(releaseCount);
            releaseCount = 0;
        }
        if(CurFrontIndex >= progresses.size())	// 마지막 작업까지 끝나면 탈출
            break;
    }
    return answer;
}

• Better Code

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

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)		// 반복문 하나로 끝 
    {
        day = (99 - progresses[i]) / speeds[i] + 1;	// 매 작업마다 한 작업당 스피드로 나누면 몇일이 소요할 지 바로 나오겠지

        if (answer.empty() || max_day < day)
            answer.push_back(1);
        else
            ++answer.back();		// 이 부분이 포인트라 했다. ++answer.back() ..

        if (max_day < day)
            max_day = day;
    }

    return answer;
}

" 나는 정작 STACK을 잘 구현할려고 한 것인가 ? "

• [ CheckPoint ]

1.  이 문제의 작은 포인트는 작업이 100프로가 되면 작업을 중단하고 배포를 해야 한다는 것. 혹시 본인의 테스트 케이스가 대부분 맞는데 1,2개가 틀린다면 이 부분을 체크 해볼 것.
2. 나의 로직은 맨 앞 작업부터 끝나기까지 맨 끝 작업까지 한번 씩 speed만큼 작업의 진도를 증가 시키는 것인데, 만약 기존 작업량이 모두 낮고
   (10% 미만 ) speed는 각각 전부 1일 경우, 나의 알고리즘은 작업시간이 오래걸릴 것이다.
3. 좀 더 좋은 방법은 Better Code의  한 작업의 단계에서
   (99-현재작업의 량) / 작업의 speed + 1 = 남은 작업 일 수가 측정 됨을 생각하면 연산 한번의 이런 과정이 끝난다.
4. 아직 ++answer.push_back(1)의 의미를 정확히 모르겠는데 이해를 해봐야 겠다. 혹시 먼저 의견을 줄 수 있다면 조언을 주길 바란다.

• [ 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하는 식으로 정렬한 다음, 정답 벡터에 넣어주면 끝나는 문제였다.

[ 참고자료 ]

• [ LEVEL 2 ] [ 스택 / 큐 ]
• [ Qusetion ]

[ LEVEL 2 ] [ 스택/큐 ] 프린터

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

programmers.co.kr

• My Code

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0,tmp,i,j;
    while(true)
    {
        for(i = 1; i < priorities.size(); i++)	// 첫번째 우선순위기준으로 그 다음인덱스부터 우선순위벡터 끝까지 조사
        {
            if(priorities[0] < priorities[i])	// 첫번째 우선수위보다 더 큰 우선순위있으면
            {
                tmp = priorities[0];	// 첫번째 우선순위 담아두고
                for(j = 0 ; j < priorities.size()-1 ; j++)	// 뒤에 원소를 하나씩 앞으로 댕김
                    priorities[j] = priorities[j+1];
                priorities[j] = tmp;	// 첫번째 우선순위는 벡터 맨 뒤에 위치
                break;
            }
        }
        if(priorities.size() == i)	// 첫 번째 우선순위가 가장 큰 우선순위일 때
        {
            answer++;	// 우선순위벡터에서 pop()개념으로 정답 우선순위 순번 1증가
            for(j = 0 ; j < priorities.size()-1 ; j++)	// q.pop()개념으로 뒤에 원소들 하나씩 댕김
                priorities[j] = priorities[j+1];
            priorities[j] = 0;	// pop()된 우선순위를 0 (의미없는 수)으로 지정
            if(location == 0)	// 중복된 수들이 있었을 때를 고려. 같은 수중에 내가 원한 우선순위를 체크
                break;
        }
        location--;	// 내가 원하는 우선순위 차례 조작
        if(location < 0)	// 맨뒤로 내가 원하는 우선순위가 벡터에 갔을때 
                location = priorities.size() - 1;	// 맨뒤 인덱스로 변경
    }
    return answer;
}

• Best Code

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

using namespace std;

int solution(vector<int> priorities, int location) {
    queue<int> printer;                         //queue에 index 삽입.
    vector<int> sorted;                         //정렬된 결과 저장용
    for(int i=0; i<priorities.size(); i++) {
        printer.push(i);
    }
    while(!printer.empty()) {
        int now_index = printer.front();
        printer.pop();
        if(priorities[now_index] != *max_element(priorities.begin(),priorities.end())) {
            //아닌경우 push
            printer.push(now_index);
        } else {
            //맞는경우
            sorted.push_back(now_index);
            priorities[now_index] = 0;
        }
    }
    for(int i=0; i<sorted.size(); i++) {
        if(sorted[i] == location) return i+1;
    }
}

" C++의 큐(Queue) STL 사용에 익숙해지자 "

• [ CheckPoint ]

1.  우선 <queue> STL은 <algorithm> 헤더가 필요하다.
2.  queue는 정렬이 따로 없다.
3.  사용가능한 주 함수로는 다음이 있다.

1.  문제에서 큐에서 최대값을 순회하면서 구하는 방법을 몰랐다.
2.  *max_element OR *min_element ( 객체.begin() , 객체.endl() )
   를 기억하자.
3. 함수는, 배열이나 벡터 큐 등등 (문자열도 됨) 에서 시작과 끝 사이에서 각각 최대값, 최소값을 반환한다.
   다만 값이 아닌 주소를 반환하기 때문에 함수앞에 참조연산자를 붙인다.

• Qusetion

프로그래머스 #12943

콜라츠 추측 : 1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.

programmers.co.kr

• My Code

#include <string>
#include <vector>

using namespace std;

int solution(int num) {
    int answer = 0;
    long long n = num;
    for(int i = 0 ; i < 500; i++)
    {
        if(n == 1)
            break;
        if(n % 2 == 1)
            n =  3 * n +1;
        else
            n /= 2;
        answer++;
    }
    if(answer >= 500)
        return -1;
    else
        return answer;
}

• Better Code

#include<iostream>
using namespace std;

int collatz(int num)
{
    int answer = 0;
  cout<< num <<"\n";
  while(answer++ <= 500){
    num = num%2 ==0 ? num/2 : num*3+1;
    if(num == 1) break;
  }

    return answer > 500 ? -1 : answer;
}

int main()
{
    int testCase = 6;
    int testAnswer = collatz(testCase);

    cout<<testAnswer;
}

" int 정수의 범위를 파악하자. "

• CheckPoint

• int 형 n의 정수형 수용범위를 확인하고, 필요할시 long이나 long long
• > 형을 사용할 생각을 하자.
• 이제는 짝수or홀수로 조건문의 조건을 작성할 때 if( n & 1 ) 형태를 기억.
  %연산자보다 비트연산자가 처리속도가 빠르다.
• 3항연산자를 잘 쓰면 코드가 짧아진다.