Array

개념

1. Math.max(max, a) 이용하여 max 구하기
2. sum = sum + nums[] ( sum += nums[] ) 이용하여 합 구하기

문제

1. maxProfit - Math.max() 이용

문제)

• 최대 한번의 거래만 가능할 때 (주식을 하나 사고 또는 하나 파는) 최대 수익이 얼마인지 찾아라
• 입력으로 i번째 요소가 i일에 주어진 주식의 가격인 배열을 주어진다.
• 주식을 구입하기 전에는 주식을 팔 수 없다.

Input : int[] prices = { 8, 2, 6, 5, 1, 7, 5 }
Output : 6
설명) : 5일에 구매 6일에 판매 => 이익 7 - 1 = 6

풀이

1. 최대 이익을 담을 max와 배열 중 제일 작은 값을 담을 min 값
2. for문을 돌려서 min 과 max를 갱신
3. min의 초기값은 prices[0] (이유 : 첫번째로 사야하는 주식이기 때문)
4. i번째 값이 min보다 클 경우 Math.max()를 이용하여 max를 갱신

소스

public class Q1 {

	public static void main(String[] args) {
		int[] prices = { 8, 2, 6, 5, 1, 7, 5 };

		System.out.println(maxProfit(prices));
	}

	public static int maxProfit(int[] prices) {
		if (prices.length == 0) {
			return 0;
		}

		int max = 0;
		int min = prices[0];

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

		return max;
	}

}

2. subArraySum -> sum+= 이용

문제)
Integer 배열 nums 와 k가 있을 때 subarray의 합이 k와 같은 경우의 수를 출력

Input : int[] nums = {3, 4, 7, 2, -3, 1, 4, 2} , int k = 7
Output : 4

풀이

1. 갯수를 저장할 count 변수 선언
2. 2중 for문을 돌려 구현
3. 배열의 0부터 시작하면서 sum을 구하고 그 sum이 k와 동일할 때 count++해준다.

소스

public class Q2 {

	public static void main(String[] args) {
		int[] nums = { 3, 4, 7, 2, -3, 1, 4, 2 };
		int k = 7;
		System.out.println(subArraySum(nums, k));

	}

	public static int subArraySum(int[] nums, int k) {
		int count = 0;

		for (int i = 0; i < nums.length; i++) {
			int sum = 0;
			for (int j = i; j < nums.length; j++) {
				sum += nums[j];

				if (sum == k) {
					count++;
				}
			}
		}

		return count;
	}

}

3. subArraySum -> map 이용

2번 문제와 동일

풀이

1. Map을 이용하는데, Key 값은 sum으로 넣고 Value는 기본 1 만일 sum이 이미 있으면 그 sum의 value + 1를 하여 넣어준다.
2. sum - k 가 Map에 있는 경우 value 값을 가져와서 count에 더해준다.
3. sum - k를 해주는 이유는 앞에 예제에서 마지막의 합이 20일 때를 예를들면 20 - 7 = 13이고 13 역시 이미 map안에 있다. 그러면 13 다음에 20이 나왔다는 것은 13 이후에 합이 7이 되는 것이 존재한다는 의미인 것이다.

getOrDefault() : 해당 key를 포함하면 그 value를 가져온다. 포함 안하면 default 값을 가져온다. 꼭 기억하기

소스

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

public class Q3 {

	public static void main(String[] args) {
		int[] nums = { 3, 4, 7, 2, -3, 1, 4, 2 };
		int k = 7;
		System.out.println(subArraySum_map(nums, k));

	}

	public static int subArraySum_map(int[] nums, int k) {
		int count = 0;

		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		map.put(0, 1);
		int sum = 0;

		for (int i = 0; i < nums.length; i++) {
			sum += nums[i];

			if (map.containsKey(sum - k)) {
				count += map.get(sum - k);
			}

			map.put(sum, map.getOrDefault(sum, 0) + 1);
		}

		return count;
	}

}

참고

인프런 강의 : 코딩테스트 전 꼭 알아야 할 개념과 문제(with 자바) - 푸샵맨 코딩스터디