JAVA

자바란

썬 마이크로 시스템즈에서 개발하여 1996년 01월 공식 발표. (이후 오라클이 인수)

모바일(J2ME), 대규모 기업환경(J2EE), XML 등을 지원.

자바의 특징

1. 운영체제에 독립적.
   • 자바는 JVM에 종속적이고, JVM은 운영체제에 종속적이다.
   • 따라서 자바는 서로 다른 운영체제에 종속적인 JVM만 있으면 실행 가능하다.
2. 객체지향 언어.
   • 상속, 캡슐화, 다형성
3. 자동 메모리 관리 (Garbage Collection)
   • 주기적으로 사용하지 않는 메모리 반환
4. 네트워크 분산처리 지원
   • 네트워크 프로그래밍 라이브러리(Java API) 지원
5. 멀티쓰레드 지원
   • 시스템과 관계없이 멀티쓰레드 구현 가능.
   • 여러 쓰레드에 대한 스케쥴링은 자바 인터프리터가 담당.
6. 동적 로딩(Dynamic Loading) 지원
   • 프로그램 시작시 모든 클래스를 로딩하는게 아니라 필요한 시점에 클래스를 로딩.
   • 따라서 일부 클래스가 변경되어도 전체 애플리케이션 컴파일을 하지 않아도 됨.

JVM(Java Virtual Machine)

자바를 실행하기 위한 가상 머신.

자바는 하드웨어 맞게 컴파일된 상태가 아니고, 실행시 해석(interpret)되므로 네이티브 프로그램에 비해 느리다.

최근 바이트코드(컴파일 된 자바코드)를 바로 기계어로 바꿔주는 JIT 컴파일러 등 최적화 기술이 적용되어 빨라짐.

JDK

JDK를 설치하면, JVM과 자바클래스 라이브러리(Java API) 외 개발에 필요한 프로그램들이 설치된다.

JDK의 bin을 path로 지정해주면 해당 path의 프로그램들을 경로 없이 사용할 수 있다.

JDK의 bin 디텍토리에 있는 주요실행파일

• javac.exe - 자바코드를 바이트코드로 컴파일
• java.exe - 바이트코드를 해석하고 실행
• javap.exe - 바이트코드를 다시 자바코드로 디컴파일
• javadoc.exe - 소스파일의 주석(/* */)을 이용하여 JAVA API문서와 같은 형식의 문서를 자동생성.
• jar.exe - 압축프로그램. 클래스와 프로그램에 실행에 관련된 파일을 jar로 압축하거나 압축 해제.

|참고|

JDK = JRE + 개발에 필요한 실행파일(javac 등)

JRE = JVM + 클래스 라이브러리(Java API)

자바 공식 API문서

https://docs.oracle.com/javase/8/docs/api/index.html

https://docs.oracle.com/en/java/javase/11/docs/api/index.html

자바 문법

• 자바 애플리케이션은 항상 main 메서드의 호출로 시작해서 main 메서드의 수행을 마치면 종료된다.

• 하나의 Java 애플리케이션에는 반드시 하나의 main 메서드가 있어야 한다.

• 작성된 Java 애플리케이션을 실행 할 때는 'java ${메인메서드를 포함한 클래스의 이름}'을 적어줘야 한다.
• 하나의 소스파일에 하나의 클래스가 보통.
  • 하나의 소스파일에 둘 이상을 정의도 가능.
  • 소스파일의 이름은 public class와 같아야 함.
  • 만약 public class가 없다면 아무거나 다른 class의 명.

• 클래스파일(*.class)는 클래스별로 하나씩 만들어지므로 여러 클래스를 가진 자바 코드 하나를 컴파일 했을 때 여러개의 class 파일이 생성될 수 있음.

자바 실행과정

1. 프로그램의 실행에 필요한 클래스(*.class)를 로드한다.
2. 클래스파일을 검사한다. (파일형식, 악성코드 체크)
3. 지정된 클래스에서 main(String[] args)를 호출한다.
4. main메서드가 종료되면 자원을 모두 반환한다.

참고

그림

> 문제 설명 보기

programmers.co.kr/learn/courses/30/lessons/42861

>IDEA

Minimum Spanning Tree(MST)를 구하는 문제이다.

정점을 기준으로 MST를 구하는 Prim의 알고리즘과 간선을 기준으로 MST를 구하는 Kruskal의 알고리즘으로 해당 문제를 해결 할 수 있다.

해당 문제의 input이 간선으로 주어졌으므로, Kruskal의 알고리즘의 코드가 더 짧다.

>Solution (Kruskal's Algorithm)

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs){
        int answer = 0;
        int[] fromIsland = new int[n];

        // 모든 간선을 가중치 오름차순으로 정렬
        Arrays.sort(costs, (o1, o2) -> o1[2] - o2[2]);

        for(int idx = 0; idx < n; idx ++){
            fromIsland[idx] = idx;
        }

        for(int[] cost : costs){
            if(findRoot(cost[0], fromIsland) != findRoot(cost[1], fromIsland)){
                fromIsland[findRoot(cost[0], fromIsland)] = findRoot(cost[1], fromIsland);

                answer += cost[2];
            }
        }

        return answer;
    }

    int findRoot(int nodeNo, int[] fromIsland){
        if(fromIsland[nodeNo] == nodeNo) return nodeNo;
        return findRoot(fromIsland[nodeNo], fromIsland);
    }
}

> Result (Kruskal's Algorithm)

> Solution (Prim's Algorithm)

public int solution(int n, int[][] costs) {
        int answer = 0;

        HashMap<Integer, ArrayList<int[]>> edgeMap = new HashMap<>();
        HashSet<Integer> nodes = new HashSet<>();
        ArrayList<int[]> edges = new ArrayList<>();

        for(int[] cost : costs){
            if(edgeMap.containsKey(cost[0])){
                edgeMap.get(cost[0]).add(new int[]{cost[1], cost[2]});
            } else {
                ArrayList<int[]> insertList = new ArrayList<>();
                insertList.add(new int[]{cost[1], cost[2]});
                edgeMap.put(cost[0], insertList);
            }
            if(edgeMap.containsKey(cost[1])){
                edgeMap.get(cost[1]).add(new int[]{cost[0], cost[2]});
            } else {
                ArrayList<int[]> insertList = new ArrayList<>();
                insertList.add(new int[]{cost[0], cost[2]});
                edgeMap.put(cost[1], insertList);
            }
            nodes.add(cost[0]);
            nodes.add(cost[1]);
        }

        int node = costs[0][0]; // 시작 노드
        edges.addAll(edgeMap.get(node));
        nodes.remove(node);

        while(!nodes.isEmpty()){
            Collections.sort(edges, (o1, o2) -> o1[1] - o2[1]);
            for(int idx = 0; idx < edges.size(); idx++){
                int[] edge = edges.get(idx);
                if(nodes.contains(edge[0])){
                    nodes.remove(edge[0]);
                    edges.remove(idx);
                    edges.addAll(edgeMap.get(edge[0]));
                    answer += edge[1];
                    break;
                }
            }
        }

        return answer;
    }

> Result (Prim's Algorithm)

Prim의 알고리즘이 더 느려보이지만 구현방식에 있어 Collection 객체가 많이 사용되어서 그렇고, 사실은 두 알고리즘의 시간복잡도는 똑같다.

> 문제 설명 보기

programmers.co.kr/learn/courses/30/lessons/42885?language=java

>IDEA

최대 2인승의 구명보트를 가능한 적게 써서 모든 사람을 구출하는 문제다.

가장 무거운 사람이 보트에 탔을 때, 가장 가벼운 사람이 같이 탈수 있다면 둘을 같이 보내고, 아니라면 무거운사람 혼자 보내야 한다.

최대 2인승이기 때문에, 혼자 타거나, 둘이 타는 경우의 수 밖에 없다.

>Solution

import java.util.Arrays;
import java.util.LinkedList;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        LinkedList<Integer> linkedList = new LinkedList<>();

        Arrays.sort(people);
        for(int weight : people){
            linkedList.addLast(weight);
        }

        int weight;
        while(!linkedList.isEmpty()){
            weight = linkedList.pollLast(); // 가장 무거운놈
            if(!linkedList.isEmpty()){
                if(weight + linkedList.peekFirst() <= limit){ // 가장 무거운놈과 가장 가벼운놈이 같이 탈 수 있는 경우
                    linkedList.pollFirst();
                }
            }
            answer++;
        }
        return answer;
    }
}

> Arrays.sort() vs Collections.sort() 성능 비교

Arrays.sort를 사용했을 경우 효율성 테스트

Collections.sort를 사용했을 경우 효율성 테스트

생각보다 성능 차이가 심해서 놀랐다.

컬렉션의 자료구조가 배열보다 무거워서 이런 차이가 발생하는 것 같은데, 간단한 구조인 배열이 훨씬 빠르다는 점을 다시 한번 되뇌었다.

> 문제 설명 보기

programmers.co.kr/learn/courses/30/lessons/42898

>IDEA

중고등학교적 많이 풀던 가장 짧은 거리의 개수를 구하는 문제다.

기본적으로 이전 도달 지점까지의 도달 개수를 다음 지점에서 더해주면 된다.

해당 방법을 기본으로 예외처리 (웅덩이)를 해주며 해결했다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        boolean[][] isPud = new boolean[m][n];
        long[][] map = new long[m][n];


        // Initialize
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j ++){
                map[i][j] = 0;
            }
        }

        for(int[] intArr : puddles){
            isPud[intArr[0] - 1][intArr[1] - 1] = true;
        }

        map[0][0] = 1;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(isPud[i][j]) continue;
                if(j > 0 && i > 0) {
                    if (isPud[i - 1][j] && isPud[i][j - 1]) {
                        isPud[i][j] = true;
                        continue;
                    }
                }
                if(j > 0){
                    if(!isPud[i][j-1]){
                        map[i][j] = (map[i][j] + map[i][j-1]) % 1000000007;
                    }
                }
                if(i > 0){
                    if(!isPud[i-1][j]){
                        map[i][j] = (map[i][j] + map[i-1][j]) % 1000000007;
                    }
                }
            }
        }

        return (int)(map[m-1][n-1]);
    }
}

> 문제 설명 보기

programmers.co.kr/learn/courses/30/lessons/42883

> IDEA

순서를 바꿀수 없는 문자열 형태의 숫자 중 k개를 제거하여 ( = 문자열의 총 길이가 n일 때, n-k개를 선택하여) 가장 큰 수를 만드는 문제이다.

가장 큰 자릿수의 수를 골라야 가장 큰 수를 만들 수 있으므로 왼쪽부터 가장 큰 수를 고르면서, 항상 남아있는 숫자의 개수가 선택해야 하는 수의 개수 이상을 유지하면 된다.

예를들어 "1231234"의 경우, k = 3이라면 4개의 숫자를 선택해야 하는데

첫번째 숫자는 3개의 숫자를 남긴 "1231"에서 가장 큰 수를 골라 3이 되며

두번째는 첫번째 고른 숫자로부터 오른쪽엔 2개의 숫자를 남긴 "12" 중에 가장 큰 수를 골라 2가 되며

세번째는 두번째 고른 숫자로부터 오른쪽엔 1개의 숫자를 남겨 "3"중에 3이 되며

네번째는 세번째 고른 숫자로부터 오른쪽엔 0개의 숫자를 남겨 "4"중에 4가 된다.

따라서 "3234"를 반환하면 된다.

>Solution

class Solution {
    public String solution(String number, int k) {
        char maxVal;
        int pos = 0;
        StringBuffer sb = new StringBuffer();
        for(int cnt = number.length() - k; cnt > 0 ; cnt--){
            maxVal = '0';
            for(int idx = pos; idx < number.length() - cnt + 1; idx++){
                if(number.charAt(idx) > maxVal){
                    maxVal = number.charAt(idx);
                    pos = idx+1;
                }
            }
            sb.append(maxVal);
        }
        return sb.toString();
    }
}

String, StringBuilder, StringBuffer의 성능 차이를 알 수 있는 문제였다.

String은 immutable한 변수이기 때문에 한 번 선언되면 변하지 않고 String끼리 연산하여 String을 만들어 낼 때는 새로운 class를 생성하여 연산 결과를 할당하게 된다. 따라서 다수의 String 연산을 실행하게 되면 속도가 급격히 떨어진다.

StringBuilder와 StringBuffer는 내부적으로 배열 형태로 구현되어 새로운 문자열이 추가될 때, 해당 길이만큼 배열이 남아있다면 그대로 추가하여 사용하고, 모자라다면 두배의 크기로 배열을 할당하기 때문에 String보다 연산 속도가 빠르다.

다만 StringBuiler가 단일 쓰레드에서 연산속도가 더 빠르며 StringBuffer는 Thread-Safe하다.

> String 구현

>StringBuilder 구현

> StringBuffer 구현

> 문제설명

leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/

문제내용 요약

주어진 바이너리 트리에서 노드의 왼쪽 하위노드와 오른쪽 하위노드를 바꾸는 것을 flip이라고 한다.

주어진 바이너리 트리를 pre-order 방식으로 탐색했을 때, 주어진 배열 voyage와 같은 순서로 탐색하기 위해 flip해야 하는 노드의 val값을 리스트에 넣어 반환하라.

>IDEA

바이너리 트리를 pre-order(DFS)로 탐색하며 voyage와 비교한다.

voyage와 pre-order의 순서가 다른 경우 하위 노드를 flip하며 pre-order 탐색을 진행한다.

탐색이 끝난 후 pre-order로 탐색한 순서와 voyage가 같다면 리스트를 출력한다.

>Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int[] travel;
    int travelIdx;
    ArrayList<Integer> answerList = new ArrayList<>();

    boolean flip(TreeNode treeNode){
        if(treeNode.left == null || treeNode.right == null) return false;
        answerList.add(treeNode.val);
        TreeNode tmp = treeNode.left;
        treeNode.left = treeNode.right;
        treeNode.right = tmp;
        return true;
    }

    void preOrder(TreeNode treeNode, int[] voyage){
        travel[travelIdx] = treeNode.val;
        if(travelIdx < voyage.length- 1)travelIdx++;
        else return;
        if(treeNode.left != null){
            if (treeNode.left.val != voyage[travelIdx]) {
                flip(treeNode);
            }
            preOrder(treeNode.left, voyage);
        }
        if(treeNode.right != null){
            if (treeNode.right.val != voyage[travelIdx]) {
                flip(treeNode);
            }
            preOrder(treeNode.right, voyage);
        }
    }

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        travel = new int[voyage.length];
        travelIdx = 0;
        preOrder(root, voyage);
        if(!Arrays.equals(travel, voyage)) {
            answerList.clear();
            answerList.add(-1);
        }
        return answerList;
    }
}

> Result

flip을 없애고 다음과 같이 구현 할 수도 있다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int[] travel;
    int travelIdx;
    ArrayList<Integer> answerList = new ArrayList<>();

    void preOrder(TreeNode treeNode, int[] voyage){
        travel[travelIdx] = treeNode.val;
        if(travelIdx < voyage.length- 1)travelIdx++;
        else return;
        if(treeNode.left != null){
            if (treeNode.left.val != voyage[travelIdx]) {
                answerList.add(treeNode.val);
                if(treeNode.right != null) preOrder(treeNode.right, voyage);
                preOrder(treeNode.left, voyage);
                return;
            }
        }
        if(treeNode.left != null) preOrder(treeNode.left, voyage);
        if(treeNode.right != null) preOrder(treeNode.right, voyage);
    }

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        travel = new int[voyage.length];
        travelIdx = 0;
        preOrder(root, voyage);
        if(!Arrays.equals(travel, voyage)) {
            answerList.clear();
            answerList.add(-1);
        }
        return answerList;
    }
}

> Result

수행 속도가 줄었다.

> 문제설명

leetcode.com/problems/reconstruct-original-digits-from-english/

문제 내용 요약

0부터 9까지의 숫자의 스펠링이 규칙없이 나열된 String에서 숫자를 복원해 오름차순으로 반환한다.

> IDEA

각 숫자가 가질 수 있는 특별한 알파벳을 검사하여 해결할 수 있다.

> Solution

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

class Solution {
    void mapRemove(char c, HashMap<Character, Integer> stringMap){
        if(!stringMap.containsKey(c)) return;
        if(stringMap.get(c) == 1){
            stringMap.remove(c);
        } else {
            stringMap.replace(c, stringMap.get(c) - 1);
        }
    }
    public String originalDigits(String s) {
        ArrayList<Integer> answerList = new ArrayList<>();
        HashMap<Character, Integer> stringMap = new HashMap<>();
        for(int idx = 0; idx < s.length(); idx++){
            if(stringMap.containsKey(s.charAt(idx))){
                stringMap.replace(s.charAt(idx), stringMap.get(s.charAt(idx))+1);
            } else {
                stringMap.put(s.charAt(idx), 1);
            }
        }

        while (!stringMap.isEmpty()){
            if(stringMap.containsKey('z')) {
                answerList.add(0);
                mapRemove('z', stringMap);
                mapRemove('e', stringMap);
                mapRemove('r', stringMap);
                mapRemove('o', stringMap);
                continue;
            }
            if(stringMap.containsKey('w')) {
                answerList.add(2);
                mapRemove('t', stringMap);
                mapRemove('w', stringMap);
                mapRemove('o', stringMap);
                continue;
            }
            if(stringMap.containsKey('u')) {
                answerList.add(4);
                mapRemove('f', stringMap);
                mapRemove('o', stringMap);
                mapRemove('u', stringMap);
                mapRemove('r', stringMap);
                continue;
            }
            if(stringMap.containsKey('x')) {
                answerList.add(6);
                mapRemove('s', stringMap);
                mapRemove('i', stringMap);
                mapRemove('x', stringMap);
                continue;
            }
            if(stringMap.containsKey('g')) {
                answerList.add(8);
                mapRemove('e', stringMap);
                mapRemove('i', stringMap);
                mapRemove('g', stringMap);
                mapRemove('h', stringMap);
                mapRemove('t', stringMap);
                continue;
            }
            if(stringMap.containsKey('o')) {
                answerList.add(1);
                mapRemove('o', stringMap);
                mapRemove('n', stringMap);
                mapRemove('e', stringMap);
                continue;
            }
            if(stringMap.containsKey('t') || stringMap.containsKey('h') || stringMap.containsKey('r')) {
                answerList.add(3);
                mapRemove('t', stringMap);
                mapRemove('h', stringMap);
                mapRemove('r', stringMap);
                mapRemove('e', stringMap);
                mapRemove('e', stringMap);
                continue;
            }
            if(stringMap.containsKey('f')) {
                answerList.add(5);
                mapRemove('f', stringMap);
                mapRemove('i', stringMap);
                mapRemove('v', stringMap);
                mapRemove('e', stringMap);
                continue;
            }
            if(stringMap.containsKey('s')) {
                answerList.add(7);
                mapRemove('s', stringMap);
                mapRemove('e', stringMap);
                mapRemove('v', stringMap);
                mapRemove('e', stringMap);
                mapRemove('n', stringMap);
                continue;
            }
            answerList.add(9);
            mapRemove('n', stringMap);
            mapRemove('i', stringMap);
            mapRemove('n', stringMap);
            mapRemove('e', stringMap);
            continue;
        }

        Collections.sort(answerList);
        StringBuilder sb = new StringBuilder();
        for(int num : answerList){
            sb.append(num);
        }

        return sb.toString();
    }
}

> 문제설명

leetcode.com/problems/vowel-spellchecker/

문제 내용을 요약하자면 다음과 같다.

목표 String배열 wordlist와 질의 String배열 queries가 주어졌을 때, 각 질의 String배열을 다음과 같은 연산을 통해 정답 String배열을 return하면 된다.

1. 목표 String과 질의 String이 완벽히 일치하면 그대로 정답 배열에 추가.

2. 대소문자에 관계없이 일치하는 경우, 목표 String배열중 가장 앞의 String을 정답 배열에 추가.

3. 대소문자에 관계없이 vowel(모음, [AaEeIiOoUu])이 위치와 개수 상관 없이 다른 경우, 모음을 제외한 자음이 모두 일치하는 String을 목표 String배열의 가장 앞쪽에서 찾아 정답 배열에 추가.

4. 위 경우가 아닌 경우 빈 String을 정답 배열에 추가.

> Solution

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;

class Solution {
    public String[] spellchecker(String[] wordlist, String[] queries) {
        LinkedHashSet<String> wordSet = new LinkedHashSet<>();
        HashMap<String, String> vowelMap = new HashMap<>();
        HashMap<String, String> upperMap = new HashMap<>();

        for(String word : wordlist){
            wordSet.add(word);
            upperMap.putIfAbsent(word.toUpperCase(), word);
            vowelMap.putIfAbsent(word.replaceAll("[AaEeIiOoUu]", "*").toUpperCase(), word);
        }

        ArrayList<String> ansList = new ArrayList<>();
        for(String query : queries){
            if(wordSet.contains(query)) {
                ansList.add(query);
                continue;
            }

            if(upperMap.containsKey(query.toUpperCase())){
                ansList.add(upperMap.get(query.toUpperCase()));
                continue;
            }

            String str = query.replaceAll("[AaEeIiOoUu]", "*");
            if(vowelMap.containsKey(str.toUpperCase())){
                ansList.add(vowelMap.get(str.toUpperCase()));
                continue;
            }

            ansList.add("");
        }
        return ansList.toArray(new String[0]);
    }
}