[LeetCode # 55 ~ 57] 문제 풀이

# 55. Jump Game

배열이 주어지고 배열의 각 값이 해당 위치에서 다음 인덱스로 Jump 가능한 범위라고 할 때 시작 인덱스부터 마지막 인덱스까지 점프가 가능할 지를 찾는 문제

 

이 문제는, 시작 인덱스부터 탐색을 하면 각 인덱스에서 점프를 뛰어 갈 수 있는 위치를 일일히 표시해야 해서 시간이 오히려 오래 걸리는 문제였다.

문제 해결이 안 되는 것은 아니지만, 이보다 빠르게 해결할 수 있는 방법이 끝 인덱스부터 탐색을 하는 방법이었다.

뒤에서부터 앞으로 탐색을 하면서 현재 위치에서 내가 저장하고 있는 위치까지 점프를 뛸 수 있으면, 저장하고 있는 위치를 현재 위치로 바꾼 다음 다시 앞으로 탐색을 진행하는 방식이다.

이 방식을 통해 O(N) 으로 탐색이 가능해졌고 문제의 해결을 빠르게 할 수 있었다.

 

bool canJump(vector<int>& nums) {
	int last = nums.size() - 1;
	for (int i = last - 1; i >= 0; i--) {
		if (i + nums[i] >= last) {
			last = i;
		}
	}
	return (last == 0);
}

# 56. Merge Intervals

Interval 들을 저장하는 배열이 주어졌을 때, 겹치는 Interval 들을 합치는 문제

 

일단 이 문제를 해결하기에 앞서 Interval 들이 서로 겹쳐지는 지를 확인하기 위해서 배열을 정렬을 한 후 문제를 해결했다.

결과를 저장할 배열을 새로 만들고, 앞에서부터 Interval 이 겹쳐지면 겹쳐진 범위의 최대를 저장하는 식으로 문제를 풀었다.

 

vector<vector<int>> merge(vector<vector<int>>& intervals) {
	sort(intervals.begin(), intervals.end());

	vector<vector<int>> ans;
	ans.push_back(intervals[0]);

	for (int i = 1; i < intervals.size(); i++) {
		if (ans.back()[1] >= intervals[i][0]) {
			ans.back()[1] = max(ans.back()[1], intervals[i][1]);
		}
		else {
			ans.push_back(intervals[i]);
		}
	}
	return ans;
}

# 57. Insert Intervals

겹치지 않는 Interval 들이 주어졌을 때, 새로운 Interval 을 삽입하는 문제

 

기존에 있던 Interval 에 겹쳐지는 영역이 있을 수 있기 때문에 해당 부분에 대한 처리가 필요한 문제였다.

새로운 Interval 과 겹치는 Interval 전까지는 그대로 저장하고, 겹치는 Interval 들에 대해서 하나의 Interval 로 만든 다음 해당 Interval 을 결과에 저장하고 남은 Interval 들을 저장하도록 해서 문제를 해결했다.

 

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
	vector<vector<int>> ans;

	int idx = 0;
	while (idx < intervals.size() && intervals[idx][1] < newInterval[0])
		ans.push_back(intervals[idx++]);

	while (idx < intervals.size() && intervals[idx][0] <= newInterval[1]) {
		newInterval[0] = min(newInterval[0], intervals[idx][0]);
		newInterval[1] = max(newInterval[1], intervals[idx][1]);
		idx++;
	}
	ans.push_back(newInterval);
	while (idx < intervals.size())
		ans.push_back(intervals[idx++]);

	return ans;
}