developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 시계열분석
  • 통계분석
  • 운영체제인터럽트
  • 카카오코테java풀이
  • 삼성코테기출자바풀이
  • BOJ파이썬풀이
  • 삼성코테파이썬풀이
  • 삼성코테파이썬
  • 삼성코테자바꿀팁
  • SW역량테스트파이썬풀이
  • 삼성코테자바풀이
  • 시계열
  • SW역량테스트파이썬
  • MA모형
  • ARIMA모형
  • 카카오코테
  • 코테파이썬
  • 백준파이썬풀이
  • Arima
  • 삼성코테구현풀이
  • c++ 빌더 패턴
  • 삼성코테파이썬준비
  • 데이터분석
  • 삼성코테자바준비
  • 통계학
  • 삼성코테기출
  • 삼성코테구현문제추천
  • AR모형
  • c++디자인패턴
  • 삼성코테준비

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 수들의 합4 2015번 (JAVA)

2022. 12. 7. 20:42

❓ 문제 - 백준 수들의 합4 2015번 - JAVA 풀이법

출처

(https://www.acmicpc.net/problem/2015)

 

2015번: 수들의 합 4

첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로

www.acmicpc.net

 

 

 

📝 문제해결법

1. 문제

  • A[1], A[2], A[3], A[4]. ... A[N]의 N개의 정수가 있을 때 i~j 구간의 부분합이 K인것이 몇 개인지 구하시오.

 

2. 해결 방법

  • 일단 누적합 + 각 구간 합의 숫자를 카운팅한 HashMap 이용으로 문제를 해결해야한다.
  • 만약 다음과 같은 경우로 답을 구한다면 시간 복잡도 O(N^2)로 시간초과가 발생한다.
4 0
2 -2 2 -2

========
누적합(0~4)

0 2 0 2 -2

=======
누적합에서 K(0)과 같아지는 경우는 우선 1개(1~3 누적)이다.

그리고 예를 들어 누적 1~4 구간에서 부분 합이 다시 K(0)과 같아지는 경우를 구하려면
구간 1~4, 1~3, 1~2, 2~4, 2~3, 3~4 를 다 살펴야 하며 이것은 시간복잡도 O(N(N+1)/2) 즉 O(N^2)을 야기한다. 
  • 위에 지금까지 누적합 구간안에 부분 합을 다시 살피려면,  현재까지 구간합 - (현재까지 구간 합 사이에 부분합) = K인 경우를 살피면 된다.
  • 따라서 구간 합에 대한 카운팅 정보를 hashMap에 넣어서 관리한다. 현재까지 구간합 - k의 숫자를 key로 hashMap에서 value를 찾아 answer에 더해준다.

 

3. 느낀점

  • 누적합이라는 아이디어로 문제를 바라봤는데.. 수학적인 공식에서 오는 풀이가 큰 문제인것 같다...

 

💻 소스코드 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main_2015 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] sum = new int[n+1];
        HashMap<Integer, Integer> hash = new HashMap<>();
        st = new StringTokenizer(br.readLine(), " ");
        long answer = 0;
        for(int i=1;i<n+1;i++){
            int num = Integer.parseInt(st.nextToken());
            sum[i] = num + sum[i-1];
            if(sum[i] == m) answer++;
            answer += hash.getOrDefault(sum[i]-m, 0);
            hash.put(sum[i], hash.getOrDefault(sum[i], 0)+1);
        }

        System.out.println(answer);

    }
}

 

 

 

 

 

 

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 단어 수학 1339번 (JAVA)  (0) 2023.01.12
BOJ - 거짓말 1043번 (JAVA)  (0) 2022.12.06
2022 KAKAO TECH INTERNSHIP - 등산코스 정하기 (JAVA)  (0) 2022.12.01
프로그래머스 코딩테스트 연습 - 여행경로 (JAVA)  (0) 2022.11.29
프로그래머스 코딩테스트 연습 - 카펫 (JAVA)  (0) 2022.11.22
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 단어 수학 1339번 (JAVA)
    • BOJ - 거짓말 1043번 (JAVA)
    • 2022 KAKAO TECH INTERNSHIP - 등산코스 정하기 (JAVA)
    • 프로그래머스 코딩테스트 연습 - 여행경로 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바