Lv 2. 연속된 부분수열의 합

2024. 8. 4. 21:53·Algorithm & Data Structures/Programers

 

코드 흐름

  • 투포인터 알고리즘을 사용하였다.
  • left, right 를 지정하는 변수를 두고 right를 while 문을 통해서 계속 늘려가면서 sum 이 k를 넘어갈때까지 더한다.
  • 이후 left를 더하고 sum에서 left칸의 sequence 원소를 빼면서 sum과 k를 비교한다.
  • 문제조건에 맞게 부분수열의 길이가 짧다면 최신화한다.
class Solution {
    public int[] solution(int[] sequence, int k) {
        
        int N = sequence.length;
        int left=0, right = N-1;
        int sum = 0;
        for(int i = 0, j = 0 ; i < N ; i++){
            while(j < N && sum < k){
                sum+= sequence[j];
                j++;
            }
            if(sum == k){
                if((right-left)>(j-i))
                {
                    left = i;
                    right = j-1;
                }
            }
            sum -= sequence[i];
        }
        int[] answer = {left,right};
        return answer;
    }
}

'Algorithm & Data Structures > Programers' 카테고리의 다른 글

Lv 2. 시소 짝궁  (0) 2024.08.08
Lv 2. 마법의 엘리베이터  (1) 2024.08.06
Lv 2. 큰 수 만들기  (0) 2024.08.03
Lv 2. 두 큐 합 같게 만들기  (1) 2024.08.02
Lv 2. 삼각달팽이  (1) 2024.07.31
'Algorithm & Data Structures/Programers' 카테고리의 다른 글
  • Lv 2. 시소 짝궁
  • Lv 2. 마법의 엘리베이터
  • Lv 2. 큰 수 만들기
  • Lv 2. 두 큐 합 같게 만들기
Geisha
Geisha
개발 일기
  • Geisha
    Geisha
    Geisha
  • 전체
    오늘
    어제
    • 분류 전체보기 (326)
      • Algorithm & Data Structures (246)
        • BOJ (104)
        • SWEA (1)
        • Programers (137)
        • Data Structures (3)
      • DB (27)
        • SQL (21)
        • RDBMS (2)
      • Java (1)
        • Class (1)
      • Spring (5)
        • Spring MVC (1)
        • Annotations (1)
      • CS (36)
        • 운영체제 (13)
        • 네트워크 (5)
      • Tool (6)
        • Git (5)
        • AWS (1)
      • Project (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    다익스트라
    골드
    Union-Find
    스택
    algorithm
    경로압축
    전위순회
    PriorityQueue
    알고리즘
    SQL
    programmers
    binarySearch
    프로그래머스
    dp
    Stack
    백트래킹
    dfs
    후위순회
    투포인터
    구현
    Java
    이분탐색
    DynamicProgramming
    unionfind
    Dijkstra
    유니온파인드
    BFS
    백준
    동적계획법
    baekjoon
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
Geisha
Lv 2. 연속된 부분수열의 합
상단으로

티스토리툴바