[12월 2주차] 알고리즘 스터디

1. 수들의 합 4 - 골드 4

출처 - https://www.acmicpc.net/problem/2015

 

  Sol)  스터디원 코드 JW - 440 ms

<hide/>

public class Test3 {

    public static BufferedReader br = new BufferedReader(
        new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(
        new OutputStreamWriter(System.out));

    public static int N;
    public static int K;
    public static Map<Integer, Integer> nums = new HashMap<>();
    public static long result;
   
    public static void main(String[] args) throws IOException {
    
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K =  Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int sum = 0;
        nums.put(0, 1);

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            sum += num;	
            result += nums.getOrDefault(sum - K, 0);
            nums.put(sum, nums.getOrDefault(sum, 0) + 1);
        }

        bw.write(result + "");
        br.close();
        bw.close();

    }

}

 

• ex) 현재 합 (sum) = 10, target(K) = 3인 경우
  • keySet에 7 (= 10 - 3)이 존재한다면
  • {더해서 10이 되는 원소들} - {더해서 7이 되는 원소들} = {남은 원소들}
  • {남은 원소들} 의 합은 K가 될 것이다.
  • 따라서 result += map.get(sum - K)를 해준다.
• map의 초깃값으로 (0, 1)을 넣어준다. ????????? 
  • sum = 5, K = 5 인 경우
  • sum - K = 0
  • 따라서, 이 경우를 위해 map.put(0, 1)를 초깃값으로 넣어줘야한다. ??? 
  • (어느 부분합도 K가 아닌 경우와 같은) 예외 상황이 없기 때문에 1을 초깃값으로 넣어줘야 되는 건가?
• result를 int형으로 설정하는 경우 66%까지 가다가 오답이 난다.
• 로직은 모두 맞는데 result가 int의 범위를 넘어가는 경우가 있을 수 있어서 long으로 설정해야한다.
• N 20만 이하, K은 20억 이하라는 조건이 있다. 
• map의 keySet에 sum - K가 존재하는 경우,  result 에 map.get(sum - K) 를 해서 더해주는데 더하다가 INT 범위를 넘을 때 오류가 나는 걸로 보인다.
• 따라서 이 부분만 long으로 바꿔주면 된다.
• 문제 이해하고 정리하는데 3시간 넘게 걸렸다 .ㅎㅎㅎ ㅠ