[LV2] 귤 고르기

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

더보기 주의 , 코드에 관한 설명이 간략히 있지만 코드 내용 원문이 있으니 주의 할 것 

 

<나의 풀이(비추천)>

플로우차트

1.귤을 size 기준으로 오름차순 정렬

2.오름차순 정렬한 귤을 반복문을 돌려 사이즈별로 갯수를 체크( vector<int> tangerine_count 에 저장)
3.정렬되서 나온 벡터를 귤 갯수 기준으로 내림차순 정렬

4.상자에 k갯수만큼 담으면서 루프 ( k개를 초과할시 루프 탈출후 answer 반환)

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

using namespace std;

int solution(int k, vector<int> tangerine) 
{
    int answer = 0, count = 0; //count : 상자에 들어가는 귤의 갯수 
    vector<int> tangerine_count; // 귤을 사이즈별로 나눠서 갯수를 알게하는 벡터
      
    sort(tangerine.begin(), tangerine.end()); //귤을 오름차순 순으로 정렬 

    int compare_tagerine = tangerine[0];//정렬한 귤 첫번째를 선택(기준)

	//루프를 시작 ( 사이즈별로 갯수 확인 루프 )
    for (int i = 1; i < tangerine.size(); i++)
    {
    	//기준 귤 사이즈 와 i번째 귤의 사이즈가 같으면 count++
        if (compare_tagerine == tangerine[i])
        {
            count++;
        }
        else // 기존 귤 사이즈와 i번째 귤이 다름
        {
            tangerine_count.push_back(++count); // 자기자신을 count하면서 벡터에 추가
            compare_tagerine = tangerine[i];//기준을 i번째 귤로 교체
            count = 0;//count 초기화 
        }
    }
    tangerine_count.push_back(++count); // 마지막 원소count 가 안된경우 추가 
	//마지막 루프를 탈출할때 count가 안되는 경우가 있기 때문에 따로 추가
    
    //사이즈 별로 나눠놓은 귤갯수 벡터를 정렬 후 내림차순 정렬로 전환 
    sort(tangerine_count.begin(), tangerine_count.end());
    reverse(tangerine_count.begin(), tangerine_count.end()); // 내림차순 정렬로 바꾸기 

    int count_sum = 0; // 상자에 들어간 귤 
    int i = 0;//인덱스
	
    //k갯수를 초과하지 않으면 계속 상자에 담음 
    while (k > count_sum)
    {
        //사이즈 별로 가장 많은 귤을 먼저 상자에 담음
        count_sum += tangerine_count[i++];
        answer++;
    }


    return answer;
}

---

<다른사람의 풀이>

귤벡터가 [ 1,3,2,5,4,5,2,3]인 경우

 

1.첫번재 루프

t = 귤 벡터의 첫번째인덱스의 데이터값
v[ 1 - 1 ] ++; 

v[0]은 1의 값을 가지고 있게 된다.
이 벡터의 의미는 Size가 1 인 귤을 count했다는 의미이다.

 

2.두번째 루프

t = 귤 벡터의 두번째인덱스의 데이터값

v[3-1]++; //v[2]은 Size가 3인 귤을 의미,count한다

...

 

루프를 계속 반복하면

결과:

v[0] = 1 // Size = 1 인 귤이 1개 있음,

v[1] = 2  // Size = 2 인 귤이 2개 있음,

v[2] = 2  // Size = 3 인 귤이 2개 있음,

v[3] = 1  // Size = 4 인 귤이 1개 있음,

v[4] = 1  // Size = 5 인 귤이 2개 있음,

이런식으로 나눌수 있다. 

#include <bits/stdc++.h>

using namespace std;

int solution(int k, vector<int> tangerine)
{
    int answer = 0;
    int m = *max_element(tangerine.begin(), tangerine.end()); //귤벡터중 제일 큰 원소(size)를 호출
    //m = 귤 최대 size를 입력 ,기준이 됨 
    vector<int> v(m, 0); // m범위 만큼 0(초기값)으로 초기화
    
    //위에 내용 참조
    for(auto& t : tangerine)
    {
        v[t - 1]++;
    }
    
    //사이즈별로 나눈 귤을 내림차순 정렬
    //rbegin,rend로 역으로 정렬
    //Stable Sorting은 같은 것이 있는 경우 정렬하기 전의 순서가 유지되는 정렬 알고리즘이다
    stable_sort(v.rbegin(), v.rend());
    
    //사이즈 별로 나눈 벡터 사이즈만큼 루프를 돌림
    for(int i = 0 ; i < v.size() ; i++)
    {
        answer++;
        k -= v[i]; // 현재 인덱스의 갯수만큼 상자에 담음
        if(k <= 0) return answer; // 상자에 k개 만큼 초과시 answer값을 반환
    }
    
    return answer;
}