오늘의 공부

https://programmers.co.kr/learn/courses/30/lessons/1829#

재귀를 이용한 DFS 방식으로 풀었다.

방문한 픽셀은 color값을 0으로 바꿔주고 방문 시에 해당 픽셀의 color값을 비교해 같은 부분인지 체크하는 방식으로 풀었다. 

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

vector<vector<int>> v;
int sizeN, sizeM;
int maxSize = 0;

bool dfs(int x, int y, int color)
{
	if (x <= -1 || x >= sizeN || y <= -1 || y >= sizeM)
	{
		return false;
	}

	if (v[y][x] != 0 && v[y][x] == color)
	{
		v[y][x] = 0;
		maxSize += 1;
		dfs(x - 1, y, color);
		dfs(x, y - 1, color);
		dfs(x + 1, y, color);
		dfs(x, y + 1, color);
		return true;
	}
	return false;
}


vector<int> solution(int m, int n, vector<vector<int>> picture) {
	vector<int> answer(2, 0);
	int number_of_area = 0;
	sizeN = n;
	sizeM = m;
	v = picture;

	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (dfs(j, i, picture[i][j]))
			{
				number_of_area += 1;
				answer[1] = maxSize > answer[1] ? maxSize : answer[1];
				maxSize = 0;
			}
		}
	}
	answer[0] = number_of_area;
	return answer;
}

 프로그래머스 홈페이지에서 그냥 풀다가 dfs 함수를 if문으로 체크하는 부분에 i와 j를 반대로 줘서 분명 맞는데 왜 값이 다르게 나오지? 하고 디버깅까지 찍어봤다ㅠ

[y][x] 방식으로 이용하는데 함수에 인자로 넘겨줄 때 x,y 순서로 넘겨주고 있어서 문제가 생겼던 것이다... 

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

앞서 풀었던 문제 중 땅따먹기와 개념이 비슷한 문제이다. 

int Find_max(int n1, int n2)
{
	return n1 > n2 ? n1 : n2;
}

int solution(vector<vector<int>> triangle) {
	int answer = 0;

	int triangle_size = triangle.size();

	for (int i = 0; i < triangle_size-1; ++i)
	{
		for (int j = 0; j < triangle[i+1].size(); ++j)
		{
			if (j < 1 || (j == triangle[i + 1].size() - 1))
			{
				// 왼쪽 끝// 오른쪽 끝 
				if (j < 1)
				{
					triangle[i + 1][j] += triangle[i][0];
				}
				else
				{
					triangle[i + 1][j] += triangle[i][j-1];
				}
				
			}
			else
			{
				triangle[i + 1][j] += Find_max(triangle[i][j - 1], triangle[i][j]);
			}
		}
	}
	
	answer = triangle[triangle_size - 1][0];
	for (int i = 1; i < triangle[triangle_size - 1].size(); ++i)
	{
		if (answer < triangle[triangle_size - 1][i])
		{
			answer = triangle[triangle_size - 1][i];
		}
	}

	return answer;
}

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

처음에는 단순히 뇌빼기를 하고 풀어도 되는 쉬운 문제인 줄 알고 이전값만 더했는데 테스트에서 실패가 뜨는 것을 보고 직감했다. 이게 아니구나.

그래서 다른 방식으로 풀었다. 

원래는 각 행에 가장 큰 값을 더하되 이전 행에서 더했던 인덱스(열)면 다른 최댓값을 찾았었다.

그런데 생각해보니 반례가 있었다.

이렇게 극한으로 치닫는 예제에서 4->8->12를 하고나면 마지막행에서 1000을 더할 수가 없게 된다.

그래서 각 행에 이전 행의 최댓값을 더한 후에 비교해줬다. 

int find_max(int n1, int n2, int n3)
{
	int temp = n1;

	if (temp < n2)
	{
		temp = n2;
	}
	if (temp < n3)
	{
		temp = n3;
	}
	return temp;
}


int solution(vector<vector<int> > land)
{
	int answer = 0;
	int m_size = land.size();

	for (int i = 0; i < m_size-1; ++i)
	{
		land[i+1][0]+= find_max(land[i][1], land[i][2], land[i][3]);
		land[i+1][1]+= find_max(land[i][0], land[i][2], land[i][3]);
		land[i+1][2]+= find_max(land[i][0], land[i][1], land[i][3]);
		land[i+1][3]+= find_max(land[i][1], land[i][2], land[i][0]);
	}

	answer = land[m_size - 1][0];
	for (int i = 1; i < 4; ++i)
	{
		if (answer < land[m_size - 1][i])
		{
			answer = land[m_size - 1][i];
		}
	}
	return answer;
}

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

효율성 테스트까지 통과하기 위해서는 Stack을 이용해서 풀어야 한다.

괄호 { } 맞추기 문제, 그리고 카카오 테스트 중에 크레인 인형 뽑기와 비슷했던 문제였다.

stack의 top과 s의 idx값을 비교했을 때 같으면 stack의 top을 pop하고 같지 않다면 s의 idx값을 현재 stack에 넣어준다. 

#include <iostream>
#include<string>
#include <stack>
using namespace std;
int solution(string s)
{
	int answer = 0;
	stack<char> Stack;

	int idx = 0;

	Stack.push(s[idx++]);

	while (idx < s.size())
	{
		if (Stack.empty())
		{
			Stack.push(s[idx++]);
		}
		char s_top = Stack.top();

		if (!Stack.empty() && s_top == s[idx])
		{
			Stack.pop();
		}
		else
		{
			Stack.push(s[idx]);
		}
		idx += 1;

	}

	if (Stack.empty())
		answer = 1;
	else
		answer = 0;

	return answer;
}

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;
}