코드 한 줄

이 문제는 “Quick Select”의 알고리즘을 사용하는 대표적인 문제이다.

Quick select는 퀵 정렬(quick sort)를 이용하는 알고리즘이다.

퀵 정렬의 pivot을 정하고 1차 정렬을 하면 pivot의 원소 위치는 최종 정렬된 배열의 위치가 된다.

이것을 이용하여 모든 배열을 정렬 하지 않고, pivot의 값을 비교하여, 찾는 값에 따라 pivot의 왼쪽이나 오른쪽만 정렬하는 알고리즘이다.

int quickselect(int[] arr, int k) {
    return quickselect(arr, 0, arr.length - 1, k - 1);
}

int quickselect(int[] arr, int first, int last, int k) {
    if (first <= last) {
        int pivot = partition(arr, first, last);
        if (pivot == k) {
            return arr[k];
        }
        if (pivot > k) {
            return quickselect(arr, first, pivot - 1, k);
        }
        return quickselect(arr, pivot + 1, last, k);
    }
    return Integer.MIN_VALUE;
}

int partition(int[] arr, int first, int last) {
    int pivot_spot = first;
    for (int i = first; i < last; i++) {
        if (arr[i] > arr[last]) {
            swap(arr, i, pivot_spot);
            pivot_spot++;
        }
    }
    swap(arr, pivot_spot, last);
    return pivot_spot;
}

void swap(int[] arr, int x, int y) {
    int tmp = arr[x];
    arr[x] = arr[y];
    arr[y] = tmp;
}

먼저, 본인은 다음과 같은 변수를 선언했다.

private int N;
private boolean tf;
private int cnt;

    while(collatz.tf) {
        collatz.cnt++;

        if(collatz.N % 2 == 0) {
            collatz.N = collatz.N / 2;
            System.out.println("[" + collatz.cnt + "] : " + collatz.N);
        } else {
            collatz.N = (collatz.N * 3) + 1;
            System.out.println("[" + collatz.cnt + "] : " + collatz.N);
        }

        if(collatz.N == 1) {
            collatz.tf = false;
        }
    }

반복문이 돌아갈 때마다 카운트를 증가하며, N에 대하여 짝수일 때, 홀수일 때마다 해당 작업을 하고 과정을 출력한다.

N이 1이 되면 while문을 빠져나오기 위해 tf에 false 값을 넣는다.

import java.util.Scanner;

public class Collatz {

    private int N;
    private boolean tf;
    private int cnt;

    public static void main(String[] args) {
        Collatz collatz = new Collatz();
        Scanner sc = new Scanner(System.in);
        collatz.tf = true;
        collatz.cnt = 0;

        System.out.print("콜라츠 추측 : ");
        collatz.N = sc.nextInt();

        while(collatz.tf) {
            collatz.cnt++;

            if(collatz.N % 2 == 0) {
                collatz.N = collatz.N / 2;
                System.out.println("[" + collatz.cnt + "] : " + collatz.N);
            } else {
                collatz.N = (collatz.N * 3) + 1;
                System.out.println("[" + collatz.cnt + "] : " + collatz.N);
            }

            if(collatz.N == 1) {
                collatz.tf = false;
                System.out.println("");
            }
        }
    }
}

public class CoinChange {

    private int ten;
    private int fifty;
    private int hundred;
    private int fiveHundred;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        CoinChange cc = new CoinChange();

        System.out.print("거스름돈을 입력하세요 : ");
        int change = sc.nextInt();

        while(change >= 500) {
            change -= 500;
            cc.fiveHundred++;
        }
        while(change >= 100) {
            change -= 100;
            cc.hundred++;
        }
        while(change >= 50) {
            change -= 50;
            cc.fifty++;
        }
        while(change >= 10) {
            change -= 10;
            cc.ten++;
        }

        System.out.println("10원짜리 " + cc.ten + "개");
        System.out.println("50원짜리 " + cc.fifty + "개");
        System.out.println("100원짜리 " + cc.hundred + "개");
        System.out.println("500원짜리 " + cc.fiveHundred + "개");
        System.out.println("총 동전 개수는 " + (cc.ten + cc.fifty + cc.hundred + cc.fiveHundred) + "개 입니다.");
    }
}

(간단한 문제라서 따로 메소드를 사용하진 않았습니다.)

이 문제는 해쉬맵(hashmap)을 써서 A의 문자를 B의 문자 매칭을 저장하면 된다.

A의 문자가 해쉬맵의 키로 있다면, B의 문자와 해쉬맵의 있는 값과 비교한다.

A의 문자가 해쉬맵의 키로 없다면, B의 문자가 해쉬맵의 값으로 있는지 확인하고 없으면 해쉬맵에 더해준다.

bool solve(String a, String b) {
    HashMap<char, char> map = new HashMap<>();
    for (int i = 0; i < a.length(); i++) {
        char c1 = a.charAt(i);
        char c2 = b.charAt(i);
        if (map.containsKey(c1)) {
            if (map.get(c1) != c2) {
                return false;
            }
        }
        else {
            if (map.containsValue(c2)) {
                return false;
            }
            map.put(c1, c2);
        }
    }
    return true;
}

주로 조합을 구하거나 답의 양이 많을 경우는 재귀함수를 사용하면 된다.

empty string 부터 시작하여 "("를 더하고 재귀함수를 부르고, ")"를 더하고 재귀함수를 부르면 된다.

여기서 중요한 건, 현재 몇 개의 여는 괄호를 사용 하였는지와 몇 개의 닫는 괄호를 사용 하였는지 알아야 한다.

괄호 조합을 왼쪽에서 오른쪽으로 읽을 때, 닫는 괄호가 여는 괄호 개수보다 많으면 정당한 조합이 될 수 없다.

그러므로, 재귀함수에서 여는 괄호가 n보다 작을 때 여는 괄호를 더한 재귀함수를 만들고,

닫는 괄호 개수가 여는 괄호 개수보다 작을 때 닫는 괄호를 더한 재귀함수를 만들면 된다.

재귀함수에 주어진 문자열이 (n*2) 길이를 가진다면 알맞는 괄호 조합이니, 리스트에 더해주면 된다.

List<string> parenthesisPairs(int n) {
    List<string> ans = new ArrayList();
    recurse(ans, "", 0, 0, n);
    return ans;
}

void recurse(List<string> ans, String cur, int open, int close, int n){
    if (str.length() == n * 2) {
      ans.add(cur);
      return;
  }
    if (open < n) {
      recurse(ans, cur + "(", open + 1, close, n);
    }
    if (close < open) {
      recurse(ans, cur + ")", open, close + 1, n);
    }
}

이 문제는 n보다 클 때까지 피보나치의 수를 구하며 짝수인 피보나치 수를 다 더해주면 된다.

int evenFibSum(int N) {

    int sum = 0;
    int x = 1;
    int y = 2;

    while (x <= N) {
      if (x % 2 == 0) {
        sum += x;
      }
      int z = x + y;
      x = y;
      y = z;
  }

    return sum;
}

여기서 피보나치 수가 0이 아니고 1부터 시작하는 이유는 x가 0일 경우 sum에 더해도 도움이 되지 않기 때문이다.

이 문제는 두 개의 정수 변수로 현재의 합(currentSum)과 전체의 제일 큰 합(maxSum)을 저장해야 합니다.

각 원소마다 (currentSum + 원소) 값을 원소 값이랑 비교하고, 더 큰 값이 currentSum이 됩니다.

maxSum은 currentSum이 바뀔 때마다 체크하여 제일 큰 값을 저장하면 됩니다.

int solution(int[] arr) {

    int maxSum = arr[0];
    int currentSum = arr[0];

    for(int i = 1; i < arr.length; i++) {
      currentSum = Math.max(currentSum + arr[i], arr[i]);
      maxSum = Math.max(currentSum, maxSum);
    }

    return maxSum;
}