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

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());

풀이 과정

1. math.gcd 함수는 존재하지만 math.lcm 함수는 없어서 lcm 함수를 만들어 줌.

2. a * b = gcd * lcm인걸 활용하여 lcm 함수를 만들어준 다음 첫번째 요소에서부터 순차적으로 갱신하면서 lcm을 구해주면 된다.

import math

def lcm(a, b):
    return (a * b) // math.gcd(a, b)

def solution(arr):
    answer = arr[0]
    for i in range(1, len(arr)):
        answer = lcm(answer, arr[i])

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 순차적으로 접근하면서 문자열의 첫번째를 숫자인지 알파벳인지 체크

2. 숫자가 아니라면 첫번째 대문자, 맞다면 그대로 저장

3. 나머지 문자열들은 소문자로 변환하여 저장

4. 공백(" ") 만날 시 저장 및 문자열 초기화

def solution(s):
    word = False # 문자열 상태 저장
    answer = ''
    for i in s:
        if not word: # 첫번째 자리
            if i.isdigit(): # 첫번째 자리가 숫자
                answer += i
                word = True
            elif i == ' ': # 공백(첫번째 자리가 아님)
                answer += i
                continue
            else: # 첫번째 자리가 알파벳
                answer += i.upper() # 대문자
                word = True
        else:
            if i == " ":
                answer += i
                word = False
            else:
                answer += i.lower()


    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. numpy의 matmul 함수를 활용하여 행렬의 곱셈 수행

2. matmul 함수 활용하기 위해 리스트를 np.array로 변환하는 과정 필요

3. numpy array를 list로 변환하기 위해 tolist 함수 사용

import numpy as np

def solution(arr1, arr2):
    a1 = np.matmul(np.array(arr1),np.array(arr2))
    answer = a1.tolist()
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. split과 map을 활용하여 정수형 리스트로 변환

2. 리스트 정렬후 0번째 ,-1번째 합쳐서 리턴(최소, 최댓값)

def solution(s):
    answer = ''
    p = list(map(int, s.split()))
    p.sort()
    answer = str(p[0]) + ' ' + str(p[-1])

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 참가자들이 어디에 있는지 위치를 모두 저장

2. 각각의 참가자 기준으로 bfs를 진행

   • 현재 위치 기준 거리 2 이내에 사람이 있는지 검사.
   • 칸막이가 있다면 그방향은 방문 x

3. 참가자들중 한명이라도 실패하면 0, 모두 성공하면 1 저장

from collections import deque

def check(place, x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    queue = deque()
    queue.append([x, y, 0])
    visited = set()
    visited.add(tuple([x, y]))
    while queue:
        a, b, c = queue.popleft()
        if c == 2:
            continue
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx >= 0 and nx <= len(place)-1 and ny >= 0 and ny <= len(place[0])-1:
                if tuple([nx, ny]) not in visited:
                    visited.add(tuple([nx, ny]))
                    if place[nx][ny] == 'P':
                        return False
                    if place[nx][ny] == 'X':
                        continue
                    queue.append([nx, ny, c+1])

    return True


def solution(places):
    answer = []

    for place in places:
        people = []
        for i in range(len(place)):
            for j in range(len(place[0])):
                if place[i][j] == 'P':
                    people.append([i, j])

        flag = True
        for x, y in people:
            if not check(place, x, y):
                flag = False
                break

        if flag:
            answer.append(1)
        else:
            answer.append(0)


    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제 설명

풀이 과정

1. 현재 값의 2진수 변환한 결과의 1의 개수를 구함.

2. 현재 값 + 1 ~ 1000000까지의 수를 순차적으로 방문하면서 2진수 변환 및 2진수 개수 비교

3. 같으면 바로 종료 

def getonecount(n):
    result = 0
    while(n > 0):
        if n%2 == 1:
            result += 1
        n = n // 2
    return result

def solution(n):
    answer = 0
    oc = getonecount(n)
    for i in range(n+1, 1000000):
        if oc == getonecount(i):
            answer = i
            break
    
    return answer

풀이 과정

1. 진법 변환을 할때 2진법~16진법까지 가능하므로 매칭되는 배열을 만들어줌. [0] = 0, ... [10] = A, [11] = B, ... , [15] = F

2. 나누었을 때 나머지들만 붙여서 진법 변환

3. 최대 인원이 100명이고, 튜브가 구할 숫자의 최대 갯수는 1000개이므로 여유있게 10만개정도의 숫자 진법 변환

4. 이후 튜브의 순서에 맞추어서 값들을 하나씩 꺼내오면 된다.

def convert(num, scale):
    match = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
            'A', 'B', 'C', 'D', 'E', 'F']

    if num == 0:
        return '0'

    result = ''
    while num > 0:
        result = match[num % scale] + result
        num = num // scale

    return result

def solution(n, t, m, p):
    answer = ''
    temp = ' '
    for i in range(0, 100000): # 여유있게 10만개정도 변환해서 붙여둠
        temp += convert(i, n)

    for i in range(p, len(temp), m): # 문자열 붙임
        answer = answer + temp[i]
        if len(answer) == t:
            break

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges