[프로그래머스] 징검다리 건너기

[프로그래머스] 징검다리 건너기

• https://programmers.co.kr/learn/courses/30/lessons/64062

접근

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_VAL = 2000000000;

int solution(vector<int> stones, int k) {
	int answer = 0;
	
    //k개의 연속된 0을 만들기 위해 징검다리를 건너야하는 최소 횟수
	int minVal = MAX_VAL;
	for (int i = 0; i <= stones.size() - k; ++i) {		
		int maxVal = 0;
        //연속된 k개의 구간 전부 검사
		for (int j = 0; j < k; ++j) {
			maxVal = max(maxVal, stones[i + j]);
		}
		minVal = min(minVal, maxVal);
	}
	answer = minVal;

	return answer;
}

int main() {
	vector<int> a;
	for (int i = 0; i < 10; ++i) {
		int input;
		cin >> input;
		a.push_back(input);
	}

	int k;
	cin >> k;

	cout << solution(a, k);
}

풀이

#include <iostream>
#include <vector>
#include <cstring>
#include <limits.h>
#include <algorithm>
using namespace std;

const int MAX_VAL = 2000000000;

int N;
vector<int> arr;

struct treeNode {
	int maxVal;
};

struct SegmentTree {
	vector<treeNode> tree;

	treeNode merge(treeNode left, treeNode right) {
		treeNode mergeNode;
		mergeNode.maxVal = max(left.maxVal, right.maxVal);
		return mergeNode;
	}

	treeNode buildRecursive(int node, int nodeLeft, int nodeRight) {
		if (nodeLeft == nodeRight) {
			treeNode mergeNode;
			mergeNode.maxVal = arr[nodeLeft];

			return tree[node] = mergeNode;
		}

		int mid = (nodeLeft + nodeRight) / 2;
		treeNode leftNode = buildRecursive(node * 2, nodeLeft, mid);
		treeNode rightNode = buildRecursive(node * 2 + 1, mid + 1, nodeRight);

		return tree[node] = merge(leftNode, rightNode);
	}

	void build() {
		tree.resize(N * 4);
		buildRecursive(1, 0, N - 1);
	}

	treeNode queryRecursive(int left, int right, int node, int nodeLeft, int nodeRight) {
		if (right < nodeLeft || nodeRight < left) {
			treeNode defaultNode;
			defaultNode.maxVal = 0;

			return defaultNode;
		}

		if (left <= nodeLeft && nodeRight <= right)
			return tree[node];

		int mid = (nodeLeft + nodeRight) / 2;
		treeNode leftNode = queryRecursive(left, right, node * 2, nodeLeft, mid);
		treeNode rightNode = queryRecursive(left, right, node * 2 + 1, mid + 1, nodeRight);

		return merge(leftNode, rightNode);
	}

	treeNode query(int left, int right) {
		return queryRecursive(left, right, 1, 0, N - 1);
	}

};


int solution(vector<int> stones, int k) {
	
    //전역 변수로 사용하기 위해 매개변수로 받은 stone 벡터 복사
	arr = stones;
	N = stones.size();
	
    //구간 최댓값을 저장하는 세그먼트 트리 만들기
	SegmentTree segmentTree;
	segmentTree.build();

	int answer = 0;
	
    //k개의 연속된 0을 만들기 위해 징검다리를 건너야하는 최소 횟수
	int minVal = MAX_VAL;
	for (int i = 0; i <= stones.size() - k; ++i) {	
        //연속된 k개의 구간 전부 검사
		treeNode res = segmentTree.query(i, i + k-1);
		minVal = min(minVal, res.maxVal);
	}
	answer = minVal;

	return answer;
}

📌참고자료

• [백준] 2042 구간 합 구하기
  https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-2042-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0