이 영역을 누르면 첫 페이지로 이동
시간의화살 블로그의 첫 페이지로 이동

시간의화살

페이지 맨 위로 올라가기

시간의화살

행복하세요

[백준] 2015 수들의 합 4 - Java

  • 2022.07.28 15:53
  • Algorithm/Baekjoon

 

 

 

이중 for문을 돌면 당연히 시간 초과가 난다 -_-

 

먼저 입력받은 수들에 대해 누적 합 배열을 만들고 시작한다.

해시 맵은 누적 합 배열을 돌면서 해당 값이 나온 횟수를 저장하고, 현재 값 - 목표 값을 확인해 답을 갱신할 때 사용한다.

 

일단 누적 합 배열을 만들어놓으면 sum_arr[6] - sum_arr[3] == arr[4] + arr[5] + arr[6] 이렇게 사용할 수 있으니..

 

누적 합 배열을 돌면서 배열의 값이 찾으려는 값과 같으면 ans 1 증가.

나머지는 위에서 설명한 대로.

 

 

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        
        StringBuilder sb = new StringBuilder();      
        
        StringTokenizer st = new StringTokenizer(br.readLine()) ;

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[N+1];

        st = new StringTokenizer(br.readLine());

        for(int i=1; i<N+1; i++){
            arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
        }

        HashMap<Integer, Integer> hm = new HashMap<>();

        long result = 0;
        long cnt = 0;

        for(int i=1; i<N+1; i++){
            if(arr[i] == K){
                result++;                
            }

            if(hm.containsKey(arr[i] - K)){
                cnt = hm.get(arr[i] - K);
            }else{
                cnt = 0;
            }
            
            result += cnt;
            
            if(hm.containsKey(arr[i])){
                hm.put(arr[i], hm.get(arr[i]) + 1);
            }else{
                hm.put(arr[i], 1);
            }
        }

        System.out.println(result);

        
    }
}

 

 

 

 

 

반응형

'Algorithm > Baekjoon' 카테고리의 다른 글

[백준] 2468 안전 영역 - Java  (0) 2022.07.28
[백준] 25332 수들의 합 8 - Java  (0) 2022.07.28
[백준] 25395 커넥티드 카 실험 - Java  (0) 2022.07.28
[백준] 1766 문제집 - Java  (0) 2022.07.28
[백준] 9251 LCS - Java  (0) 2022.07.27

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [백준] 2468 안전 영역 - Java

    [백준] 2468 안전 영역 - Java

    2022.07.28
  • [백준] 25332 수들의 합 8 - Java

    [백준] 25332 수들의 합 8 - Java

    2022.07.28
  • [백준] 25395 커넥티드 카 실험 - Java

    [백준] 25395 커넥티드 카 실험 - Java

    2022.07.28
  • [백준] 1766 문제집 - Java

    [백준] 1766 문제집 - Java

    2022.07.28
다른 글 더 둘러보기

정보

시간의화살 블로그의 첫 페이지로 이동

시간의화살

  • 시간의화살의 첫 페이지로 이동

검색

방문자

  • 전체 방문자
  • 오늘
  • 어제

카테고리

  • 분류 전체보기 (607)
    • Algorithm (205)
      • Data Structure (5)
      • Theory && Tip (33)
      • Baekjoon (166)
      • ALGOSPOT (1)
    • Spring (123)
      • Spring (28)
      • Spring Web MVC (20)
      • Spring Database (14)
      • Spring Boot (6)
      • Spring 3.1 (11)
      • Spring Batch (6)
      • Spring Security (16)
      • JPA (12)
      • Spring Data JPA (5)
      • QueryDSL (4)
      • eGovFramework (1)
    • Programming Language (74)
      • Java (19)
      • JavaScript (15)
      • C (25)
      • C++ (12)
      • Python (1)
      • PHP (2)
    • Computer Science (69)
      • Operating System (18)
      • Computer Network (17)
      • System Programming (22)
      • Universial Programming Lang.. (8)
      • Computer Architecture (4)
    • Database (21)
      • Database (7)
      • MySQL (3)
      • Oracle (3)
      • Redis (5)
      • Elasticsearch (3)
    • DevOps (20)
      • Docker && Kubernetes (8)
      • Jenkins (4)
      • Github Actions (0)
      • Amazon Web Service (8)
    • Machine Learning (28)
      • AI Introduction (28)
    • Mobile (28)
      • Android (21)
      • Flutter (7)
    • Solutions (14)
    • Life Logs (0)
    • 낙서장 (25)

최근 글

나의 외부 링크

메뉴

  • 홈

정보

13months의 시간의화살

시간의화살

13months

블로그 구독하기

  • 구독하기
  • RSS 피드

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © 13months.

티스토리툴바