프로그래머스 3단계 : 연속 펄스 부분 수열의 합 (Java 자바)

2023. 9. 7. 02:01·💻 코딩테스트/programmers
728x90

문제 설명
어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

 


제한 사항

  • 1 ≤ sequence의 길이 ≤ 500,000
  • -100,000 ≤ sequence의 원소 ≤ 100,000
  • sequence의 원소는 정수입니다.

 

입출력 예

 

풀이

주어진 정수 수열에서 연속된 부분 수열을 선택하고, 해당 부분 수열과 같은 길이의 펄스 수열을 원소끼리 곱하여 얻을 수 있는 연속 펄스 부분 수열 중에서 가장 큰 합을 구하는 문제입니다.

동적 프로그래밍(Dynamic Programming)을 사용하여 문제를 해결합니다. 주요 아이디어는 두 가지 펄스 수열을 따로 계산하고, 그 중에서 가장 큰 값을 선택하는 것입니다.

 

dp1과 dp2 배열: 이 두 배열은 각각 펄스 수열을 1로 시작하는 경우와 -1로 시작하는 경우의 최대 연속 부분 수열 합을 저장합니다.

배열 초기화: dp1[0]과 dp2[0]는 첫 번째 원소로 초기화됩니다. 이 값은 주어진 수열의 첫 번째 원소와 동일합니다.

반복문: 주어진 수열을 순회하면서 dp1과 dp2 배열을 업데이트합니다. 펄스 수열 패턴에 따라서 두 가지 경우를 나누어 계산합니다.

펄스 수열 패턴에 따른 값 업데이트:

홀수 인덱스(i % 2 == 1)일 때: 펄스 수열을 -1로 시작하는 경우. 이 때, 현재 수와 이전까지의 합(dp1[i - 1])을 더해주거나 현재 수를 선택하여 최댓값을 계산합니다.


짝수 인덱스(i % 2 == 0)일 때: 펄스 수열을 1로 시작하는 경우. 이 때, 현재 수와 이전까지의 합(dp2[i - 1])을 더해주거나 현재 수를 선택하여 최댓값을 계산합니다.


배열 정렬: 두 배열을 정렬하여 가장 큰 값을 찾기 위해 마지막 인덱스(size)의 값을 선택합니다.

최종 답 반환: dp1과 dp2 중에서 가장 큰 값을 선택하여 answer에 저장하고 반환합니다.

 

import java.util.*;

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;

        // 두 가지 펄스 수열을 따로 계산하기 위한 배열 선언
        long[] dp1 = new long[sequence.length]; // 1로 시작하는 펄스 수열
        long[] dp2 = new long[sequence.length]; // -1로 시작하는 펄스 수열

        // 초기 값 설정: 주어진 수열의 첫 번째 원소로 초기화
        dp1[0] = sequence[0];
        dp2[0] = sequence[0] * -1;

        // 주어진 수열을 순회하면서 펄스 수열의 합을 계산
        for (int i = 1; i < sequence.length; i++) {
            long num = sequence[i]; // 현재 수열의 원소

            if (i % 2 == 1) {
                // 홀수 인덱스일 때, 펄스 수열은 -1로 시작
                // 이전까지의 합과 현재 수를 비교하여 더 큰 값을 선택
                dp1[i] = Math.max(dp1[i - 1] + num * -1, num * -1);
                dp2[i] = Math.max(dp2[i - 1] + num, num);
            } else {
                // 짝수 인덱스일 때, 펄스 수열은 1로 시작
                // 이전까지의 합과 현재 수를 비교하여 더 큰 값을 선택
                dp1[i] = Math.max(dp1[i - 1] + num, num);
                dp2[i] = Math.max(dp2[i - 1] + num * -1, num * -1);
            }
        }

        int size = sequence.length - 1;

        // 계산된 값들을 정렬하여 가장 큰 값 선택
        Arrays.sort(dp1);
        Arrays.sort(dp2);

        // dp1과 dp2 중에서 가장 큰 값 선택
        answer = Math.max(dp1[size], dp2[size]);

        // 결과 반환
        return answer;
    }
}
728x90
저작자표시 비영리 변경금지 (새창열림)

'💻 코딩테스트 > programmers' 카테고리의 다른 글

프로그래머스 3단계 : 디스크 컨트롤러 (Java 자바)  (0) 2023.09.12
프로그래머스 3단계 : 부대복귀 (Java 자바)  (0) 2023.09.07
프로그래머스 3단계 : 가장 긴 팰린드롬 (Java 자바)  (0) 2023.09.07
프로그래머스 3단계 : 입국심사 (Java 자바)  (0) 2023.09.06
프로그래머스 3단계 : 섬 연결하기 (Java 자바)  (0) 2023.09.06
'💻 코딩테스트/programmers' 카테고리의 다른 글
  • 프로그래머스 3단계 : 디스크 컨트롤러 (Java 자바)
  • 프로그래머스 3단계 : 부대복귀 (Java 자바)
  • 프로그래머스 3단계 : 가장 긴 팰린드롬 (Java 자바)
  • 프로그래머스 3단계 : 입국심사 (Java 자바)
gxxg
gxxg
함께 일하고 싶은 개발자를 꿈꾸는 예비개발자의 공부 기록
  • gxxg
    공공
    gxxg
  • 전체
    오늘
    어제
    • 분류 전체보기 (138)
      • ☁️ 구름 x 카카오 Deep Dive 풀스택 (7)
        • html, css (1)
        • Java (3)
        • 스프링 MVC (0)
      • 💻 코딩테스트 (89)
        • 백준 (2)
        • programmers (87)
      • SQLD (1)
      • Language (3)
        • Java (2)
        • JavaScript (1)
      • Style Sheet (0)
        • CSS (0)
        • SCSS & SASS (0)
      • DBMS (2)
        • Oracle (2)
        • MySQL (0)
        • postgresql (0)
        • 데이터베이스 기초 이론 (0)
      • React (0)
      • SpringBoot (0)
      • JSP (2)
      • 알고리즘 (0)
      • 2023-02 몰입형 SW 정규 교육 (24)
        • 9월 프로젝트 (8)
      • 벽돌깨기 (4)
      • Etc (4)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    프로그래머스
    구현체
    2단계
    programmers
    JSP
    0단계
    CSS
    자바스크립트
    프로젝트 구조
    코테
    오블완
    Lv0
    회원 관리 시스템
    자바
    LV3
    spring
    HTML
    java
    이클립스
    springboot
    junit 테스트
    티스토리챌린지
    javascript
    eclipse
    톰캣
    Lv2
    DFS
    POST
    3단계
    코딩테스트
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
gxxg
프로그래머스 3단계 : 연속 펄스 부분 수열의 합 (Java 자바)
상단으로

티스토리툴바