그냥 코딩하는 사람의 블로그

Union-find에는 2가지 연산 존재(Union, Find)

0. 초기 그룹 상태 초기화

- 초기 그룹은 자기 자신을 가리키도록 설정해주어야 함. (각각이 개별 그룹)

public void init(int[] parent) {
    for(int i = 0; i<parent.length; i++)
        parent[i] = i;
}

1. 자기가 속한 그룹의 대표값 (find)

- 1, 2, 3, 4, 5가 한 그룹일때 5->4, 4->3, 3->2, 2->1 이런 식으로 가리키도록 구현하면 효율이 좋지 않음.

- 5->1, 4->1, 3->1, 2->1 이런식으로 가리키도록 구현

public int find(int[] parent, int a) {
  int temp = a;
  if (parent[temp] != temp)
      parent[temp] = find(parent, parent[a]);

  return a;
}

2. 그룹 간 결합 함수 (union)

- 각 그룹의 부모노드를 찾은 후, 한쪽의 부모노드를 다른쪽의 부모노드로 바꿈.

- 나중에 find 다시 호출 시 일괄적으로 변경됨.

public void union(int[] parent, int a, int b) {
    int t = find(parent, a);
    int l = find(parent, b);

    if (t != l) {
        parent[t] = l;
    } 
}

1. HashMap 생성

HashMap<키 타입, 값 타입> map = new HashMap<키 타입, 값 타입>();

2. HashMap 값 저장

map.put(키, 값);

3. HashMap 값 가져오기

map.get(키); // 키에 해당하는 값이 없는 경우 null 리턴

4. HashMap 값 바꾸기

map.replace(키, 변경할 값); // 키가 존재하지 않는 경우 동작 안함

HashMap 활용 문제

- [Programmers] [ Lv 1 ] 완주하지 못한 선수

import java.util.Arrays;
import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(String complete:completion) {
        	if (map.get(complete) == null) {
        		map.put(complete, 1); 
        	} else {
        		map.replace(complete, map.get(complete) + 1);
        	}
        }
        
    	String answer = "";
        for(String person:participant) {
        	if(map.get(person) == null || map.get(person) == 0) {
        		answer = person;
        		break;
        	}
        	map.replace(person, map.get(person) - 1);
        }

        return answer;
    }
}

Array

Arrays.copyOfRange(배열, 시작인덱스, 종료인덱스)

• 배열을 시작인덱스 ~ (종료인덱스-1)까지 잘라서 새로운 배열 만들어서 리턴

int[] temp = Arrays.copyOfRange(array, 0, 5);

Arrays.parallelSort(배열)

• 배열을 오름차순으로 정렬

Arrays.sort(배열, Comparator)

• comparator에 지정한 방식으로 요소가 정렬된다.
• comparator의 compare 메서드를 오버라이딩
  • 두 요소를 비교하였을 때, 어느 요소를 앞으로 보낼지 결정
  • int compare(a, b)
  • a보다 b가 클때, b를 앞에다가 두고 싶으면 1, 아니면 -1 리턴,
    • a보다 b가 작을때는 반대 값을 리턴해주면 된다.
  • a와 b가 같을때는 0 리턴
• 길이 순서로 오름차순 정렬하는 예시

Arrays.sort(array, new Comparator<String>(){
  @Override
  public int compare(String a, String b) {
    if (a.length() < b.length()) {
        return 1;
    } else if (a.length() == b.length()) {
        return 0;
    } else {
        return -1;
    }
  }
});

String

String.subString(startindex, endindex)

• 시작 인덱스~종료 인덱스까지 쪼갠 문자열 리턴 (종료 인덱스 미포함, 기존 문자열은 적용되지 않음)

String temp = phone.substring(0, phone.length()-i);

Queue

Queue.offer / Queue.poll

• Queue에 값 / 객체를 삽입(offer)/삭제(poll)
• Queue 객체는 LinkedList를 할당해준다.
• 예시 소스

        for (int i = 0; i<progresses.length; i++) 
        	progress_queue.offer(new job(progresses[i], speeds[i]));
       
        int day = 0;
        while (!progress_queue.isEmpty()) {
        	job nearest_job = progress_queue.peek();
        	int job_count = 0;
        	
        	while (nearest_job.progress + nearest_job.speed * day >= 100) {
        		progress_queue.poll();
        		job_count++;
        		if (progress_queue.isEmpty()) 
        			break;
        		nearest_job = progress_queue.peek();
        	}
        	
        	if (job_count != 0) {
        		answer.add(job_count);
        	}	
        	day++;
        }

PriorityQueue

최소 히프

 PriorityQueue<Integer> heap = new PriorityQueue<Integer>();

최대 히프

PriorityQueue<Integer> heap = new PriorityQueue<Integer>(Collections.reverseOrder());

히프 삽입/삭제/맨 위 요소 보기

1. 삽입 : add
2. 삭제 : remove
3. 삭제하지 않고 조사 : peek

heap.add(score);

int e1 = heap.remove();

heap.peek() >= K

Integer Collection -> Int Array 변환

int[] real_answer = answer.stream().mapToInt(Integer::intValue).toArray();

배열 내림차순 정렬

• 그냥은 할수 없음. 리스트로 변형 후 진행하여야 함.
• 리스트로 변형할 때 일반타입은 박싱하여 객체로 바꾸어주어야 함에 유의
• 이후 Collections.sort에 reverseOrder 인자를 같이 넘겨주면 된다.

int[] prior_copy = Arrays.copyOf(priorities, priorities.length);
List<Integer> list = Arrays.stream(prior_copy).boxed().collect(Collectors.toList());
Collections.sort(list, Collections.reverseOrder());