[코딩테스트, LeetCode] 문제풀이 #1, #9, #88, #121, #350, #704

LeetCode 문제풀이를 하며, 주요 포인트들을 기록해보고자 한다.

1. TwoSum

int array와 target이 주어지면 더해서 target이 되는 수의 index를 int array로 반환하는 문제이다.
Map의 containsKey를 사용하기 위해 value에 index, key에 숫자를 넣어주었다.(모두 값이 다르다는 조건이 있어서 가능했다.)
실행시간 4ms

class Solution {
    public int[] twoSum(int[] nums, int target) {

       int[] answer = new int[2];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            int temp = nums[i];
            if(map.containsKey(target-temp)){
                answer[0] = i > map.get(target-temp)? map.get(target-temp) : i;
                answer[1] = i > map.get(target-temp)? i: map.get(target-temp) ;
                // {1,0} 대신 {0,1}로 반환해야 해서 이렇게 짰는데 
                // 그냥 return new int[]{map.get(target-temp), i}; 
                // 하면 될 것 같다.
            }
            map.put(nums[i], i);
        }


        return answer;
    }
    
}

9. Palindrome Number

정수가 주어졌을 때, 앞뒤로 대칭인지를 파악하는 문제이다.
char array로 변환하여 구하니 어렵지 않았다.
실행시간 7ms

class Solution {
    public boolean isPalindrome(int x) {
         if(x<0) return false;
        char [] arr = String.valueOf(x).toCharArray();
//        System.out.println(Arrays.toString(arr));
        for(int i=0; i< arr.length/2; i ++){
            if(arr[i] != arr[arr.length - 1- i]) return false;
        }
        return true;
        
    }
}

88. Merge Sorted Array

꼼수로 푼 거 같긴 하다.
실행시간 0ms

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=0; i<n; i++){
            nums1[m+i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

121. Best Time to Buy and Sell Stock

Greedy 로 푸는 법이 안떠올라 해답을 참조했다.
실행시간 1ms

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int min = prices[0];

        for(int i=1; i<prices.length; i++){
            if(prices[i]> min) max = Math.max(prices[i]- min, max);
            else min = prices[i];
        }
        return max;
    }
}

350. Intersection of Two Arrays II

두 int[]가 주어졌을 때, 겹치는 부분을 반환하는 문제.

• stream 의 boxed(): primitive type -> wrapper type변환
• list의 길이에 따라 solution 함수를 호출하고, 겹치는 부분을 추출한 뒤 list -> array 변환을 했다.
• stream을 intellij 도움 없이도 슥슥 사용할 수 있게끔 연습해야겠다.
  실행시간 18ms > 너무 느려서 다른 방법 다시 풀어봐야함.

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
       List <Integer> list1 = Arrays.stream(nums1).boxed().collect(Collectors.toList());
       List <Integer> list2 = Arrays.stream(nums2).boxed().collect(Collectors.toList());

       if(nums1.length > nums2.length){
        return solution(list1, list2);
       }
       else return solution(list2, list1);
    }
    public static int[] solution(List<Integer> l1, List<Integer> l2){
        List<Integer> answer = new ArrayList<>();
        for(int i=0; i<l1.size(); i++){
            if(l2.contains(l1.get(i))) {
                answer.add(l1.get(i));
                l2.remove(l1.get(i));
            }
        }
       return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

704. Binary Search

target의 Index를 반환하는 문제. 없으면 -1 반환.
Arrays.binarySearch를 사용해도 통과는 시켜주었다.
실행시간 0ms

class Solution {
    public int search(int[] nums, int target) {
         int index = Arrays.binarySearch(nums, target);

        return index >=0 ? index : -1;
    }
}

직접 짜본 코드

public static int bsearch(int start, int end, int[] nums, int target){
        if(start == end) {
            if(target == nums[start]) return start;
            else return -1;
        }
        else if (end == start +1){

            if(target == nums[start]) return start;
            else if (target == nums[end]) return end;
            else return -1;
        }
        else {

            int mid = (start + end) / 2;

            if (target > nums[mid]) return bsearch(mid + 1, end, nums, target);
            else if (target < nums[mid]) return bsearch(start, mid - 1, nums, target);
            else return mid;
           
        }
    }