오늘의 공부

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

※ 절대적인 해답은 당연히 아니고 제 마음대로 풀었으니 참고용으로 봐주세요

어떻게 풀까 고민을 하다 location값을 언제 찾아줘야 하는지가 애매해서 queue에 index값을 넣어주기로 했다.

1. q를 만들고 거기에 priorities(vector<int>) 우선순위들이 들어있는 벡터의 사이즈만큼 값을 채워준다. 

	for (int i = 0; i < p_size; ++i)
	{
		q.push(i);
	}

2. while문을 돌면서 queue의 값을 체크

2-1. q의 제일 앞에 있는 index값을 빼온다 

(여기의 index값이란 priorities 벡터의 index를 가리키는 값임)

2-2. for문을 돌면서 현재의 index값(temp)과 i의 값을 비교해 나보다 더 큰 우선순위가 존재한다면 해당 인덱스 값이 맨 뒤로 가게 큐에서 빼서 다시 넣어준다. 

2-3. 만약에 인덱스 값의 변화가 일어나지 않았다면(=내가 제일 우선순위가 크다면) for문 안에서 IsChange가 true가 되지 않았을 것이므로 false이면 큐에서 인덱스를 빼주고 해당 인덱스값이 가리키는 우선순위 벡터의 값을 0으로 만들어준다. 

왜 0인지? 우선순위는 1~9로 0이면 어떠한 우선순위보다 작게 되므로 for문 안에서 체크 시 제외된다.

2-4. 만약 IsChange가 false일 때 temp값(현재 검사하고 있는 index값)이 location과 같다면 while문을 나와서 결과값을 리턴한다. 

int solution(vector<int> priorities, int location) {
	int answer = 0;
	int p_size = priorities.size();
	queue<int> q;

	for (int i = 0; i < p_size; ++i)
	{
		q.push(i);
	}

	while (1)
	{
		int temp = q.front();

		int IsChange = false;
		for (int i = 0; i < p_size; ++i)
		{
			if (i == temp)
			{
				continue;
			}
			if (priorities[temp] < priorities[i])
			{
				q.pop();
				q.push(temp);
				IsChange = true;
				break;
			}
		}

		if (!IsChange)
		{
			
			q.pop();
			priorities[temp] = 0;
			answer += 1;
			if (temp == location)
			{
				break;
			}

		}
	}

	return answer;
}

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

int solution(string s) {
	int answer = 1001;// s의 길이가 최대 1000이므로
	int s_size = s.length();

	string temp = "";
	int same = 1;

	if (s_size == 1)
	{
		return 1;
	}

	for (int i = 1; i<= s_size / 2; ++i)
	{
		string save = "";
		for (int j = 0; j < s_size; j+=i) {

			temp = s.substr(j, i);

			if (temp.length() % i != 0)
			{
				if (same != 1) {
					save += to_string(same);
				}
				save += temp;
				break;
			}
			string value = s.substr(i + j, i);
			if (temp == value)
			{
				// 같으면
				same += 1;
			}
			else
			{
				// 다르면
				if (same != 1) {
					save += to_string(same);
				}
				save += temp;
				same = 1;
			}
		}

		int temp_length = save.length();

		if (temp_length < answer)
		{
			answer = temp_length;
		}
		
	}

	return answer;
}

이.. 이게 생각보다 어려웠다. 이거 레벨2 맞나?

왜.. 왜이렇게 어렵지... 너무 어렵게 생각했나? 계속 고치고 고치다가 맞았는데 앞에 풀었던건 왜 틀렸는지 모르겠음

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

카카오 블로그의 해설과 질문하기 란을 보니 투포인터 방식으로 해결하라고 했다.

질문하기에서 어떤 분이 링크해주신 블로그 주소인데 깔끔하게 정리가 잘 돼 있어서 한번에 이해했다.

blog.naver.com/kks227/220795165570

vector<int> solution(vector<string> gems) {
	vector<int> answer;
	int gems_size = gems.size();
	int min_dist = 100001;

	unordered_map<string, int> list;

	unordered_set<string> s_temp;
	for (int i = 0; i < gems_size; ++i)
	{
		s_temp.insert(gems[i]);
	}
	int kind = s_temp.size();

	int idx_r = 0, idx_l = 0;


	while (1)
	{
		if (list.size() >= kind)
		{
			// 해당 key에 있는 value값을 하나 줄여준다.
			list[gems[idx_l]]--;

			if (list[gems[idx_l]] == 0)
			{
				// l의 포인터를 증가시킬 것이므로 지워준다.
				list.erase(gems[idx_l]);
			}
			// 포인터 증가
			idx_l++;
		}
		else if (idx_r == gems_size)
		{
			break;
		}
		else
		{
			list[gems[idx_r]]++;
			idx_r++;
		}

		if (list.size() == kind)
		{
			int temp = idx_r - idx_l;
			if (temp < min_dist)
			{
				answer.clear();
				answer.push_back(idx_l + 1);
				answer.push_back(idx_r);
				min_dist = temp;
			}
		}
	}

	return answer;
}

그리고 다시 풀면서 한 번 헤맸던 부분이 있는데 min_dist의 초기값을 설정할 때 gems의 size보다 큰 값을 줘야 한다. 그러니까 

gems의 size를 구해서 +1한 값을 주던지 아니면 gems는 최대 100000개가 들어올 수 있다고 했으니 그것보다 +1한 값을 설정해주거나. 그러지 않으면 r의 포인터값과 gem의 size를 비교해서 break를 하는 부분에서 마지막 부분에 break를 해버려 answer에 idx를 넣지 않는 경우가 발생한다. 구현방법은 여러가지이니까 다른 방식으로 구현했으면 상관없을 수도

바보 같은 그 전의 기록

vector<int> solution(vector<string> gems) {
	vector<int> answer;
	int gems_size = gems.size();
	int min_dist = gems_size;

// 중복없는 unordered로 
	unordered_map<string, int> list;
	unordered_set<string> s_temp;  
	for (int i = 0; i < gems_size; ++i)
	{
		s_temp.insert(gems[i]);
	}
	int kind = s_temp.size();

	auto iter = list.begin();

	int idx_r = 0, idx_l = 0;

	if (kind == 1)
	{
		answer.push_back(1);
		answer.push_back(1);
		return answer;
	}

	while (idx_r < gems_size && idx_l < gems_size)
	{
		iter = list.find(gems[idx_r]);
		if (iter != list.end())
		{
			iter->second += 1;
		}
		else
		{
			list.insert(pair<string, int>(gems[idx_r], 1));
		}

		if (list.size() < kind)
		{
			idx_r += 1;
		}
		else if (list.size() >= kind)
		{
			int temp = idx_r - idx_l;
			if (temp < min_dist)
			{
				answer.clear();
				answer.push_back(idx_l + 1);
				answer.push_back(idx_r + 1);
				min_dist = temp;
			}
			iter = list.find(gems[idx_l]);
			iter->second -= 1;
			if (iter->second == 0)
			{
				list.erase(iter);
			}
			idx_l += 1;
		}
	}
	return answer;
}

tech.kakao.com/2020/07/01/2020-internship-test/

카카오 블로그에 공식 해설이 있습니다!

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

stack을 사용해서 푸는 문제이다.

우선 인형뽑기 기계의 움직임. moves로 들어오는 정보들은 열을 기준으로 움직인다.

{0,0,0,0,0}, {0,0,1,0,3},{0,2,5,0,1 },{4,2,4,4,2},{3,5,1,3,1}

입력되는 값은 0번째 행, 1번째 행, 2번째 행, 3번째 행... 순으로 가로로 채워지게 된다.

그러므로 moves의 값이 1이라면 0번째의 열에 있는 0,0,0,4,3의 값 중 가장 위에 있는 4를 뽑아야 하며

moves의 값이 5라면 4번째 열에 있는 0,3,1,2,1의 값 중 3을 뽑아야 한다.

그렇게 뽑은 값은 stack을 이용한 basket에 넣어준다. 

basket에 정보를 넣어줄 때마다 바로 위에 있는 인형의 종류와 비교해 주었다.

문제의 조건은 터트린 인형의 '개수'를 구하는 것이므로 한 번 터트릴 때마다 두 개 씩 더해준다. 

인형의 종류가 같지 않다면 basket에 넣어준다. 

int solution(vector<vector<int>> board, vector<int> moves) {
	int answer = 0;

	stack<int> basket; 
	int cnt = moves.size();
	int board_width = board[0].size();

	for (int i = 0; i < cnt; ++i)
	{
		for (int j = 0; j < board_width; ++j)
		{
			if (board[j][moves[i] - 1] != 0)
			{
				int value = board[j][moves[i] - 1];

				if (!basket.empty() && basket.top() == value )
				{
					answer += 2;
					basket.pop();
				}

				else {
					basket.push(value);

				}

				board[j][moves[i] - 1] = 0;
				break;
			}
		}
	}
	return answer;
}

tech.kakao.com/2020/04/01/2019-internship-test/

문제 공식 해설! 

https://programmers.co.kr/learn/courses/30/lessons/42626

처음에는 아무생각없이 vector sort를 이용해서 풀었다.

정확성 테스트는 통과했지만 효율성 테스트에서 빨간색 잔치가 열려서 당황했다가 이 문제가 heap 문제라는 것을 깨닫고 priority_queue를 이용해서 풀었다.

priority_queue를 이용하면서 뒤에 compare 조건으로 greater를 이용해 오름차순으로 정렬되게 만들었다.

그렇게 해서 top을 했을 때 작은 숫자가 나오는 것을 이용했다.

int solution(vector<int> scoville, int K)
{
	int answer = 0;
	int scoville_size = scoville.size();

	priority_queue<int, vector<int>, greater<int>> t_scoville;

	for (int i = 0; i < scoville_size ; ++i)
	{
		t_scoville.push(scoville[i]);
	}

	while (1)
	{
		if (t_scoville.empty())
			return -1;

		if (t_scoville.size() == 1)
		{ 
			// 혹시 처음 조건 자체가 어떻게 될 지 모르니까 추가해 놓은 조건

			//음식이 하나인데 그 음식의 스코빌 지수가 K보다 작으면 -1
			if (t_scoville.top() < K)
				return -1;
		}

		// 가장 안 매운것 (temp_food1)과 그 다음으로 안 매운것(temp_food2)를 뽑아 스코빌 지수를 계산한다.
		auto temp_food1 = t_scoville.top();
		t_scoville.pop();
		auto temp_food2 = t_scoville.top();
		t_scoville.pop();

		int temp_scoville = temp_food1 + (temp_food2 * 2);

		t_scoville.push(temp_scoville);

		answer += 1;

		// 정렬된 상태의 scoville 지수. 만약 top의 값이 K보다 크다면 뒤의 것들은 당연히 더 클 것이므로 break한다.
		if (t_scoville.top() > K)
			break;
	}
	return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/42588

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> heights) {
	vector<int> answer(heights.size());

	for (int i = heights.size() - 1; i >= 0; i--) {

		for (int j = i - 1; j >= 0; j--) {
			if (heights[i] < heights[j]) {
				answer[i] = j+1;
				break;
			}
		}
	}
	return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/12980

#include <iostream>
using namespace std;

int solution(int n)
{
	int ans = 0;
	int remain_meter = n;
	for (int i = remain_meter; i > 0; i /= 2) {
		if (i % 2 == 1) {
			ans += 1;
		}
	}
	return ans;
}