myBlog

>> 문제설명

leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

> 1차원 배열로 주어진 변동하는 주식 가격을 받아 가장 쌀 때 사고, 가장 비쌀때 파는 문제다.

> 주식을 사거나 팔때 수수료가 발생한다.

> IDEA1

문제에서는 현재 상태를 주식을 판 상태(주식을 살 수 있는 상태)와 주식을 산 상태(주식을 사서 들고 있는 상태) 두가지로 분류 할 수 있다.

현재 상태가 가질 수 있는 가장 큰 이익을 저장하며 마지막 상태에서 가질 수 있는 가장 큰 이익값을 반환한다. (동적 계획법)

> Solution

class Solution {
    public int maxProfit(int[] prices, int fee) {
        // Set initial state.
        int sellState = 0;
        int buyState = -prices[0];

        for(int idx = 1; idx < prices.length; idx++){
            sellState = Math.max(
                    sellState // 판 상태 -> 판 상태
                    , prices[idx]-fee+buyState// 산 상태 -> 판 상태
            );
            buyState = Math.max(
                    sellState - prices[idx]// 판 상태 -> 산 상태
                    , buyState // 산 상태 -> 산 상태
            );
        }
        return Math.max(buyState, sellState);
    }
}

> IDEA2

주식 가격으로 생각한다면, 저점에서 사서 고점에 파는걸 반복하면 가장 많은 이득을 가지게 된다.

두개의 변수를 관리한다.

하나는 저점에서 산 주식을 현재 가격에 팔았을때 최대로 가지는 수익.

하나는 전고점 대비 하한가, 즉 매수타이밍의 가격.

두개의 변수를 관리하여 문제를 해결 할 수도 있다.

>> 문제설명

leetcode.com/problems/swapping-nodes-in-a-linked-list/

정말 single linked list에서 2개의 node를 swap하려고 하다가 결국 숫자만 바꾸기로 했다.

객체를 swap하는건 무척 어렵지만 그냥 숫자만 바꾸는건 간단하다.

이대로 통과가 되는걸 보니 문제에서도 이걸 의도한 듯 하다..

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ArrayList<ListNode> nodeList = new ArrayList<>();
        ListNode next = head;
        while(next != null){
            nodeList.add(next);
            next = next.next;
        }
        int tmp = nodeList.get(k-1).val;
        nodeList.get(k-1).val = nodeList.get(nodeList.size()-k).val;
        nodeList.get(nodeList.size()-k).val = tmp;

        return head;
    }
}

>> 문제설명

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

>> 문제설명

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;
    }
}

>>문제설명

leetcode.com/problems/average-of-levels-in-binary-tree/

>mySolution

class Solution {
    public double getAverage(LinkedList<TreeNode> linkedList){
        long sum = 0;
        for(TreeNode treeNode : linkedList){
            sum += treeNode.val;
        }
        return (double)sum / linkedList.size();
    }

    public List<Double> averageOfLevels(TreeNode root) {
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        LinkedList<TreeNode> nextList = new LinkedList<>();
        List<Double> answerList = new ArrayList<>();
        linkedList.add(root);

        while (!linkedList.isEmpty()){
            answerList.add(getAverage(linkedList));
            nextList.clear();
            while (!linkedList.isEmpty()){
                TreeNode treeNode = linkedList.poll();
                if(treeNode.left != null) nextList.add(treeNode.left);
                if(treeNode.right != null) nextList.add(treeNode.right);
            }
            linkedList.addAll(nextList);
        }

        return answerList;
    }
}

> Result

> Modify

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        List<Double> answerList = new ArrayList<>();
        linkedList.add(root);
        long sum;
        int size;

        while (!linkedList.isEmpty()){
            sum = 0;
            size = linkedList.size();
            for(int idx = 0; idx < size; idx++){
                TreeNode treeNode = linkedList.poll();
                sum += treeNode.val;
                if(treeNode.left != null) linkedList.addLast(treeNode.left);
                if(treeNode.right != null) linkedList.addLast(treeNode.right);
            }
            answerList.add((double)sum / size);
        }
        return answerList;
    }
}

>Result

leetCode 엔진 자체가 같은 코드를 넣어도 결과가 다르게 나온다는 점을 알았다.