기본 콘텐츠로 건너뛰기

코딩 테스트 - 연속 펄스 부분 수열의 합

package programmers;

import java.util.List;

class 연속_펄스_부분_수열의__Java_230827 {
/*
문제:
주어진 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다.
펄스 수열이란 [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가 매개변수로 주어질 때,
연속 펄스 부분 수열의 합 중 가장 큰 것을 반환하는 solution 함수를 완성하세요.
*/
public long solution(int[] sequence) {
long answer = Long.MIN_VALUE;

int n = sequence.length;

// 0 : [-1, 1, -1, 1, ...]
// 1 : [1, -1, 1, -1, ...]
List<long[]> dp = List.of(new long[n], new long[n]);
// 펄스 패턴에 따른 연속 부분 수열의 곱 결과를 저장할 dp 리스트

dp.get(0)[0] = 펄스패턴과_수열원소의_(0, 0, sequence);
dp.get(1)[0] = 펄스패턴과_수열원소의_(1, 0, sequence);
answer = Math.max(dp.get(0)[0], dp.get(1)[0]);

for(int i = 1; i < n; i++) {
for(int j = 0; j < 2; j++) {
//DP를 이용해서 최대 합 계산
long summary = 펄스패턴과_수열원소의_(j, i, sequence);
dp.get(j)[i] = Math.max(summary, dp.get(j)[i - 1] + summary);
}
// 현재 인덱스에서의 최대 합과 기존의 최대 합을 비교하여 더 큰 값 선택
answer = Math.max(answer, Math.max(dp.get(0)[i], dp.get(1)[i]));
}

return answer;
}

private long 펄스패턴과_수열원소의_(int k, int i, int[] sequence) {
long answer;
if(i % 2 == 0) { // 짝수 인덱스
answer = (k == 0) ? (sequence[i] * -1) : sequence[i];
} else { // 홀수 인덱스
answer = (k == 0) ? sequence[i] : (sequence[i] * -1);
}
return answer;
}
}
package programmers

class 연속_펄스_부분_수열의__Kotlin_230827 {
/*
문제:
주어진 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다.
펄스 수열이란 [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가 매개변수로 주어질 때,
연속 펄스 부분 수열의 합 중 가장 큰 것을 반환하는 solution 함수를 완성하세요.
*/
fun solution(sequence: IntArray): Long {
var answer = Long.MIN_VALUE

val n = sequence.size

// 0 : [-1, 1, -1, 1, ...]
// 1 : [1, -1, 1, -1, ...]
val dp = listOf(LongArray(n), LongArray(n))
// 펄스 패턴에 따른 연속 부분 수열의 곱 결과를 저장할 dp 리스트

dp[0][0] = 펄스패턴과_수열원소의_(0, 0, sequence)
dp[1][0] = 펄스패턴과_수열원소의_(1, 0, sequence)
answer = maxOf(dp[0][0], dp[1][0])

for (i in 1 until n) {
for (j in 0 until 2) {
// DP를 이용해서 최대 합 계산
val summary = 펄스패턴과_수열원소의_(j, i, sequence)
dp[j][i] = maxOf(summary, dp[j][i - 1] + summary)
}
// 현재 인덱스에서의 최대 합과 기존의 최대 합을 비교하여 더 큰 값 선택
answer = maxOf(answer, maxOf(dp[0][i], dp[1][i]))
}

return answer
}

private fun 펄스패턴과_수열원소의_(k: Int, i: Int, sequence: IntArray): Long {
val answer: Long
if (i % 2 == 0) { // 짝수 인덱스
answer = if (k == 0) sequence[i].toLong() * -1 else sequence[i].toLong()
} else { // 홀수 인덱스
answer = if (k == 0) sequence[i].toLong() else sequence[i].toLong() * -1
}
return answer
}
}

댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ *...

개발 공부 - PC 카카오톡 작업 표시줄 아이콘 이미지 변경 방법

PC 카카오톡 사용시 작업 표시줄에서 아이콘 이미지를 변경하는 방법이다. 1) 작업 표시줄 내 카카오톡 아이콘에서 마우스 오른쪽 버튼을 누른  뒤 속성에 들어간다. 2) 아이콘 변경에서  C:\Windows\system32\imageres.dll C:\Windows\system32\shell32.dll C:\Windows\system32\DDORes.dll C:\Windows\System32\moricons.dll (MS DOS Icons) 등을 누른 뒤 적당한 것을 선택하여 적용한다. * 사내 메신저 아이콘을 참고해도 된다. 참고 : 기본 아이콘 위치 https://blog.silnex.kr/windowstip-windows-%EA%B8%B0%EB%B3%B8-%EC%95%84%EC%9D%B4%EC%BD%98-%EC%9C%84%EC%B9%98/ 2022. 11. 29.  생각보다 유입이 많아서 놀랐습니다. PC 카톡 사용자 화이팅!

운동 정보 - 어메이즈핏 밴드 5 스마트밴드 나이키 런 클럽(NRC = Nike Run Club) 연동

 나이키 런 클럽 쓰려고 산 어메이즈핏 밴드5 인데 연동이 영 어려워서 찾아보고 써봤다. 1. Zepp 앱은 연동이 되어 있어야 한다. 2.  Zepp 앱 -> 프로필 -> 내 기기 -> Amazfit Band 5 3. 검색 가능 : 켜짐 활동 심박수 공유 : 켜짐 연결 제한 : 꺼짐 (기본) 백그라운드에서 실행 : 제외로 등록 4. NRC(나이키 런 클럽) 앱 -> 설정 -> 러닝 설정 -> 기기 5. 심박수 표시 -> 블루투스에서 AmazFit Band 5 누르고 NRC 즐기면 된다! * 안드로이드 이용자입니다.