오늘의 공부

programmers.co.kr/learn/courses/30/lessons/12924?language=cpp#

처음에 정확성은 맞는데 효율성에서 안되길래 대체 그럼 이건 어떻게 풀어야 하는건가?

했더니 더한 값이 n을 넘어갔을 때의 예외처리를 해주지 않아서 초과가 발생했던 것이었다.

 if(temp > n)
{
       break;
}

이 부분이다.. 

int solution(int n) {
    int answer = 0;
    int idx= 1;

    
    while(idx <= n)
    {
        int temp = 0;
        bool Find = false;
        for(int i=idx; i <= n; ++i)
        {
            temp += i;
            if( temp == n)
            {
                answer += 1;
                idx +=1;
                Find = true;
                break;
            }
            if(temp > n)
            {
                break;
            }
        }
        if(!Find)
        {
             idx +=1;
        } 
    }
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/12927

처음에는 이렇게 풀어서 정확성은 다 맞는데 효율성에서 시간이 초과 돼 실패했다.

그래서 뭐가 문제인지 찾아보니 이 문제는 우선순위큐를 이용해서 풀면 된다고 했다.

생각해보니 그랬다. 이전에 푼 방식같은 경우에는 제일 큰 값들을 하나씩 빼주려고 sort를 매번 루프때마다 했는데

그게 큰 요인이지 않았을까.

우선순위 큐를 하면 숫자가 제일 큰 게 제일 위로 오니까 매번 정렬을 할 필요가 없었다.

long long solution(int n, vector<int> works) {
    long long answer = 0;
    int works_size = works.size();
   int idx = 0;
    while( idx < n)
    {
        sort(works.begin(), works.end(), greater<int>());
        if(works[0]>0){
        works[0] -=1;
        }
        idx += 1;
    }
    
    for(int i=0;i<works_size;++i)
    {
        answer += works[i]*works[i];
    }
    return answer;
}

아래는 우선순위 큐를 이용해 수정한 방식이다.

long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue<int> pq;
    
    for(int i=0;i<works.size();++i)
    {
        pq.push(works[i]);
    }
    
    int idx = 0;
    while(n > idx)
    {
        int temp = pq.top();
        pq.pop();
        
        if(temp > 0)
        {
            temp -=1;
        }
        
        pq.push(temp);
        
        idx+=1;
    }

    for(int i=0;i<works.size();++i)
    {
        int temp = pq.top();
        answer += temp*temp;
        pq.pop();
    }
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/12946

하노이의 탑. 재귀를 이용해서 풀었다.

void hanoi(int n, int from, int by, int to, vector<vector<int>>& answer){
    if (n == 1)
        answer.push_back({from,to});
    else{
        hanoi(n - 1, from, to, by,answer);   
        answer.push_back({from,to});         
        hanoi(n - 1, by, from, to,answer);   
    }
}

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer;

    hanoi(n,1,2,3,answer);
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/42885

사실 결국 처음 고민했던 개념이 맞았다. 처음 값과 끝 값을 비교하면 됐다. 근데 굳이 erase를 할 필요없이 전에 풀었던 투 포인터 방식처럼 lidx와 ridx로 풀어줬더니 효율성까지 통과했다.

안에 for문도 써줄 필요가 없었다.

int solution(vector<int> people, int limit) {
	int answer = 0;
	sort(people.begin(), people.end()); // 정렬 
    
	// 제일 무거운사람하고 제일 가벼운 사람 태우기
	int lidx = 0;
	int ridx = people.size() - 1;
	while (lidx <= ridx)
	{
		if (people[lidx] + people[ridx] <= limit)
		{
			answer += 1;
			lidx += 1;
			ridx -= 1;
		}
		else if(people[lidx] + people[ridx] > limit){
			ridx -= 1;
			answer += 1;
		}

	}
	
	return answer;
}

해결하지 못했을 때 했던 고민들 ↓ 

효율성 테스트 4,5번은 맞는데 1,2,3번은 통과하지 못했다.

vector를 중간에 삽입,삭제 하면서 효율성이 떨어져서 그런가? 뭐가 문제일까..

보면 자꾸 효율성 검사 1,2,3번이 틀리는 경우가 좀 많은 것 같다. 테스트 케이스를 알면 어떤 부분을 잘못 생각하고 있는지 알 수라도 있을 것 같은데 프로그래머스는 이런 부분이 좀 아쉽다.

효율성 만점은 아니지만 생각했던 방법은 우선 사람들의 무게를 오름차순으로 정렬한 후에 

처음 값(제일 가벼움)과 마지막 값(제일 무거움)을 더한 값이 limit보다 큰 지, 작은지를 확인했다. 

만약 limit를 넘는다면 뒷 부분부터 앞으로 오면서 처음의 값과 비교했다.

그 후에 limit보다 작은 값을 찾게 됐다면 erase를 해줬는데 erase는 삭제 되면 capacity까지 줄어드니까

한 번 while문을 돌 때마다 다시 people 벡터의 size를 계산해주었다. 

그 후에 다 비교해봤는데 limit보다 작은 조합을 못찾았다면 이제 더이상 두 명씩 태울 수 없으므로 (cantTake == true) 남은 people 벡터의 사이즈만큼을 answer에 더해주고 반복문을 끝낸다. 

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    while(1)
    {
        bool cantTake = true;
        int people_cnt = people.size();
        if(people_cnt == 1)
        {
            answer += 1;
            break;
        }

        for(int i=people_cnt-1;i> 0 ; --i)
        {
            if(people[0] + people[i] <= limit)
            {
                cantTake = false;
                answer +=1;
                people.erase(people.begin() + i);
                people.erase(people.begin());
                break;
            }
        }
        if(cantTake)
        {
            answer += people_cnt;
            break;
        }
    }
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/42579

너무 복잡하게 풀어서 일단 풀기는 했지만 뭔가 찝찝하다.

IDE없이 풀려니까 어디가 문제인지도 안나오고 프로그래머스에서 풀 때 sort 오름차순, 내림차순 정렬 greater, less 추가하면 자꾸 오류나서 직접 비교 함수까지 추가했다.

map을 이용해서 장르 별로 총 몇 번 재생했는지 저장하고 (m)

그 m에 있는 정보를 정렬하기 위해서 또 re_m에다가 m의 키값과 value를 순서를 바꿔 저장했다.

이 때 map정렬을 따로 추가하는 게 귀찮아서 어차피 재생 횟수는 마이너스가 안되니까 -1을 곱해서 내림차순으로 저장했다.

그리고 나서 가장 많이 재생된 장르 순대로 하나씩 꺼내서 장르별로 횟수와 고유번호를 넣고 (v에) 정렬을 해줬다. 

iter를 2개까지만 끊어야 해서 idx변수를 추가로 써서 idx가 2면 break하게 하는 방식으로 answer에 넣어줬다. 

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    return a.first > b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    int song_cnt = genres.size();

    map<string, int> m;
    map<int, string> re_m;
    for(int i=0;i<song_cnt;++i)
    {
        m[genres[i]] += plays[i];
    }
    for(auto iter = m.begin(); iter != m.end(); ++iter)
    {
        re_m.insert(make_pair((iter->second)*-1, iter->first));
    }
    
    for(auto iter = re_m.begin(); iter != re_m.end();++iter)
    {
        vector<pair<int, int>> v;
        for(int i=0;i<song_cnt;++i)
        {
            if(genres[i] == iter->second)
            {
                v.push_back(make_pair(plays[i], i));
            }
        }
        sort(v.begin(), v.end(), cmp);
        
        int idx = 0;
        for(auto v_iter = v.begin(); v_iter != v.end() ; ++v_iter)
        {
            ++idx;
            answer.push_back(v_iter->second);
            
            if(idx >= 2)
            {
                break;
            }
        }
    }
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/43162

깊이 우선 탐색(DFS)의 방식으로 풀었다.

stack을 이용해서 갈 수 있는 점으로 진행하다가 갈 수가 없으면 stack을 pop해서 이전의 점으로 돌아간다.

bool (check)를 이용해 방문한 컴퓨터는 true로 바꿔 주었으며 

다시 이전으로 돌아가야 하는 조건을 설정하는 부분에서 (if (!Find) 부분) 스택이 비어있다면 하나의 네트워크 연결을 구한 것이므로 새로운 비어있는 컴퓨터를 찾아주어야 한다. 

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    bool check[201]= {};
    stack<int> s;
    s.push(0);
    check[0] = true;
    
    while(!s.empty())
    {
        int y = s.top();
        bool Find = false;
        for(int i=0;i<n;++i)
        {
            if(computers[y][i] == 1)
            {
                if(check[i] == false)
                {
                    check[i] = true;
                    s.push(i);
                    Find = true;
                    break;
                }
            }
        }
        
        if(!Find)
        {
            // 다시 이전으로 돌아가야함
            s.pop();
            if(s.empty())
            {
                answer+=1;
                // 다음 찾아야됨
                for(int i=0;i<n;++i)
                {
                    if(check[i] == false)
                    {
                        check[i] = true;
                        s.push(i);
                        break;
                    }
                }
            }
        }
    }
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/1845

3분만에 푼 문제이다.

중복된 포켓몬들 사이에서 뽑을 수 있는 가장 최대한 여러 종류의 포켓몬을 뽑는 문제였다.

그래서 map에 포켓몬의 종류를 저장하고 (중복이 불가능하므로) 최대 뽑을 수 있는 nums/2 의 값보다 종류가 더 많으면 nums/2만큼, 작으면 종류의 개수(max_choice_collect)만큼 뽑도록 했다.

int solution(vector<int> nums)
{
    int answer = 0;
    map<int, int> choice;
    int nums_size = nums.size();
    for(int i=0;i<nums_size;++i)
    {
        choice[nums[i]]+=1;
    }
    
    int max_choice_collect = choice.size();
    
    if(nums_size/2 <= max_choice_collect)
    {
        answer = nums_size/2;
    }
    else
    {
        answer = max_choice_collect;
    }
    return answer;
}

걱정되는게 모든 문제에 map을 이용하는 경우가 많아서 다른 방법으로 풀 수 있는데도 map으로만 풀려고 해서 시야가 좁아지는 건 아닐까 걱정된다. 

programmers.co.kr/learn/courses/30/lessons/68644?language=cpp

중복을 확인하기 귀찮아서 key의 중복이 안되며 자동으로 정렬해주는 map을 이용했다.

map의 key값에 더한값들을 다 저장해주고 (중복 없이) map의 key값들을 answer에 넣어주었다. 

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    map<int, int> value;

    int num_size = numbers.size();
    for(int i=0;i< num_size-1;++i)
    {
        for(int j=i+1;j<num_size;++j)
        {
            value[numbers[i]+numbers[j]]+=1;
        }
    }
    
    auto iter =  value.begin();
    auto iterend = value.end();
    
    for(;iter != iterend; ++iter)
    {
        answer.push_back(iter->first);
    }

    return answer;
}