해싱을 통한 부분수열(음수포함)의 합이 m이는 경우 이론 - java

 

nums = {1,  2,  3,  -3,  1,  2,  2,  -3}

m=5

정수 m과  수열 nums 배열이 주어졌을때, 연속부분수열의 합이 m(5)가 되는 경우를 구하라는 문제가 주어진다.

 

결론부터 말하면 정답은 5이다. 아래는 연속부분수열의 합이 m(5) 가 되는 경우들이다.

[1,2,3,-3,1,2,2,-3]

[2,3]

  [2,3,-3,1,2]

[3,-3,1,2,2]

[3,-3,1,2,2]

[1,2,2]

 

어떻게 이 문제를 푸는지가 중요하다. 
사실 중첩 반복문으로 풀면 누구나 풀 수 있는 문제일 것이다. 하지만 보통 이런 문제는 nums의 길이가 100,000 이상으로 나와 효율성을 고려해야 한다.
나는 이 문제를 보자마자 투포인터 방식을 생각했지만 연속부분수열이기 때문에 정렬을 하지못해 규칙성이 없어 투포인터 방식으로는 풀 수 없다는 것을 깨달았다. 이 문제를 통해 해싱방식의 풀이를 학습할 수 있었다.
해싱방식으로 풀면 중첩반복문 없이 간결하게 풀 수 있다.

 

 풀이 

먼저 연속부분수열의 합을 저장할 변수 sum과 해싱하기 위해 필요한 HashMap인 map을 선언한다.  그리고 map에 0,1를 추가한다.

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

 

해싱방식으로 부분수열이 m(5)이 되는 상황을 설명한다.

nums = {1,  2,  3,  -3,  1,  2,  2,  -3}

***로직을 순서대로 설명하자면 

1. nums수열에서 첫번째 요소인 1을 sum에 누적한다. 

2. map에 sum(1)-m(5)가 키로 저장되어 있는지 찾는다. -4인 key가 없으므로 넘어감.

3. sum(1)값을 map에 키로 저장한다.value는 동일한 키가 등장할때마다 1씩 증가해야 한다. 키가 1인게 처음 저장되니

map은 { 0:1, 1:1 } 로 되어있다.

이를 반복하면

 

 

nums = {1,  2,  3,  -3,  1,  2,  2,  -3}

이때는 sum이 6이며

map에는 {0:1, 1:1, 3:1} 이 저장되어 있다.

이때 위 설명 2번의 sum-m이 map에 키로 저장되어 있는지 확인한다. sum(6)-m(5)= 1. map에 키가 1인 데이터가 있다.

이때 정답을 출력할 int answer=0; 변수에 1인 키의 value값을 누적한다.

answer+=map.get(sum-m);

 

sum-m 값이 map에 키로 포함되어 있냐는 조건의 의미는 연속된 부분수열 {1,2,3}에서 5를 빼면 즉 {2,3}을 빼도 {1}이 map에 키로 존재한다는게 이미 누적된 연속 부분수열이라는 뜻으니 {2,3}이 적합하게 m이 만들어지는 경우라고 볼 수 있다. map 선언 후 map.put(0,1); 값을 넣어준것은 

nums = {1,  2,  3,  -3,  1,  2,  2,  -3} 

이 경우 sum=5 이다 5-m(5)는 0이다.  이는  {1,2,3,-3,1,2,2,-3} 차체가 m이 되는 경우이다.

핵심코드는 다음과 같다.

HashMap<Integer,Integer>map = new HashMap<>();
int sum=0;
map.put(0,1);
for(int i=0;i<nums.length;i++){
    sum+=nums[i];
    if(map.containsKey(sum-m))answer+=map.get(sum-m);
    map.put(sum,map.getOrDefault(sum,0)+1);
}

 

 

 

 

출처 : 자바 코딩테스트 - it 대기업 유제[김태원]