Sunday, November 24, 2019

clean code 1장, 2장

책을 읽고 개인적으로 내용을 정리합니다.

요약

서문
- 과거의 프로그래밍과 현재의 프로그래밍이 크게 차이점이 없다.

1장
- 시간이 없다고 코드 리팩토링을 나중으로 미루면 안된다.
- 좋은 구조가 아니면 계속 반복해서 소프트웨어를 출시하게 되는 경우 개발자도 많이 필요하고 업무 효율도 계속 줄어듬

2장
- 범하기 쉬운 실수1
- 중요하지도 않고, 긴급하지도 않은 것을 중요하고, 긴급함으로 격상시키는 일
- 좋은 아키텍쳐를 위해 투쟁하라
- 아키텍쳐를 후순위로 두지 마라
- 개발하는데 더 시간이 많이 걸릴수도 있다.

Thursday, November 7, 2019

요즘 읽고 있는 책 ( 미래를 바꾼 아홉 가지 알고리즘 )

미래를 바꾼 아홉가지 알고리즘

2년전에 한번 도서관에서 빌렸었는데 다시 빌렸다.
대여기간이 11월 18일까지인데 지금 챕터 2개를 읽었음.
- 오류 정정 코드
- 반복 기법
- redundant 기법
- checkSum 기법

- 데이터 압축
- 비손실 압축
- 여기서는 공짜 점심이라고 표현한다.
- hamming code , zip등 압축전과 압축후가 동일
- 손실압축
- JPEG가 대표적인 예
- 압축을 하고 복구를 하게 되면 전과 후가 다름

18일전까지 꾸준히 읽어야 겠다.

Wednesday, October 16, 2019

palindrome

DP가 약하기도하고 공부도 하고 내용도 복습할겸 정리합니다.
기본에서 true 와 false말고 숫자로 표현하면 응용이 가능하다.
참고 링크 https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/

dp 문제를 푸는 나름대로의 방법

DP 에서 row와 column에 어떤값을 정확하게 넣어야 할지가 분명하게 서지 않을때 그림을 그리는것은 도움이 된다.

문제

여러개의 특정 포지션에서 해당 substring이 palindrome인지 체크 하는 로직을 만드세요
left = 시작 지점 right = 끝 지점
ex) str = “abad”

풀이

T = true, F = false로 간주한다.
table[left][right]에 대한 값을 담을 수 있는 table을 만들고 값을 채워나간다.
left == right 같을때는 T 로 셋팅
left != right
- left +1 <= right-1 ( size가 3이상인 경우)
  - str[left] == str[right] && table[left+1][right-1] 인경우 table[left][right] T 셋팅
- left +1 > right-1 ( size 가 2인경우 )
  - str[left] == str[right] 인 경우 table[left][right] T 셋팅

사이즈가 1인경우

사이즈가 2이고 left = 0, right =1 인경우

사이즈가 3이고 left = 0 right =2 인경우

코드

String s = "abac";
boolean[][] table = new boolean[s.length()][s.length()];
for(int i=0; i<s.length(); i++){
    table[i][i] = true;
}
for(int size=2; size<s.length(); size++){
    for(int left=0; left<s.length(); left++){
        int right= left+size-1;
        if(right >= s.length()){
            continue;
        }
        if( size == 2){
            table[left][right] = s.charAt(left) == s.charAt(right);
        }else{
            table[left][right] = s.charAt(left) == s.charAt(right) && table[left+1][right-1];
        }
    }
}

Monday, October 14, 2019

Async Await 사용할때 3가지만 알면 모든게 해결됨

1. async function은 promise 를 리턴함
2. promise는 then이나 await 로 기다림
3. await는 async 안에서만 사용한다.

Wednesday, October 9, 2019

575. distribute candies

https://leetcode.com/problems/distribute-candies/

처음 생각해낸 방법은
두개의 priority qeue 를 생성해서 하나는 asc, 하는 desc 로 생성
sister 가 asc에서 한개씩 빼고, brother가 desc에서 큰 순으로 하나씩 빼다보면 최대 개수가 나올것 같다고 생각이 들었음.
코딩하기 귀찮아서 다른 방법 생각해보니 유니크한 사탕의 종류의 개수에 따라서 간단히 풀수 있었음.
O(N)
종류개수 > length/2 return length/2, else 종류개수

Runtime: 14 ms, faster than 96.34% of Java online submissions for Distribute Candies.

class Solution {
    public int distributeCandies(int[] candies) {
        int [] map = new int[200001];
        int kinds = 0;
        for(int i=0; i<candies.length; i++){
            if(map[candies[i]+100000] == 0){
                kinds ++;
            }
            map[candies[i]+100000]++;
        }
        int maxLen = candies.length/2 ;
        return kinds <= maxLen ? kinds : maxLen;
    }
}

Sunday, October 6, 2019

53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

Runtime: 1 ms, faster than 85.87% of Java online submissions for Maximum Subarray.

O(N) 코드

class Solution {
    public int maxSubArray(int[] nums) {
        
        int max = nums[0];
        int pre = nums[0];
        for(int i=1; i<nums.length; i++){
            if(pre >0){
                pre += nums[i];
                max = Math.max(pre, max);
            }else{
                pre = nums[i];
                max = Math.max(pre, max);
            }
        }
        return max;
    }
}

Divide and Conquer

2ms

ide 사용하고 debugging하는데 시간이 오래 걸림
2개또는 1개로 자른다.
데이터를 머지할때 3가지 데이터를 구한다
- leftMost = 왼쪽 0번째 인덱스 부터 시작해서 가장 큰 sum을 구한다.
- rightMost = 오른쪽 0번째 인덱스부터 왼쪽으로 가장 큰 sum을 구한다.
- full 은 머지한전체 sum, leftMost와 rightMost를 구하기 위해서 필요함.

public class Solution {

    int max =0;
    int[] nums ;
    public int maxSubArray(int[] nums) {
        max = nums[0];
        this.nums = nums;
        divideAndConquer(0, nums.length-1);

        return max;
    }

    public Data divideAndConquer(int start, int end){
        Data data = new Data();
        if(start == end){
            data.full = nums[start];
            data.leftMost = nums[start];
            data.rightMost = nums[start];
            max = Math.max(max ,data.full);
            return data;
        }else if (start == end-1){
            data.full = nums[start] + nums[end];
            data.leftMost = Math.max(nums[start], nums[start] + nums[end]);
            data.rightMost = Math.max(nums[end], nums[start] + nums[end]);
            max = Math.max(max ,data.leftMost);
            max = Math.max(max ,data.rightMost);
            return data;
        }
        int mid = (end-start)/2 + start;
        // left
        Data left = divideAndConquer(start, mid);

        // right
        Data right = divideAndConquer(mid+1 ,end);
            
        if(left.rightMost >0 || right.leftMost >0){
            max = Math.max((Math.max(left.rightMost, 0) + Math.max(right.leftMost, 0)), max);
        }
        
        data.leftMost = Math.max(left.leftMost, left.full + right.leftMost);
        data.rightMost = Math.max(right.rightMost, right.full + left.rightMost);
        data.full = right.full + left.full;
        max = Math.max(max, data.leftMost);
        max = Math.max(max, data.rightMost);
        max = Math.max(max, data.full);
        return data;
    }

  
}

class Data {
    int leftMost;
    int full;
    int rightMost;
}

Tuesday, October 1, 2019

1009. Complement of Base 10 Integer

https://leetcode.com/problems/complement-of-base-10-integer/

첫번째 방법

2 로 나누기 비트연산하면서 0 to 1 , 1 to 0으로 변경한 비트 값을 더해줌
2번째 방법
digit을 구한후 해당 xor 연산으로 한번에 풀었음

Runtime: 0 ms, faster than 100.00% of Java online submissions for Complement of Base 10 Integer.

class Solution {
    public int bitwiseComplement(int N) {
        if(N==0){
            return 1;
        }
        
        int digit = 0;
        int sum =0;
        while (N> 0){
            int remainder = N % 2 ;
            N = N>>1;
            if(remainder == 0 ){
                sum += 1<< digit;
            }
            digit++;            
        }
       
        return sum;
    }
}

두번째 코드

class Solution {
    public int bitwiseComplement(int N) {
        int digit =1;
        int n = N;
        while((n= n >> 1) > 0){
            digit++;
        }
        
        int compare = (2 << digit-1) -1;
        return N^compare;        
    }
}

Thursday, September 26, 2019

java shift 연산

Shift 연산

bit 연산은
16진수? int를 표현하는 방법
아래 예제는 전부다 16을 출력

  int a = 0x010;
  System.out.println(a);
  a = 0x0010;
  System.out.println(a);
  a = 0x0000010;
  System.out.println(a);
  a = 0x000000000000000000000000000000000000000010;
  System.out.println(a);

16진수를 표현하는 방법?
- 0x에 0 to f 까지 표현할수 있다. (0 -15)

<< number , >> number 연산자

비트값을 왼쪽으로 number만큼 움직여준다.

int a = 8;
System.out.println(Integer.toBinaryString(a));
// 001000
a = a << 2;
System.out.println(Integer.toBinaryString(a));
// 100000
a = a >> 2;
System.out.println(Integer.toBinaryString(a));
// 001000

1을 오른쪽으로 비트 연산하게 되는경우 어떻게 나올까??

int a = 1;
System.out.println(Integer.toBinaryString(a));
// 00001
a = a >> 5;
System.out.println(Integer.toBinaryString(a));
// 0

으로나온다.

Thursday, September 19, 2019

1029. Two City Scheduling

https://leetcode.com/problems/two-city-scheduling/

a와 b의 갭을 구한다.
위의 갭이 큰 값으로 descending 정렬한다.
갭순으로 정렬된것중에 중에 작은 값 기준으로 이렇게 정렬되어있다면
- a b a a a b
- a b a a b b 이렇게 분류해서 더한다. 왜냐하면 반틈씩 인터뷰를 진행해야한다고 나와있어서
위내용을 코딩화 하니깐 생각보다 복잡해졌음

Runtime: 2 ms
Memory Usage: 38.5 MB

class Solution {
     public int twoCitySchedCost(int[][] costs) {
        List<Schedule> list = new  ArrayList<Schedule> ();

        for( int i=0; i<costs.length; i++){
            list.add(new Schedule(costs[i][0], costs[i][1], Math.abs(costs[i][0] - costs[i][1]) ));
        }

        Collections.sort(list, new Comparator<Schedule>() {
            @Override
            public int compare(Schedule o1, Schedule o2) {
                return o2.gap - o1.gap;
            }
        });

        int len = costs.length/2;
        int acount = 0;
        int bcount = 0;
        int index =0;
        int minsum =0;
        while(acount<len && bcount <len){
            Schedule schedule = list.get(index++);
            if(schedule.a< schedule.b){
                acount++;
                minsum+= schedule.a;
            }else{
                bcount++;
                minsum+= schedule.b;
            }
        }

        if(acount != len){
            for (int i=index; i<list.size(); i++ ){
               minsum += list.get(i).a;
               acount++;
            }
        }

        if(bcount != len){
            for (int i=index; i<list.size(); i++ ){
                minsum += list.get(i).b;
                bcount++;
            }
        }
        return minsum;

    }

    class Schedule {
        int a;
        int b;
        int gap;

        Schedule(int a, int b, int gap){
            this.a = a;
            this.b = b;
            this.gap = gap;
        }
    }
}

두번째 코드

위의 로직을 조금더 깔끔하게 하는 방법
solution을 보니깐 compare 하는부분에서 조금더 잘 정렬하던데 머리로 한 70% 이해했음. 코드 짜라고 하면 어려움
다음에 한번더 보면 좋을것 같은 문제

public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Math.abs(o2[0]- o2[1]) - Math.abs(o1[0]- o1[1]) ;
            }
        });

        int len = costs.length/2;
        int acount = 0; int bcount = 0; int index =0; int minsum =0;
        while(acount<len && bcount <len){
            int[] schedule = costs[index++];
            if(schedule[0]< schedule[1]){
                acount++;
                minsum+= schedule[0];
            }else{
                bcount++;
                minsum+= schedule[1];
            }
        }
        for (int i=index; i<costs.length; i++ ){
            if(bcount != len){
                minsum += costs[i][1];
                bcount++;
            }else{
                minsum += costs[i][0];
                acount++;
            }
        }
        return minsum;
     }

Sunday, September 15, 2019

459. repeated-substring-pattern

https://leetcode.com/problems/repeated-substring-pattern/
문제 난이도는 easy 이지만 생각도 힘들었고 생각을 코드로 구현도 힘들었음.
파티션으로 나누어서 모든게 일치하면 통과하는식으로 구현
아래 그림으로 로직 표현

Runtime: 15 ms, faster than 71.70% of Java online submissions for Repeated Substring Pattern.
Memory Usage: 36.5 MB, less than 100.00% of Java online submissions for Repeated Substring Pattern.

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        //abcabcabcabc

        char [] arr = s.toCharArray();

        // distance
        for (int i=1; i<=arr.length/2; i++){
            if(arr.length % i !=0){
                continue;
            }
            boolean allSame = true;
            // 각 파티션
            second :
            for(int j=i; j<arr.length; j+=i){
                // 파티션의 distacne 까지 비교
                for(int k=0; k<i; k++){
                    if(arr[k] != arr[j+k]){
                        allSame = false;
                        break second;
                    }
                }
            }
            if(allSame){
                return true;
            }
        }
        return false;
    }
}

83. remove-duplicated-from-sorted

https://leetcode.com/problems/remove-duplicates-from-sorted-list/
head.val 과 head.next.val 을 비교해서 같으면 head.next.next를 head.next에 연결해준다.

Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Duplicates from Sorted List.
Memory Usage: 36.2 MB, less than 100.00% of Java online submissions for Remove Duplicates from Sorted List.

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode mockHead = new ListNode(-1);
        mockHead.next = head;

        while(head != null && head.next != null){
            if(head.val == head.next.val){
                head.next = head.next.next;
                continue;
            }
            head = head.next;
        }

        return mockHead.next;
        
    }
}

695. max-area-of-island

방문한 곳은 1 to 2로 치환하고 연결된 모든 섬의 count를 구해서 max sum을 구한다.

Runtime: 2 ms, faster than 100.00% of Java online submissions for Max Area of Island.
Memory Usage: 43.6 MB, less than 55.56% of Java online submissions for Max Area of Island.

public class Solution {
    int maxSum =0;
    public  int maxAreaOfIsland(int[][] grid) {
        if(grid.length ==0){
            return 0;
        }

        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j] == 1){
                    int sum = visit(i, j, grid);
                    maxSum = Math.max(maxSum, sum);
                }
            }
        }
        return maxSum;
    }

    private int visit(int i, int j, int[][] grid) {
        int sum=0;
        if(i >=0 && i<grid.length && j>=0 && j<grid[i].length){
            if(grid[i][j] ==1){
                sum++;
                grid[i][j] =2;
                sum+=visit(i+1, j, grid);
                sum+=visit(i-1, j, grid);
                sum+=visit(i, j-1, grid);
                sum+=visit(i, j+1, grid);
            }
        }
        return sum;
    }
}

Monday, September 9, 2019

342. power of four

https://leetcode.com/problems/power-of-four/

해결과정

10진수 to 2진수

4 -> 100
16 -> 10000
64 -> 1000000

Runtime: 7 ms, faster than 5.74% of Java online submissions for Power of Four.
Memory Usage: 34.3 MB, less than 6.67% of Java online submissions for Power of Four.

public boolean isPowerOfFour(int num) {
        String binarySring = Integer.toBinaryString(num);
        if(binarySring.length()>=3 && (binarySring.length()-1)%2 ==0){
           return  "1".equals(binarySring.replaceAll("0", ""));
        }

        return false;
    }

second soluton

민수님 numberOfTrailingZero꺼랑 And 논리 연산자를 이용함.
100
011 의 and 0

class Solution {
    public boolean isPowerOfFour(int num) {
        if(num==0)return false;
        return Integer.numberOfTrailingZeros(num) % 2==0 && ((num & num-1) == 0);
    }
}

Tuesday, September 3, 2019

979. Distribute Coins in Binary Tree

https://leetcode.com/problems/distribute-coins-in-binary-tree/

이문제는 풀이는 조금더 생각을 해서 코딩 라인수를 줄여야할필요가 있음
실제 코인의 이동이 아니라 코인이 없더라도 음수대로 값을 채움 ( 있는것처럼 가상의 코인을 움직인다 )
data를 채우는것은 inorder 순서로 적용

Runtime: 1 ms, faster than 87.01% of Java online submissions for Distribute Coins in Binary Tree.
Memory Usage: 37.7 MB, less than 100.00% of Java online submissions for Distribute Coins in Binary Tree.

public class Solution {

    int count =0;
    public int distributeCoins(TreeNode root) {
        if(root == null){
            return 0;
        }
        conqer(root);

        return count;
    }

    public void conqer ( TreeNode root){
        if(root.left != null){
            conqer(root.left);
            calclator(root, root.left);
        }
        if(root.right != null){
            conqer(root.right);
            calclator(root, root.right);
        }
    }
    public void calclator(TreeNode root, TreeNode child){
        if(child.val <=0){
            int increase = 1-child.val;
            count += increase;
            child.val = 1;
            root.val = root.val - increase;
        }else {
            int decrease =  child.val - 1;
            count += decrease;
            child.val = 1;
            root.val = root.val + decrease;
        }
    }
}

1047. Remove All Adjacent Duplicates In String

-https://leetcode.com/problems/verifying-an-alien-dictionary/

Hi! I’m your first Markdown file in StackEdit. If you want to learn about StackEdit, you can read me. If you want to play with Markdown, you can edit me. Once you have finished with me, you can create new files by openi

1차 코드

49 ms	38.5 MB	java

class Solution {
    public String removeDuplicates(String S) {
        // "abbaca"

        if(S.length()<= 1){
            return S;
        }

        char[] chars = S.toCharArray();
        Stack<Character> stack  = new Stack<Character>();
        for(int i=0; i<chars.length; i++){


            if(!stack.isEmpty()) {
                Character cha = stack.peek();
                if (cha != null && cha == chars[i]) {
                    stack.pop();
                    continue;
                }
            }
            stack.push(chars[i]);
        }

        char [] result = new char[stack.size()];
        int index = stack.size()-1;
        while(!stack.isEmpty()){
            Character  last = stack.pop();
            result[index--] = last;
        }

        return new String(result);
    }
}

2차코드

자료구조 안쓰고 다시 한번더 풀어봐야겠다.
조건이 바로 앞뒤 2개의 character 값만 비교하는거라서 마지막 last index를 기억하는걸로
앞뒤가 서로 다를때 last index = currentIndex
앞뒤가 서로 같을때 find last index and check index ‘0’

Runtime: 4 ms, faster than 98.11% of Java online submissions for Remove All Adjacent Duplicates In String.
Memory Usage: 37.7 MB, less than 100.00% of Java online submissions for Remove All Adjacent Duplicates In String.

class Solution {
    public String removeDuplicates(String S) {
        // "abbaca"

       if(S.length()<= 1){
            return S;
        }

        char[] chars = S.toCharArray();

        int last = 0;
        for(int i=1; i<chars.length; i++){
            if(last >= 0 && chars[last] == chars[i]){ // 같을때
                chars[i] = '0';
                chars[last] = '0';
                last --;
                while(last >=0 && chars[last] == '0'){
                    last --;
                }
            }else{
                last = i;
            }
        }
        StringBuilder builder = new StringBuilder();
        for(int i=0; i<chars.length; i++){
            if(chars[i] != '0'){
                builder.append(chars[i]);
            }
        }

        return builder.toString();
    }
}

3차코드

Runtime: 3 ms, faster than 99.83% of Java online submissions for Remove All Adjacent Duplicates In String.
Memory Usage: 38.1 MB, less than 100.00% of Java online submissions for Remove All Adjacent Duplicates In String.

2차코드에서 StringBilder 제거

// "abbaca"

       if(S.length()<= 1){
            return S;
        }

        char[] chars = S.toCharArray();

        int last = 0;
        int resltLenth = chars.length;
        for(int i=1; i<chars.length; i++){
            if(last >= 0 && chars[last] == chars[i]){ // 같을때
                chars[i] = '0';
                chars[last] = '0';
                last --;
                resltLenth-=2;
                while(last >=0 && chars[last] == '0' ){
                    last --;
                }
            }else{
                last = i;
            }
        }

        char[] result = new char[resltLenth];
        int resultIndex =0;
        for(int i=0; i<chars.length; i++){
            if(chars[i] != '0'){
                result[resultIndex++] = chars[i];
            }
        }
        return new String(result);