11 to 9, Day 18

Today, ToDoList

• 배열 자료구조

• LeetCode - 2. Add Two Numbers

---

package arrays;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

// 숫자로 구성된 배열이 주어졌을 때 그 배열에 중복된 숫자가 있는지 확인하는 함수를 작성하라.
// 중복된 숫자가 있다면 true 없다면 false.
public class DupCheck {

    // 시간 복잡도 O(N^2), 공간 복잡도 O(1)
    // 시간 복잡도가 너무 높음.
    public boolean solution1(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if ( nums[i] == nums[j] ) {
                    return true;
                }
            }
        }
        return false;
    }

    // 시간 복잡도 O(NlogN), 공간 복잡도 O(logN)
    // 배열을 정렬시켜서 순회를 한번만 할 수 있다.
    // 즉 시간 복잡도를 줄일 수 있다.
    // 정렬의 시간 복잡도는 O(NlogN), 공간 복잡도는 O(logN) 이다.
    public boolean solution2(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-1; i++) {
            if ( nums[i] == nums[i+1] ) {
                return true;
            }
        }
        return false;
    }

    // Set 자료구조는 Hash 값으로 조회하기 때문에
    // 시간 복잡도 O(1)으로 요소를 검색하고 포함하는지 확인할 수 있다.
    // 순회가 한번만 일어나기 때문에 시간복잡도는 줄어들지만, Set을 사용하기 때문에 공간 복잡도는 증가한다.
    // 시간 복잡도 O(N), 공간 복잡도 O(N)
    public boolean solution3(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if ( set.contains(nums[i]) ) {
                return true;
            } else {
                set.add(nums[i]);
            }
        }
        return false;
    }


    public static void main(String[] args) {
        int[] nums = {1,2,2,3,4,5};
        System.out.println("Leng : "+nums.length);

        DupCheck dupCheck = new DupCheck();
        System.out.println(dupCheck.solution1(nums));
        System.out.println(dupCheck.solution2(nums));
        System.out.println(dupCheck.solution3(nums));
    }


}

---

//주어진 문자열을 거꾸로 뒤집은 문자열을 만드는 함수를 작성하라.
public class ReverseCharArray {

    //시간복잡도 O(N), 공간복잡도 O(N)
    public char[] solution1(char[] chars) {
        char[] newChars = new char[chars.length];
        for (int i = 0; i < chars.length; i++) {
            newChars[chars.length-1-i] = chars[i];
        }
        return newChars;
    }

    //별도의 배열을 사용하지 않고 배열 swap을 이용하여 공간복잡도 낮추기
    //시간복잡도 O(N), 공간복잡도 O(1)
    public char[] solution2(char[] chars) {
        for (int i = 0; i < chars.length/2; i++) {
            char tmpChar = chars[i];
            chars[i] = chars[chars.length-1-i];
            chars[chars.length-1-i] = tmpChar;
        }
        return chars;
    }

    public static void main(String[] args) {
        ReverseCharArray reverseString = new ReverseCharArray();
        String str = "Happy New Year";
        System.out.println(reverseString.solution1(str.toCharArray()));
        System.out.println(reverseString.solution2(str.toCharArray()));
    }
}

---

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

//숫자로 구성된 배열 numbers와 target 숫자 하나가 주어졌을 때 numbers 배열에 들어있는 두 수를 더해 target 숫자를 만들 수 있는 인덱스 두개를 찾는 함수를 작성하라.
//
//예) numbers = [2, 3, 5, 7] target = 8, 8을 만들 수 있는 3과 5의 인덱스인 1, 2를 리턴해야 한다.
//예) numbers = [1, 2, 6, 8] target = 9, 9를 만들 수 있는 1과 8의 인덱스인 0, 3을 리턴해야 한다.
//
//numbers 배열에 중복되는 숫자는 없으며 target 숫자를 만들 수 있는 조합은 하나 뿐이라고 가정해도 좋다. 
public class TwoSum {

    //단순 순회
    //시간복잡도 O(N^2), 공간복잡도 O(1)
    public int[] solution1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if ( nums[i] + nums[j] == target ) {
                    return new int[]{i,j};
                }
            }
        }
        throw new RuntimeException();
    }

    //순회에서 어떤 요소에 대해 찾아야 하는 값은 (target-요소)로 정해져 있다.
    //Map<val, index>을 이용하여 시간복잡도를 줄일 수 있다.
    //Map의 get, containsKey 메소드의 시간복잡도는 O(1)
    //시간복잡도 O(N), 공간복잡도 O(N)
    public int[] solution2(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            if ( map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i ) {
                return new int[] {i, map.get(target - nums[i])};
            }
        }
        throw new RuntimeException();
    }

    public static void main(String[] args) {
        TwoSum sumLocation = new TwoSum();
        System.out.println(Arrays.toString(sumLocation.solution1(new int[]{2,3,5,7}, 8)));
        System.out.println(Arrays.toString(sumLocation.solution2(new int[]{2,3,5,7}, 8)));
    }
}

---

import java.util.Arrays;

//1부터 100 까지의 숫자 중에 50개의 랜덤한 숫자가 들어있는 배열이 있다. 이 배열을 O(n)의 시간 복잡도로 정렬하라.
public class SortingNums {

    //Arrays.sort는 시간복잡도 O(NlogN)이므로 사용할 수 없다.
    //주어지는 배열의 크기(50)나 범위가 제한되어 있으므로 또 다른 배열을 사용하여 해결할 수 있다.
    public int[] solution1(int[] nums) {
        int[] sortingArr = new int[100];
        for (int i = 0; i < nums.length; i++) {
            sortingArr[nums[i]] = nums[i];
        }

        int index = 0;
        for (int i = 0; i < sortingArr.length; i++) {
            if ( sortingArr[i] != 0 ) {
                nums[index] = sortingArr[i];
                index++;
            }
        }
        return nums;
    }

    public static void main(String[] args) {
        SortingNums sortingNums = new SortingNums();
        int[] nums = new int[50];
        for (int i = 49; i > 0; i--) {
            nums[i] = i+1;
        }
        System.out.println(Arrays.toString(sortingNums.solution1(nums)));
    }

}

---

LeetCode - 2. Add Two Numbers

/**
 * 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 addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode currentNode = new ListNode();
        ListNode head = currentNode;
        int carry = 0;
        while (l1!=null || l2!=null) {
            if (carry > 0) {
                currentNode.val = 1;
                carry = 0;
            }
            if ( l1==null ) {
                currentNode.val += l2.val;
                if ( currentNode.val >= 10) {
                    carry++;
                    currentNode.val -= 10;
                }
                l2 = l2.next;
            } else if (l2==null) {
                currentNode.val += l1.val;
                if ( currentNode.val >= 10) {
                    carry++;
                    currentNode.val -= 10;
                }
                l1 = l1.next;
            } else {
                currentNode.val += l1.val + l2.val;
                if ( currentNode.val >= 10) {
                    carry++;
                    currentNode.val -= 10;
                }
                l1 = l1.next;
                l2 = l2.next;
            }
            if (l1!=null || l2!=null || carry > 0) {
                currentNode.next = new ListNode();
                currentNode = currentNode.next;
            }
        }
        return head;
    }
}