프로그래밍

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

[풀이]

DFS

#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,1,-1 };
int M, N;
bool visit[101][101];

int dfs(vector<vector<int>>& picture, int y, int x) {
	
	visit[y][x] = 1;

	int ret = 1;
	for (int i = 0; i < 4; i++) {
		int ty = y + dy[i];
		int tx = x + dx[i];
		
		if (ty < 0 || tx < 0 || ty >= M || tx >= N || visit[ty][tx]
			|| picture[ty][tx] != picture[y][x]) continue;

		ret += dfs(picture, ty, tx);
	}
	return ret;
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
	int number_of_area = 0;
	int max_size_of_one_area = 0;
	M = picture.size();
	N = picture[0].size();

	memset(visit, 0, sizeof(visit));

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (picture[i][j] == 0 || visit[i][j]) continue;
			number_of_area++;
			max_size_of_one_area = max(max_size_of_one_area, dfs(picture, i, j));
		}
	}


	vector<int> answer(2);
	answer[0] = number_of_area;
	answer[1] = max_size_of_one_area;
	return answer;
}

https://github.com/has2/Algorithm/blob/master/programmers/level2/%EC%B9%B4%EC%B9%B4%EC%98%A4%20%ED%94%84%EB%A0%8C%EC%A6%88%20%EC%BB%AC%EB%9F%AC%EB%A7%81%EB%B6%81.cpp

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/60057

[풀이과정]

1. 문자열 길이가 n인 경우 1~n/2으로 잘랐을 경우를 모두 구한다. (n/2를 넘게 자르는 것은 불가능)

2. 길이 len으로 자른 경우 길이가 len인 substring을 한개씩 비교하면서 앞의 것과 같으면 압축 가능한 개수를 저장하는 cnt를 1 더해준다.

3. 다른 문자열이 나오면 cnt의 길이 + len만큼을 ret에 더해준다.

 (cnt를 string으로 변환 후 size 구함, cnt가 1인 경우 더해주지 않음)

4. 다음 index (i+len)이 s의 길이를 초과하는 경우 더 이상 압축이 불가능 하므로 남아있는 것을 더해준다.

   (s2.size()만큼 더해주는 이유는 제일 마지막 부분 문자열은 len보다 작을수도 있기 때문에)

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

int sol(string& s, int len) {

	int ret = 0;

	int cnt = 1;
	for (int i = len; i < s.size() ; i += len) {
		string s1 = s.substr(i-len, len);
		string s2 = s.substr(i, len);
		//cout << s1 << "," << s2 << endl;
		if (s1 == s2) {
			cnt++;
		}
		else {
			ret += len;
			if (cnt != 1) ret += to_string(cnt).size();
			cnt = 1;
		}
		if (i + len >= s.size()) {
			ret += s2.size();
			if (cnt != 1) ret += to_string(cnt).size();
		}
		//cout << ret << endl;

	}
	return ret;
}

int solution(string s) {
	if (s.size() == 1) return 1;

	int answer = 10000;

	for (int i = 1; i <= s.size() / 2; i++) {
		answer = min(answer,sol(s, i));
	}

	return answer;
}

https://github.com/has2/Algorithm/blob/master/programmers/level2/%EB%AC%B8%EC%9E%90%EC%97%B4%20%EC%95%95%EC%B6%95.cpp

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42583

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
	int answer = 0;
	queue<pair<int,int>> q;

	int cnt = truck_weights.size();
	int cur_i = 0;
	int cur_w = 0;
	int time = 0;

	while (1) {

		if (cur_i < cnt && cur_w + truck_weights[cur_i] <= weight) {

			int qsize = q.size();
			while (qsize--) {

				auto truck = q.front();
				q.pop();
				if (truck.second != bridge_length) {
					q.push(make_pair(truck.first, truck.second + 1));
				}
				else {
					cur_w -= truck_weights[truck.first];
				}
			}
			
			cur_w += truck_weights[cur_i];
			q.push(make_pair(cur_i++, 1));
			time++;
		}
		else if (!q.empty()) {

			auto truck = q.front();
			q.pop();

			cur_w -= truck_weights[truck.first];

			int offset = bridge_length - truck.second+1;
			int qsize = q.size();
			while (qsize--) {
				truck = q.front();
				q.pop();
				q.push(make_pair(truck.first, truck.second + offset));
			}

			if (cur_i < cnt && cur_w + truck_weights[cur_i] <= weight) {
				cur_w += truck_weights[cur_i];
				q.push(make_pair(cur_i++, 1));
			}

			time += offset;
		}
		else {
			answer = time;
			break;
		}
		//printf("time : %d\n", time);
	}
	
	return answer;
}

int main() {

	int bridge = 2;
	int wi = 10;
	vector<int> a = { 7,4,5,6 };

	//int bridge = 100;
	//int wi = 100;
	//vector<int> a = { 10 };

	//int bridge = 1;
	//int wi = 6;
	//vector<int> a = { 6,6};

	printf("%d", solution(bridge, wi, a));

}

소스코드 : https://github.com/has2/Algorithm/blob/master/programmers/level2/%EB%A9%80%EC%A9%A1%ED%95%9C%20%EC%82%AC%EA%B0%81%ED%98%95.cpp