myBlog

>> 문제설명

leetcode.com/problems/coin-change/

가장 적은 갯수의 동전으로 만들수 있는 수를 늘려가며 목표치만큼의 금액을 만드는 가장 적은 갯수의 동전을 반환하는 동적 계획법 문제다.

저조한 성적의 Distribution Chart를 보고 Hash맵을 Array로 바꿔서 풀어 조금은 나아진 성적표를 받았다.

> Solution 1 (Hash Map & DP)

import java.util.HashMap;
import java.util.LinkedList;

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0)
            return 0;

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        LinkedList<Integer> nextList = new LinkedList<>();

        hashMap.put(0,0);
        nextList.add(0);

        while (!nextList.isEmpty()){
            int val = nextList.poll();
            for(int coin : coins){
                if(val+coin == amount) return hashMap.get(val)+1;
                if(val+coin > amount || hashMap.containsKey(val+coin)) continue;
                if(hashMap.containsKey(val)){
                    hashMap.put(val+coin, hashMap.get(val)+1);
                    nextList.addLast(val+coin);
                }
            }
        }
        return -1;
    }
}

> Result 1

> Solution 2 (Array & DP)

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0)
            return 0;

        int[] amountMap = new int[amount+1];
        Arrays.fill(amountMap, Integer.MAX_VALUE);

        amountMap[0] = 0;

        for(int i = 0; i <= amount; i++) {
            if(amountMap[i] == Integer.MAX_VALUE) continue;
            for (int coin : coins) {
                if (coin > amount - i) continue;
                amountMap[i+coin] = Math.min(amountMap[i] + 1, amountMap[i+coin]);
            }
        }

        return amountMap[amount] == Integer.MAX_VALUE ? -1 : amountMap[amount];
    }
}

> Result 2

개인적으로 장단점에 관계 없이 stream API를 사용하는것을 선호하진 않는다.

우선 회사 업무 환경부터 JDK 1.6...을 사용하기 때문에 stream과 lamda식 표현이 너무 익숙하지 않고,

유지보수에 적절하지 않다고 생각하기 때문이다.

그래도 알고리즘 문제를 풀다보면 배열을 리스트로, 리스트를 배열로 바꿔야 하는 상황을 자주 마주치게 되는데, for문을 사용하여 원소를 하나씩 옮겨주는 것 보단 stream을 사용하는게 깔끔한 코드에 도움이 되는 것 같다.

> 예제 (배열을 리스트로)

import java.util.Arrays;
import java.util.stream.Collectors;
List list = Arrays.stream(yourArray).boxed().collect(Collectors.toList());

> 예제 (리스트를 배열로)

// Integer wrapper class를 사용한 list를 array로 변환
int[] intArray = yourList.stream().mapToInt(Integer::intValue).toArray();

문제 설명 보기

>>programmers.co.kr/learn/courses/30/lessons/43105

바이너리 트리를 탐색하며 가장 큰 숫자의 branch를 찾는 문제 같지만 그런식으로 순회하면 무조건 time-out이 되도록 설계된 문제다.

자식 Node로 탐색하는 방법 중 가장 가중치가 크도록 탐색하는 방법은 두개의 부모 노드 중 가중치가 더 큰 노드를 통해 탐색하는 법이므로, 그를 통해 문제를 해결했다.

가중치가 있는 길찾기를 한다고 생각하면 편하다.

import java.util.Arrays;
import java.util.Collections;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[][] triangle) {
        if(triangle.length == 1) return triangle[0][0];

        for(int row = 1; row < triangle.length; row++){
            for(int col = 0; col < triangle[row].length; col++){
                int left = 0;
                int right = 0;
                if(col != 0){
                    left = triangle[row-1][col-1];
                }
                if(col != triangle[row].length-1){
                    right = triangle[row-1][col];
                }
                triangle[row][col] += Math.max(left, right);
            }
        }
        return Collections.max(Arrays.stream(triangle[triangle.length-1]).boxed().collect(Collectors.toList()));
    }
}

문제 설명 보기

>> programmers.co.kr/learn/courses/30/lessons/42860

순간의 최선이 선택이 결과적으로 최고의 선택이 되는 Greedy한 풀이를 요구하는 문제다.

현재 커서의 위치에서 가장 가까운 곳으로 이동하는데 필요한 조작 횟수

Character를 원하는 알파벳으로 바꾸는 데 필요한 조작 횟수

위 두가지를 더하여 답을 냈다.

class Solution {
    class Pair<L, R>{
        L pointer;
        R cnt;
        Pair(L pointer, R cnt){
            this.pointer = pointer;
            this.cnt = cnt;
        }
    }

    Pair findClosest(int strPointer, String name){
        if(name.charAt(strPointer) != 'A') return new Pair(0, 0);
        int left = strPointer;
        int right = strPointer;
        int cnt = 0;
        for(int i = 0; i < name.length() / 2 + 1; i++){
            cnt++;
            if(right == name.length() - 1) right = 0;
            else right++;
            if(name.charAt(right) != 'A') return new Pair(right, cnt);
            if(left == 0) left = name.length() - 1;
            else left--;
            if(name.charAt(left) != 'A') return new Pair(left, cnt);
        }
        return new Pair(-1, cnt);
    }

    int countChar(char nameChar){
        if(nameChar == 'N') return 13;
        if(nameChar > 'N') return ('Z' + 1 - nameChar);
        if(nameChar < 'N') return (nameChar - 'A');
        return 0;
    }

    public int solution(String name) {
        int answer = 0;

        Pair<Integer, Integer> pair = new Pair<>(0,0);

        while(pair.pointer != -1){
            pair = findClosest(pair.pointer, name);
            if(pair.pointer == -1) break;
            else answer += countChar(name.charAt(pair.pointer));
            name = name.substring(0, pair.pointer).concat("A").concat(name.substring(pair.pointer+1));
            if(pair.pointer != -1) {
                answer += pair.cnt;
            }
        }
        return answer;
    }
}

>> 문제설명

leetcode.com/problems/integer-to-roman/

> Solution 1 (No Array)

class Solution {
    public String intToRoman(int num) {
        String answer = "";

        for(int idx = 0; idx < num / 1000; idx++) answer = answer.concat("M");
        num %= 1000;
        for(int idx = 0; idx < num / 900; idx++) answer = answer.concat("CM");
        num %= 900;
        for(int idx = 0; idx < num / 500; idx++) answer = answer.concat("D");
        num %= 500;
        for(int idx = 0; idx < num / 400; idx++) answer = answer.concat("CD");
        num %= 400;
        for(int idx = 0; idx < num / 100; idx++) answer = answer.concat("C");
        num %= 100;
        for(int idx = 0; idx < num / 90; idx++) answer = answer.concat("XC");
        num %= 90;
        for(int idx = 0; idx < num / 50; idx++) answer = answer.concat("L");
        num %= 50;
        for(int idx = 0; idx < num / 40; idx++) answer = answer.concat("XL");
        num %= 40;
        for(int idx = 0; idx < num / 10; idx++) answer = answer.concat("X");
        num %= 10;
        for(int idx = 0; idx < num / 9; idx++) answer = answer.concat("IX");
        num %= 9;
        for(int idx = 0; idx < num / 5; idx++) answer = answer.concat("V");
        num %= 5;
        for(int idx = 0; idx < num / 4; idx++) answer = answer.concat("IV");
        num %= 4;
        for(int idx = 0; idx < num / 1; idx++) answer = answer.concat("I");

        return answer;
    }
}

>Result 1

> Solution 2 (No Loop)

class Solution{
    public String intToRoman(int num){
        String[] MMap = {"","M","MM","MMM"};
        String[] CMap = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
        String[] XMap = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
        String[] IMap = {"","I","II","III","IV","V","VI","VII","VIII","IX"};
        return MMap[num/1000].concat(CMap[num/100%10]).concat(XMap[num/10%10]).concat(IMap[num%10]);
    }
}

>Result 2

확실히 연산이 적을 것 같은 방식으로 풀이해도 Runtime의 차이가 나지 않아서 아쉽다.

Solution 1이 String 배열을 4개나 선언한 Solution 2보다 메모리를 많이 사용한다는 점은 놀랍다.

각 for문마다 작동하는 concat의 작동방식이 더하려는 값을 new String으로 만들어 붙이는 내부구조를 가져서 그럴 것 같다.

그렇다면 StringBuilder는 어떨까

> Solution 2-1

class Solution{
    public String intToRoman(int num){
        String[] MMap = {"","M","MM","MMM"};
        String[] CMap = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
        String[] XMap = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
        String[] IMap = {"","I","II","III","IV","V","VI","VII","VIII","IX"};
        StringBuilder sb = new StringBuilder();
        return sb.append(MMap[num/1000]).append(CMap[num/100%10]).append(XMap[num/10%10]).append(IMap[num%10]).toString();
    }
}

> Result 2-1

미미하게 0.3MB정도의 메모리를 절약했다.

>> 문제설명

leetcode.com/problems/remove-palindromic-subsequences/

1. 문제를 잘 읽어야 함.

2. 영어실력을 기르자.

문제에서 주어진 문자열의 일부를 순서를 바꾸지 않은 상태로 지워 subsequence를 만들 수 있다고 했다.

이것을 어떻게 이해한것인지 문자열을 끊어서 일부만 지워 subsequence를 만들 생각을 못했다.

이것을 이해했다면 아주 간단한것인데..

> Solution

class Solution {
    boolean isPal(String str){
        for(int idx = 0; idx < str.length()/2; idx++){
            if(str.charAt(idx) != str.charAt(str.length()-idx-1)) return false;
        }
        return true;
    }
    public int removePalindromeSub(String s) {
        if(s.length() == 0){
            return 0;
        }
        if(isPal(s)){
            return 1;
        }
        return 2;
    }
}

>>문제설명

leetcode.com/problems/short-encoding-of-words/

> First Commit

import java.util.HashSet;

class Solution {
    public int minimumLengthEncoding(String[] words) {
        HashSet<String> indices = new HashSet<>();
        indices.add("");
        int answer = 0;
        for(String word : words){
            boolean check = false;
            for(String str : indices){
                if(str.endsWith(word)){
                    check = true;
                    break;
                }
                if(word.endsWith(str)){
                    check = true;
                    answer -= str.length() + 1;
                    indices.remove(str);
                    indices.add(word);
                    answer += word.length() + 1;
                    break;
                }
            }
            if(check == false) {
                indices.add(word);
                answer += word.length() + 1;
            }
        }
        return answer+1;
    }
}

> Result

> Recommend

import java.util.HashSet;

class Solution {
    public int minimumLengthEncoding(String[] words) {
        int sum = 0;
        HashSet<String> indices = new HashSet<>(Arrays.asList(words));
        for(String word : words){
            for(int idx = 1; idx < word.length(); idx++){
                indices.remove(word.substring(idx));
            }
        }
        for(String str : indices){
            sum += str.length() + 1;
        }
        return sum;
    }
}

문제 설명 보기

>> programmers.co.kr/learn/courses/30/lessons/49189

그래프를 순회하며 가장 비용이 많이 소모된 그래프 노드의 갯수를 반환하는 문제이다.

Node 객체를 구현하여 한번 풀었고, 그래프를 나타내는 이중리스트를 통해 한번 풀어봤다.

> Solution (Node 객체 구현)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

class Solution {
    private class Node{
        int val;

        ArrayList<Node> nextNodeList = new ArrayList<>();

        Node(int val){
            this.val = val;
        }
    }

    public int solution(int n, int[][] edge) {
        int answer = 0;
        HashSet<Node> isTraveledSet = new HashSet<>();
        HashMap<Integer, Node> nodeMap = new HashMap<>();
        LinkedList<Node> nextNodeList = new LinkedList<>();

        for(int idx = 1; idx <= n; idx++){
            nodeMap.put(idx, new Node(idx));
        }

        for(int[] intArr : edge){
            nodeMap.get(intArr[0]).nextNodeList.add(nodeMap.get(intArr[1]));
            nodeMap.get(intArr[1]).nextNodeList.add(nodeMap.get(intArr[0]));
        }

        nextNodeList.add(nodeMap.get(1));
        isTraveledSet.add(nodeMap.get(1));

        while(!nextNodeList.isEmpty()){
            answer = nextNodeList.size();
            for(int cnt = 0; cnt < answer; cnt++){
                for(Node node : nextNodeList.pollFirst().nextNodeList){
                    if(isTraveledSet.add(node)){
                        nextNodeList.addLast(node);
                    }
                }
            }
        }
        return answer;
    }
}

> Result

> Solution (Graph를 나타내는 List)

import java.util.*;

class Solution{
    public int solution(int n, int[][] edge) {
        int answer = 0;
        HashSet<Integer> isTraveledSet = new HashSet<>();
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
        LinkedList<Integer> nextNodeList = new LinkedList<>();

        for(int[] intArr : edge){
            if(!graph.containsKey(intArr[0])){
                graph.put(intArr[0], new ArrayList<>());
            }
            if(!graph.containsKey(intArr[1])){
                graph.put(intArr[1], new ArrayList<>());
            }
            graph.get(intArr[0]).add(intArr[1]);
            graph.get(intArr[1]).add(intArr[0]);
        }
        
        nextNodeList.add(1);
        isTraveledSet.add(1);
        
        while(!nextNodeList.isEmpty()){
            answer = nextNodeList.size();
            for(int cnt = 0; cnt < answer; cnt++){
                for(int node : graph.get(nextNodeList.pollFirst())){
                    if(isTraveledSet.add(node)){
                        nextNodeList.addLast(node);
                    }
                }
            }
        }
        
        return answer;
    }
}

> Result

메모리 사용량과 같은 부분은 확실히 객체를 구현한 방식이 (아주약간)적게 사용되었다.

하지만 효율성에 있어서는 큰 차이를 보여주지 않는다.