Merge 알고리즘

오늘은 MergeInterval 알고리즘을 풀어 보자

 

Interval 함수를 만들어서

start 값과

end 값을 선언한다

 

 

 

 

 

 

 

 

 

 

Interval 의 start값과 end 값 사이에 겹치는 구간이 있다면

하나로 병합해주는 알고리즘이다.

 

예를 들어서 [ 1, 3 ] , [ 2, 6 ]

두번째 Interval 의 start 값이 첫번째 Interval 과 겹친다.

 

그럴경우 이렇게 병합 하는 것을 반복 해야 한다 => [ 1, 6 ]

 

Interval 의 인스턴스들을 여러개 생성하고

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

인스턴스들을 담기 위한 그릇을 만든다.

 

 

 

 

 

 

 

 

 

 

 

 

 

배열에 모두 add 시켜주자.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

merge 함수로 intervals 을 보낸다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

isEmpty() 객체가 비어있다면

그대로 돌려보내라

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

답을 저장할 그릇

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

람다식을 이용해서 오름차순으로 정렬한다.

 

물론 순서를 바꾸면 내림차순

 

람다식은 예전에 배웠는데 함수를 그냥 진짜 필요한 부분만 골라서 쓰는

 

(a, b) -> a.start-b.start

 

오름차순 정렬 완료.

 

Collections 클래스는 Collection 인터페이스를 구현한 클래스에 대한 객체 생성, 정렬, 병합, 검색 등의 기능을 안정적으로 수행하도록 도와주는 역활을 한다

 

 

 

 

 

 

 

 

 

 

List, Set, Queue, Map 

 

 

 

 

 

 

 

 

 

 

 

 

intervals 이 정렬이 끝났잖아?

맨 처음에 있는 Interval 을 가지고 와서 before 에 저장해

 

여기서 before 은 비교 대상이 되는거야

 

첫번째 값

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

위에서는 i가 0부터 시작했지만

곰곰히 생각해보니 1부터 시작해도 될꺼 같아서 1로 바꾸었더니 잘된다

 

 

 

 

 

 

두번째 값 (배열 1번째) 을 가지고 와서

carrent 에 대입한다.

 

 

 

 

 

 

 

첫번째 end 값이랑 두번째 start 값이랑 

비교를 해서

 

첫번째 end 값이 더 크다면

둘이 중복되는 구간이 존재

그러면 병합을 해줘야 해

 

 

 

 

Math.max 함수를 사용해서

첫번째 end 두번째 end 중에서 큰 값을 

before 의 end 값으로 지정

 

 

 

 

 

 

다음 for 문을 실행 할 때 세번째에 있는 current가 if 문에 참이라면 연속 세번이 중복되는 구간이 있다는 것,

 

 

 

 

 

 

없다는 가정하에 bedore을 result 에 대입 해준다.

 

before 에는 current 로 reset

 

다음 비교 대상을 선택하기 위해서

 

 

 

 

 before 이 null 이 아니라면

즉, 마지막 값이 남아있을꺼 아니야!

 

 

마지막 값을 result에 다가 대입을 시켜줘야지!

 

 

 

결과는 이렇게 나오는데

정렬전에는 add 한 값 그대로 입력이 되어있고

 

 

정렬후에는 Collections 함수에 정의한 람다식으로 인해서

깔끔하게 오름차순으로 정의된다.

 

 

중복되는 start 값과 end 값이 잘 병합이 된것이 보인다.

이번 알고리즘은 확실히 이해 되었다. 신난다

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

package soobin.algorithm;

import java.util.*;

class Interval {

	int start;
	int end;

	Interval() {
		start = 0;
		end = 0;
	}

	Interval(int s, int e) {
		start = s;
		end = e;
	}
}

public class MergeInterval {

	public static void main(String[] args) {

		Interval in2 = new Interval(2, 6);
		Interval in1 = new Interval(1, 3);
		Interval in3 = new Interval(8, 10);
		Interval in4 = new Interval(15, 18);

		List<Interval> intervals = new ArrayList<>();
		MergeInterval a = new MergeInterval();

		intervals.add(in2);
		intervals.add(in1);
		intervals.add(in3);
		intervals.add(in4);

		List<Interval> list = a.merge(intervals);

	}

	public List<Interval> merge(List<Interval> intervals) {

		if (intervals.isEmpty()) {
			return intervals;
		}

		List<Interval> result = new ArrayList<Interval>();
		System.out.print("==============정렬전\n");
		print(intervals);
		// 람다 표현식으로 오름차순
		Collections.sort(intervals, (a, b) -> a.start - b.start);
		System.out.print("==============정렬후\n");
		print(intervals);

		Interval before = intervals.get(0); // [1, 3]

		for (int i = 0; i < intervals.size(); i++) {
			Interval current = intervals.get(i);

			if (before.end >= current.start) {
				before.end = Math.max(before.end, current.end);
			} else {
				result.add(before);
				before = current;
			}
		}

		if (!result.contains(before)) {
			result.add(before);
		}

		System.out.print("==============\n");
		print(result);
		return result;
	}

	public void print(List<Interval> list) {

		for (int i = 0; i < list.size(); i++) {
			Interval in = list.get(i);
			System.out.println(in.start + "," + in.end);
		}
	}
}