배열

 

 

-> 다시 도전 (물방울 가두기, 자신을 제외한 곱셈, 3더하기)

 

-> 투포인터로 문제 해결하는 방식 조금 배웠다 (물방울 가두기,3더하기..)

-> 중복값 계산하기 귀찮으면 Map에다가 key로 때려 박으면 쫌 다루기 쉬울 때가 있다.

-> map.containsKey, Arrays.asList, new ArrayList<>(map.values()) 야무지게 외워둡시다. 

 

> 물방울 가두기 (리트코드 - 42)

 

1. 내 풀이(3ms)

public int trap(int[] height) {

        int maxHeight = Arrays.stream(height).max().getAsInt();
        int rainWidth=0;
        int left = 0;
        int right = height.length - 1;
        int leftMax = height[left];
        int rightMax = height[right];

        while(left <= right){
            
            

            //각 왼쪽 오른쪽 max와 포인터 움직이며 차이 더하기 
            if(rightMax < height[right]){
                rightMax = height[right];
            }else if(height[right] < rightMax){
                rainWidth += rightMax - height[right];
                height[right] =  rightMax ;
            }

            if(leftMax < height[left]){
                leftMax = height[left];
            }else if(height[left] < leftMax){
                rainWidth += leftMax - height[left];
                 height[left]  =  leftMax;
            }


            //maxHeight만나면 움직이지마! 
            if(height[right] < maxHeight ){
                right--;
            }

            if(height[left] < maxHeight){
                left++;
            }

            //양 끝값이 같아서 움직이지 못할 때 풀어줌 혹은 left,right 같을때도 한번 움직이기 
            //이때 leftMax와 rightMax는 maxHeight로 설정해야한다.
            if(height[right] == maxHeight && height[left] == maxHeight && left<right ){
                right--;
                left++;
                rightMax = maxHeight;
                leftMax = maxHeight;
            }else if(left == right){
                right--;
                left++;
            }
        }

        

        return rainWidth;
    }

 

 

2. 투포인터 최대로 이동 (0ms ....)

public int trap(int[] height) {

     	int volume = 0;
        int left =0;
        int right = height.length - 1;
        int leftMax = height[left];
        int rightMax = height[right];
        
        while(left < right){
        	leftMax = Math.max(height[left],leftMax);
            rightMAx = Math.max(height[right],rightMax);
            
            if(leftMax <= rightMax){
            	volume += leftMax - height[left];
                left++;
            }else{
            	volume += rightMax - height[right];
                right--;
            }
        }
        return volume;
    }

 

 

> 두 수의 합 (1)

 

1. 내 풀이 (49ms)

 

 public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for(int i=0; i< nums.length-1; i++){
            
            for(int j=i+1; j<nums.length;j++){
                if(nums[j] == target-nums[i]){
                    result[0] = i;
                    result[1] = j;
                }
            }
        }
        return result;
    }

 

2. 첫 번째 수를 뺀 결과 키 조회

 

 public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> numsMap = new HashMap<>();
        
        for(int i = 0; i< nums.length; i++){
        	numsMap.put(nums[i],i);
        }
        
        //tartget에서 수를 뺀 것이 조회결과에 있으면 정답
        for(int i=0; i<nums.length;i++){
        	if(numsMap.containsKey(target - nums[i]) && i != numsMap.get(target - nums[i])){
            	return new int[]{i,numsMap.get(target - nums[i])};
            }
        }
        
        return null;
    }

 

3. 투 포인터 이용 

 

 > 투포인터는 정렬된 배열에서 값을 찾거나, 배열을 자르는 것에 쫌 더 이점이 있음! 인덱스를 찾는 문제에서는 투 포인터 적용하면 잘 안풀릴 수 있음 주의

 

 

> 배열 파티션 1  (리트코드 - 561)

 

 

1. 내 코드 (15ms)

   public int arrayPairSum(int[] nums) {
          Arrays.sort(nums);
        int result=0;
        for(int i=0; i<nums.length; i=i+2){
            result += Math.min(nums[i],nums[i+1]);
        }
        return result;
    }

 

 

 

> 자신을 제외한 배열의 곱 (리트코드 - 238) 

 

 public int[] productExceptSelf(int[] nums) {
        int[] array = new int[nums.length];

        int p = 1;

        //아.. 왼쪽으로 한번 민다음 곱하고 오른쪽으로 한번 밀고 곱하기
       // 오른쪽으로 한번 밀고 곱하기 
        for(int i=0; i<nums.length; i++){
            array[i] = p;
            p*=nums[i];
        }

        p=1;
        for(int i=nums.length-1; i>=0; i--){
               array[i] *=p;
               p *= nums[i];
        }

        return array;
    }

 

 

> 주식을 사고팔기 가장 좋은 시점 (리트코드 - 121)

 

1. 내 풀이(2ms)

 public int maxProfit(int[] prices) {
    
        int maxProfit =0;
        int buy = prices[0];

        for(int i=1; i<prices.length;i++){
            if(buy>prices[i]){
                buy = prices[i];
            }else if(prices[i] - buy >0 && maxProfit < prices[i] - buy){
                maxProfit = prices[i]-buy;
            }
        }
        return maxProfit;
    }