250509 12일차

오늘은 독립준비를 위해 방을 알아보고 하느라 시간이 좀 많이소비되었다..

그래도 뭔가 시간내서 해보자 하고 

코테문제 3가지를 풀었다

---

프로그래머스 / lv3 입국심사 / 이분탐색
입국심사관 N명이 각 심사 걸리는시간이 들어가있고 M명이 심사를 받을때 가장 빠른 시간을 구하는 문제

이분탐색은 쉽게 생각했었는데
문제를 이분탐색의 범위를 풀어내는게 어려웠다
결국 시간은 1초~제일오래걸리는 심사관의 시간 * M명의 범위로 설정했다.
시간의 중간 값일때 기준 각 심사관이 몇명을 처리 할수있는지가 핵심이었던것같다.
그 처리 인원수가 M명보다 많으면 Ok 그시간이 가장 짧은걸 계속 고르면 됐던 문제

long long solution(int n, vector<int> times) 
{
	
	long long answer = 0;
	int timeSize = times.size();
	long long  max = 0;
	for (int i = 0; i < timeSize; ++i)
		if (times[i] > max)
			max = times[i];

	long long right = n * max;
	answer = right;
	long long left = 1;
	
	while (left <= right)
	{
		vector<int> temp = times;
		long long mid = (left + right) / 2;
		long long solved = 0;
		long long processTime = 0;
		for (int i = 0; i < timeSize; ++i)
		{
			solved += (long long)(mid / temp[i]);
			if (processTime < (long long)(mid / temp[i]) * temp[i])
				processTime = (long long)(mid / temp[i]) * temp[i];
		}
		if (solved >= n && processTime < answer)
		{
			answer = processTime;
		}

		if (solved > n)
			right = mid - 1;
		else
			left = mid + 1;
	}

	return answer;
}

 

---

프로그래머스 / lv2 다리를 지나는트럭  / 스택,큐
처음엔 어제 풀었던 문제중 다른사람 풀이처럼 한번의 루프로 가능하지 않을까?하면서
풀었는데 테스트코드 통과하길래 채점했지만 광탈!!
좀 생각을 해봤는데도 꽤어려웠다
큐를 쓰면서 2중큐로 시간을 관리할까도 생각해봤는데 결국 실패...
다른 사람 풀이를 참조했다..
Queue에 빈객체(0)을 넣으면서 시간 처럼 처리하는게 신기한 코드였다..

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
	int answer = 0;
	int size = truck_weights.size();

	int idx = 0;
	queue<int> bridge;
	int bw = 0;
	while (idx < size )
	{
		++answer;
		if (bridge.size() == bridge_length)
		{
			bw -= bridge.front();
			bridge.pop();
		}

		if (truck_weights[idx] + bw <= weight)
		{
			bridge.push(truck_weights[idx]);
			bw += truck_weights[idx];
			idx++;
			if (idx >= size)
				answer += bridge_length;
		}
		else
			bridge.push(0);

	}

	return answer;
}

 

---

프로그래머스 / lv2 타겟 넘버 / DFS,BFS
내용은 N개의 수와 타겟번호 M이 있는데

N개의 모든 + -  경우에수에서 M을 만족하는 개수를 찾는거였다

DFS문제라고 되어있긴했지만,
얼추보니까 반복횟수가 2의 N승이 왔다

그냥 뭔가 비재귀로 풀고싶어서
Bit연산을 이용해
+++ > 000
++- > 001
이런느낌이지 않을까 해서 
N곱하기 2의 N승이지만 
시간제약이 없었기에 통과!
그리고 다른사람풀이를 보니까
역시나 재귀로 풀었다 DFS함수 매개변수만 참고하여 다시풀었다.

void DFS(vector<int>& numbers, int& target, int sum, int depth, int& answer)
{
	if (depth < 0)
	{
		if (sum == target)
			answer++;
		return;
	}


	DFS(numbers, target, sum+numbers[depth], depth -1,answer);
	DFS(numbers, target, sum-numbers[depth], depth -1,answer);
}


int solution(vector<int> numbers, int target) 
{
	//다른사람 함수만 참고하기
	int answer = 0;
	int size = numbers.size();
	DFS(numbers, target, numbers[size-1], size-2, answer);
	DFS(numbers, target, -numbers[size-1], size-2, answer);

	return answer;
	//내풀이
	//int answer = 0;

	//int size = numbers.size();
	//int trycount = 1 << size;

	//for (int i = 0; i < trycount; ++i)
	//{
	//	int sum = 0;
	//	for (int j = 0; j < size; ++j)
	//	{
	//		int bit = (1 << j);
	//		if ((i & bit) == bit)
	//			sum += numbers[j];
	//		else
	//			sum -= numbers[j];
	//	}
	//	if (sum == target)
	//		answer++;
	//}
	//return answer;
}

생각보다 간단히 풀었다.