Sort - [Java]

노력하는 배짱이·2021년 4월 4일
Java
0

코딩테스트 준비 - Java

목록 보기
5/9

Sort

개념

1) compareTo()
2) comparator
3) PriorityQueue -> O(logN)
4) BinarySearch -> O(logN)

1) compareTo()

A.compareTo(B)
1. A == B : 0
2. A > B : 1
3. A < B : -1

3번처럼 음수일 때는 오름차순으로 한다는 의미

2) Comparator

Comparaotr<Interval> Comp = new Comparator<Interval>() {
    @Override
    public int compare(Interval o1, Interval o2) {
    	return o1.end - o2.end;
    }
};

문제

1. compareTo()

버전 번호 version1, version2를 비교하여 다음과 같치 반환한다.
1. version1 < version2 : -1 반환
2. version1 > version2 : 1 반환
3. version1 = version2 : 0 반환

Input : version1 = "8.5.2.4", version2 = "8.5.3"
Output : -1

풀이

  1. '.'으로 구분되어진 수를 문자열로 넣어준다. -> split을 이용하여 '.'을 기준으로 나누어 저장
  2. 앞자리 수부터 비교한다.
  3. 0이 나오면 동일하기 때문에 0이 아닐 때를 확인한다.
  4. "1.0.1" 과 "1" 이렇게 주어지는 경우가 있기 때문에 길이가 벗어나는 부분은 0으로 채워줘서 비교한다.
    즉, 1,0,1 과 1,0,0 이 둘을 비교하는 것이다.

소스

public class Q1 {

	public static void main(String[] args) {
		String version1 = "8.5.2.4", version2 = "8.5.3";

		// String version1 = "1.0.1", version2 = "1";

		System.out.println(solve(version1, version2));
	}

	public static int solve(String v1, String v2) {
		// 1. 각 문자열을 "."을 기준으로 숫자만 저장
		String[] v1Arr = v1.split("\\.");
		String[] v2Arr = v2.split("\\.");

		// 2.
		int len = Math.max(v1Arr.length, v2Arr.length);

		for (int i = 0; i < len; i++) {
			Integer v1Int = i < v1Arr.length ? Integer.parseInt(v1Arr[i]) : 0;
			Integer v2Int = i < v2Arr.length ? Integer.parseInt(v2Arr[i]) : 0;

			int comp = v1Int.compareTo(v2Int);

			if (comp != 0) {
				return comp;
			}
		}

		return 0;

	}

}

2. Comparator

특정한 객체의 값을 비교하여 Sorting하는 문제

start, end 가 주어졌을 때, 겹쳐지는 부분은 합치고 그렇지 않은 것은 그대로 반환

Input : [[1,3], [2,6], [8,10], [15,18]]
Output : [[1,6], [8,10], [15,18]]
설명) [1,3] 과 [2,6]은 서로 겹쳐지는 부분이 존재하여 [1,6]으로 합쳐진다.

풀이

  1. 주어지는 start 와 end 의 값을 start를 기준으로 정렬한다.
    -> 정렬할 때 3가지 방법을 이용할 수 있다.
  2. 앞(before)의 end가 현재(current) start 보다 크거나 같으면 앞의 end를 둘 중 제일 긴 end로 갱신한다.

1번 방법)

Collections.sort(intervals, (a, b) -> a.start - b.start);

2번 방법)

public static Comparator<Interval> comp = new Comparator<>() {
		@Override
		public int compare(Interval o1, Interval o2) {
			return o1.start - o2.start;
		}
	};

3번 방법)

public static Comparator<Interval> comp2 = new Comparator<>() {

		@Override
		public int compare(Interval o1, Interval o2) {
			if (o1.start < o2.start) {
				return -1;
			} else if (o1.start > o2.start) {
				return 1;
			} else {
				return 0;
			}
		}

	};

소스

import java.util.*;

class Interval {
	public int start;
	public int end;

	public Interval(int start, int end) {
		this.start = start;
		this.end = end;
	}
}

public class Q2 {

	public static void main(String[] args) {
		Interval in1 = new Interval(1, 3);
		Interval in3 = new Interval(2, 6);
		Interval in2 = new Interval(8, 10);
		Interval in4 = new Interval(15, 18);

		List<Interval> intervals = new ArrayList<>();
		intervals.add(in1);
		intervals.add(in2);
		intervals.add(in3);
		intervals.add(in4);

		List<Interval> list = merge(intervals);
		print(list);

	}

	public static List<Interval> merge(List<Interval> intervals) {
		if (intervals.isEmpty()) {
			return intervals;
		}

		// 1. start를 기준으로 정렬
//		Collections.sort(intervals, (a, b) -> a.start - b.start);
		Collections.sort(intervals, comp);

		List<Interval> result = new ArrayList<Interval>();
		Interval before = intervals.get(0);

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

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

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

		return result;

	}

	public static Comparator<Interval> comp = new Comparator<>() {

		@Override
		public int compare(Interval o1, Interval o2) {
			return o1.start - o2.start;
		}

	};

	public static Comparator<Interval> comp2 = new Comparator<>() {

		@Override
		public int compare(Interval o1, Interval o2) {
			if (o1.start < o2.start) {
				return -1;
			} else if (o1.start > o2.start) {
				return 1;
			} else {
				return 0;
			}
		}

	};

	public static void print(List<Interval> list) {
		for (Interval i : list) {
			System.out.println(i.start + " " + i.end);
		}
	}

}

3. PriorityQueue

자바의 PriorityQueue 는 MinHeap으로 구성됨

양의 정수 길이의 두 막대기를 연결할 때 x 와 y의 비용을 지불한다.
이런식으로 연결하여 스틱이 하나 남을 때 까지 모든 스틱을 연결하는 최소 비용을 반환해라.

Input : 스틱 = [1, 8, 3, 5]
Output : 30
설명)
1. 1 + 3 = 4 -> [4, 8, 5]
2. 4 + 5 = 9 -> [9, 8]
3. 9 + 8 = 17 -> [17]
총 비용 : 4 + 9 + 17 = 30

풀이

  1. PriorityQueue에 sticks 요소 하나씩 넣는다.
  2. pq.size() 가 1 보다 클때까지 while문을 돌려 합을 구한다.
  3. sum에 누적하면서 두 개의 수를 더한 값은 다시 큐에 넣는다.
  4. 구해진 합을 반환한다.

소스

import java.util.*;

public class Q3 {

	public static void main(String[] args) {
		int[] sticks = { 1, 8, 3, 5 };

		System.out.println(solve(sticks));
	}

	public static int solve(int[] sticks) {
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

		for (int i : sticks) {
			pq.offer(i);
		}

		int sum = 0;

		while (pq.size() > 1) {
			int num1 = pq.poll();
			int num2 = pq.poll();

			int twoSum = num1 + num2;
			sum += twoSum;
			pq.offer(twoSum);
		}

		return sum;
	}

}

4. Map + PriorityQueue

각 문자열에 대해서 빈도수가 높은 순으로 k만큼 해당 문자열을 반환

Input : {"i", "study", "inflearn", "i", "study", "coding"} , k = 2
Output : {"i", "study"}
제한) 빈도수가 동일 할 때 알파벳 순서가 낮은 단어가 먼저 온다.
Try to solve it in O(NlogN) time and O(n) extra space.

풀이

  1. Map을 이용하여 각 단어의 빈도수를 저장한다.
  2. 빈도수가 가장 높은 것부터 낮은 것 순으로 정렬한다.
  3. 빈도수가 동일할 때는 문자열의 알파벳이 낮은 순으로 정렬한다.
  4. 2번과 3번을 할 때 PriorityQueue를 이용해야 한다. (O(NlogN))

정렬 2가지 방법)
1번 방법 - 람다식

PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(
	(a,b) -> a.getValue() == b.getValue() ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue());

2번 방법 - Comparator

PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(comp);

		Comparator<Map.Entry<String, Integer>> comp = new Comparator<Map.Entry<String, Integer>>() {

			@Override
			public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
				if (o1.getValue() == o2.getValue()) {
					return o1.getKey().compareTo(o2.getKey());
				}
				return o2.getValue().compareTo(o1.getValue());
			}
		};

소스

import java.util.*;
import java.util.Map.Entry;

public class Q4 {

	public static void main(String[] args) {
		String[] words = { "i", "study", "inflearn", "i", "study", "coding" };
		int k = 2;

		System.out.println(solve(words, k));
	}

	public static List<String> solve(String[] words, int k) {
		// 1.
		List<String> result = new ArrayList<String>();
		Map<String, Integer> map = new HashMap<String, Integer>();

		for (String word : words) {
			map.put(word, map.getOrDefault(word, 0) + 1);
		}

		// 2. pq -> 람다식
		PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>((a,
				b) -> a.getValue() == b.getValue() ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue());

		// 2. pq -> comparator
		Comparator<Map.Entry<String, Integer>> comp = new Comparator<Map.Entry<String, Integer>>() {

			@Override
			public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
				if (o1.getValue() == o2.getValue()) {
					return o1.getKey().compareTo(o2.getKey());
				}
				return o2.getValue().compareTo(o1.getValue());
			}
		};

		for (Map.Entry<String, Integer> entry : map.entrySet()) {
			pq.offer(entry);
		}

		while (k-- > 0) {
			result.add(pq.poll().getKey());
		}

		return result;

	}

}

참고

인프런 강의 : 코딩테스트 전 꼭 알아야 할 개념과 문제(with 자바) - 푸샵맨 코딩스터디

profile
노력하는 배짱이
이전 포스트

Map - [Java]

다음 포스트

BFS/DFS - [Java]

0개의 댓글