[F-Lab 모각코 페이백 11일차] 프로그래머스 - 연속된 부분 수열의 합(Java), 투포인터 알고리즘
학습 목표
- 프로그래머스 코테 한문제 풀기
- 자바의 신-(23,24 Chapter)
- 팀코칭-문제5개
- 멘토링 떄의 퀴즈 정리
TIL
- 투포인터 알고리즘(Two Pointers Algorithm)
프로그래머스 - 연속된 부분 수열의 합 Lv2
실제로 문제를 풀면서 풀이하여 정답을 맞추려고 하였으나
도중 저의 한계를 느끼고 문제풀이와 해설을 멈춘 틀린 답(틀린 풀이법) 입니다.
하지만 저의 고민과 생각했던 것을 적었습니다.
저의 공부와 그 과정을 정리한 글이니 그냥 이 사람은 이렇게 접근하려고 했고 이렇게 해서 틀렸구나 등으로 보시면 됩니다.
문제 설명
비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.
- 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
- 부분 수열의 합은 k입니다.
- 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
- 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.
수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.
제한사항
- 5 ≤ sequence의 길이 ≤ 1,000,000
- 1 ≤ sequence의 원소 ≤ 1,000
- sequence는 비내림차순으로 정렬되어 있습니다.
- 5 ≤ k ≤ 1,000,000,000
- k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.
입출력 예
| sequence | k | result |
| [1, 2, 3, 4, 5] | 7 | [2, 3] |
| [1, 1, 1, 2, 3, 4, 5] | 5 | [6, 6] |
| [2, 2, 2, 2, 2] | 6 | [0, 2] |
입출력 예 설명
입출력 예 #1
[1, 2, 3, 4, 5]에서 합이 7인 연속된 부분 수열은 [3, 4]뿐이므로 해당 수열의 시작 인덱스인 2와 마지막 인덱스 3을 배열에 담아 [2, 3]을 반환합니다.
입출력 예 #2
[1, 1, 1, 2, 3, 4, 5]에서 합이 5인 연속된 부분 수열은 [1, 1, 1, 2], [2, 3], [5]가 있습니다. 이 중 [5]의 길이가 제일 짧으므로 해당 수열의 시작 인덱스와 마지막 인덱스를 담은 [6, 6]을 반환합니다.
입출력 예 #3
[2, 2, 2, 2, 2]에서 합이 6인 연속된 부분 수열은 [2, 2, 2]로 3가지 경우가 있는데, 길이가 짧은 수열이 여러 개인 경우 앞쪽에 나온 수열을 찾으므로 [0, 2]를 반환합니다.
문제 설명을 읽어보았다.
비내림차순? 흐음 오름차순 말하는 건가? 찾아보니 그렇다고 한다.
문제 설명을 한 5분 정도 읽고 아래 부분에 해당하는 제한사항, 입출력 예, 입출력 예 설명 등을 읽어도
오랜만에 코테문제를 접해서 그런지 눈에 잘 안들어오고 집중도 잘 되지 않았다.
계속 문제 포인트를 못잡다가
입출력 예를 보고
약간 감을 잡았다.
배열이 주어지고 어떤 값이 주어지면 그 조건에 맞는 값이나 인덱스 등을 도출해야 하는 것 같았다.
배열 sequence와 k는 주어지는 거니 리턴으로 보내야하는 조건이나 알고리즘을 짜기 위해
대충 구상하고 조건을 알아보기 시작하였다.
보니 인덱스들을 배열로 리턴하고 조건에 맞다면 하나의 인덱스나 여러개의 인덱스가 나올 수도 있는 것 같았다.
즉 1~다수의 연속된 인덱스 이기만 하면 되고
좀 더 상세한 조건으로는
1. 구한 인덱스 배열 중 가장 짧은 배열
2. 그중에서 같은 길이의 배열이 있다면 가장 앞의 배열
그 조건이 단문의 조건으로 여러개의 문장으로 풀면
- 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
- 부분 수열의 합은 k입니다.
- 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
- 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.
다시 이 문장들(조건이 된다)
이것만 보면 이해가 안되니 예시나 입출력 예시가 있는 것 같다.
예전에 코테 공부했을 때 보았던 것인데 제한사항에
숫자 값의 범위를 보고
Int를 쓸지 Long을 쓸지 등을 정하면 된다고 들었던 것 같다.
실제로 로직은 정확한데 자꾸 에러가 나면 숫자 범위를 확인해보면
이 조건을 그냥 넘겨서 인 경우가 제법 있었다.
다행히 비내림차순으로 되어 있어서 딱히 문제가 없으면 다시 정렬할 필요는 없을 것 같았다.
구현할 방법을 구상 중이다.
내 생각에는 배열 값들을 k값과 각각 비교해서 인덱스 범위는 list[index] <= K조건 까지만 검색해보면 될 것같다.
그 이상의 인덱스 범위로 올라가면 1개의 배열 값만 하더라도 K 보다 커져서 조건에 맞지 않는다.
문제는 1개의 값이나 다수의 값의 합을 합해서 k값이 나와야하고
만약 여러개라면 가장 짧고 여러개면 가장 index가 작은 배열이어야 한다.
그래서 나는 생각한 것이
1개의 값이 k를 충족하는 것이 가장 짧으므로 가장 먼저 찾아보고
그다음 2개의 연속된 값이 k를 충족하는 것을 찾고
그 다음 3개의 연속된 값이 k를 충족하는 것을 찾는 식으로 구상했다.
위의 조건과 다시 맞춰보니 내 생각으로는 조건에 맞았다.
최소 1개의 이상의 값이 조건에 충족한다는 k으로 주어진다고 했으니
맞는 것 같다.
이걸 코드로 구현해야하는데
이중 for문을 생각했다.
1개의 값을 찾고 아니면
연속 된 index의 2개의 값을 더한 다음 k 값과 비교해보고
가장 빨리 나온 index로 배열로 값을 정리해주고 리턴한다.
없으면 그 다음 갯수의 값을 더한 다음 k값과 비교하고
마찬가지로 가장 빨리 나온 index로 값을 정리하고 배열을 만들어서 리턴한다.
....
배열의 길이 만큼의 연속된 값을 더한 다음 k값과 비교하고
배열을 만들어서 마찬가지로 답으로 제출한다.
1개의 값을 찾는건
인덱스 0부터 배열 길이 만큼 for문으로 만들어서 k값과 비교해서 같으면
바로 값을 해당 인덱스로 배열로 만들어서 제출
2개부턴 좀 어려워 보이는데
for문을 쓰고 인덱스가 i와 i+1 인 배열을 더한 다음 k값과 같은 지 비교
같으면 해당 i와 i+1 값으로 배열로 출력
아니면 i를 1 증가시키고 다시 k값과 비교
같으면 출력
아니면 다시 1증가
i 의 값이 배열의 길이에서 -1 한 값보다 작은 조건까지만 반복
ex)
배열 길이 5이라고 하면
i < list.length - 1 이러면 간단하다.
보통의 경우 i < list.length 하면 맞는데
i+1인 인덱스도 있어서 배열 범위를 벗어나지 않기 위해서 -1을 추가하였다.
3개는
for문을 쓰고 인덱스가 i와 i+2 인 배열들 더한 다음 k값과 같은 지 비교
2개는 for문을 쓰고 배열 2개정도는 하드코딩으로 하면 되었지만
3개부턴는 앞으로 계속 반복이기 떄문에
간단하게 하기 위해서 고민을 하였다.
3개는 실제로는
i + (i+1) + (i+2) 이다.
위 2개의 경우에서 (i+2)인 경우가 추가된 경우지만
그냥 위에서 i+1을 i+2으로 바꾸면 사이의
i+1인 인덱스의 배열 값이 더해지지 않는다.
그래서 사이 값을 추가하거나
처음 부터 i + (i+1) + (i+2) 을 다 더하는 방법을 찾아야한다.
음 이런건 내가 배운 것 중엔 없었다.
이중 i의 갯수가 1부터 배열 갯수만큼 늘어나니
이걸 코드로 적용시키면
for(int i = 0; i < list.length ;i++ ){
int sum = list[i];
int j = 2;
for( int g = i+1 ; g < i+j; g++ ){
sum += list[g];
};
j++;
}으로 짜보았다.
약간 설명을 해보자면
2개,3개 .... list.length 개수만큼 짜보았다.
완벽하지는 않겟지만
어느 정도는 맞는 코드 갔다.
1차 for문에서
인덱스 0부터 list.length까지 돌고
2차 for문에서 j의 값에 따라 j값 만큼
배열의 값이 더해지는 횟수가 정해진다.
예를 들면
j가 2면
2차 for문이 2번 돌고
j가 3이면
2차 for문이 3번 돈다.
그러면
내가 처음 구상했던
i + (i+1)인 경우와 i + (i+1) + (i+2)인 경우도 구현 가능하고
배열 길이 만큼도 가능하다.
배열 길이만큼의 조건은 빼먹어서
다시 추가 수정해서 짜보면
for(int i = 0; i < list.length ;i++ ){
int sum = list[i];
int j = 2;
for( int g = i+1 ; (i+j < list.length && g < i+j); g++ ){
sum += list[g];
};
j++;
}2차 for문에서
g < i+j코드 부분에서
i+j < list.length 을 추가하고 and 조건으로 하고 () 으로 묶어서 하나의 조건으로 만들었다.
(i+j < list.length && g < i+j)
조건이 2개나 마찮가지라 약간 성능엔 안좋겟지만 이 문제에서는 괜찮을 것 같다.
1개 일때와 그 이상의 갯수의 조건의 코드에 k값과 같은지 조건을 덧붙여서 작성하면
for(int i = 0 ; i < list.length ; i++){
int index1 = list[i];
if( index1 == k){
int[] answer = {index1,index1};
}
}
for(int i = 0; i < list.length ;i++ ){
int sum = list[i];
int j = 2;
for( int g = i+1 ; (i+j < list.length && g < i+j); g++ ){
sum += list[g];
};
if( sum == k){
int[] answer = {i,i+j};
return answer;
}
j++;
}일단 int로 선언했는데
숫자 값이 제법 커서 long으로 바꿔야 할 것 같다.
인트 값 범위는 양수는 2,147,483,647 이다.
제한 조건:
- 5 ≤ sequence의 길이 ≤ 1,000,000
- 1 ≤ sequence의 원소 ≤ 1,000
- sequence는 비내림차순으로 정렬되어 있습니다.
- 5 ≤ k ≤ 1,000,000,000
- k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.
- k값은 더한 값의 최대값이므로 배열의 값들을 더하더라도
- int 범위 안 일 것이라고 예상한다.
혹시나 계산하면 1000000 * 1000 = 1,000,000,000으로 2,147,483,647 값보다 적으므로
배열의 모든 값을 다 더하더라도 int 타입 내에서 저장과 값 계산 모두 가능하다.
흐음 이 코드로 제출 해보겠다.
class Solution {
public int[] solution(int[] sequence, int k) {
int[] answer = new int[2];
for(int i = 0 ; i < sequence.length ; i++){
int index1 = sequence[i];
if( index1 == k){
answer[0] = i;
answer[1] = i;
return answer;
}
}
for(int i = 0;i < sequence.length ;i++ ){
int sum = sequence[i];
int j = 2;
int lastindex = 0;
for( int g = i+1 ; (i+j < sequence.length && g <= i+j); g++ ){
sum += sequence[g];
if( sum == k){
answer[0] = i;
answer[1] = g;
return answer;
};
};
j++;
}
return answer;
}
}몇몇 에러가 발생했고 이에 대처해서 수정한 코드다.
코드 실행한 건 3문제 3문제 맞췄는데
제출 후 채점해보니
1/4~1/3 가량만 맞았다.
먼가 대강은 맞는데 내가 모르는 부분에서
먼가 맞지 않는 부분이 있는 것 같다,
시간이 2시간 정도 지나서 다른 분들 질문답변을 참고 해 보겠다.
오기가 생겨서 한 3시간 더 풀었는데
이거 안 풀려서 너무 화가 나는데
이정도 해서 안풀리면 대게의 경우 먼가 모르는 포인트나 해결법이여서 못 푸는 경험이 종종 있었다.
다른 분들 해결법 몇개 찾아봤는데
투포인트??
이건 머지??
투포인터 알고리즘 알고리즘으로 풀면 풀린다는데
어떤 분 설명에 의하면 100만 개의 값이여서
이중 for문으로 풀면 시간초과로 풀 수 없다고 한다.
헐.... 내가 한 방법은 무조건 통과할 수 없는 방법이였다...
시간 조건은 나는 못봤었는데...
또 다른 분들 Java 풀이법은 다른 것은 안보였다.
파이썬 코드는 잘은 몰라도 제법 간단해보였는데....
뭐지.....
투포인터 알고리즘을 알고 다시 도전하든가 하야겠다.
너무 애써서 다시 당장 풀 힘이 안난다.
투포인터 알고리즘만 조금만 검색해보고 다시 도전하든가 해야겠다.
이게 lv.2 라니... 투포인터를 모르면 풀 수 없는 문제인가...
진짜 너무 어려워서 눈물 날뻔 했다.
솔직히 이건 나에게 너무 매운 문제였다.
투포인터 알고리즘
투 포인터 알고리즘은 주로 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 알고리즘입니다. 이 알고리즘은 특히 정렬된 배열이나 리스트에서 두 숫자의 합이 특정 값이 되는 쌍을 찾거나, 배열의 특정 부분합을 계산할 때 유용합니다.
투 포인터 알고리즘의 기본 아이디어는 다음과 같습니다:
- 포인터 두 개를 배열의 시작점에 위치시킵니다.
- 이 두 포인터를 서로 다른 방향으로 이동시키며 (예: 하나는 앞으로, 다른 하나는 뒤로), 또는 한 포인터는 고정시키고 다른 포인터만 이동시키며, 원하는 결과를 찾습니다.
- 필요에 따라 이 두 포인터 사이의 값을 계산하거나, 두 포인터가 가리키는 값을 비교합니다.
예를 들어, 주어진 배열에서 두 수의 합이 특정 값인 경우를 찾는다고 가정해봅시다. 우선 배열이 오름차순으로 정렬되어 있다고 가정하겠습니다:
- 포인터 A를 배열의 시작점에, 포인터 B를 배열의 끝점에 위치시킵니다.
- A와 B가 가리키는 원소의 합이 원하는 값보다 크다면, B를 왼쪽으로 한 칸 이동시킵니다. 이는 배열이 오름차순으로 정렬되어 있기 때문에 가능합니다.
- A와 B가 가리키는 원소의 합이 원하는 값보다 작다면, A를 오른쪽으로 한 칸 이동시킵니다.
- A와 B가 가리키는 원소의 합이 원하는 값과 같다면, 이 두 원소가 원하는 결과입니다.
- A와 B가 같은 위치에 도달할 때까지 이 과정을 반복합니다.
이러한 투 포인터 알고리즘은 시간 복잡도를 크게 줄일 수 있어, 효율적인 문제 해결 방법으로 자주 사용됩니다.
투포인터 알고리즘도 종류가 몇가지 되었고
방법도 그에 따라 약간식 달랐다.
이것이 좀 특이 하다고 생각했는데
의외로 증명법을 설명하신 분이 계서서 이 증명이 맞다면
이 방법이 유효한 조건(쓸 수 있는 조건)에서
이 알고리즘이 정확히 동작하게 코딩한다면
놓치는 답은 없다고 한다.
간단하게 내가 알게 된 투포인트 알고리즘은
배열에서 두개의 포인터(C++에서트 포인터가 아닌 배열의 어떤 값을 가리키는 포인터라고 생각하자)
2개의 포인터 모두 배열 밖에서 대기하는 상태로 시작하고
1.먼저 어떤 포인터 A를 먼저 출발 시킨다.
(투포인터 알고리즘은 대개 배열과 배열값들의 합을 구할 때 쓰이는 것으로 보이므로 -나의 예상)
2.포인터 A가 가리키는 Index와 Index0간의 사이의 배열들의 값들의 합이 우리가 원하는 합보다 같거나 클때까지
포인터 A가 가리키는 Index를 한개씩 늘리면서 배열들의 값들의 합을 체크한다.(합이 같다면 하나의 정답을 찾은 것이다)
3.이상태에서 다른 포인터인 포인터 B의 Index를 하나씩 늘린다(0에서 포인터 A가 가리키는 Index까지)
약간 조심해야하는게 2에서는 포인터 A만 있었기 때문에 포인터 B가 가리키는 index까지 배열 값들을 다 더하면 되지만
여기서는 포인터가 A와 B가 있기 때문에 각 지점을 포함하여 사이의 index의 값들도 포함해야한다.
4포인터 B가 포인터 A의 인덱스 까지 왔으면 다시 포인터 A의 index를 합이 원하는 합보다 다시 같거나 커질때까지 한칸 씩 이동한다.
구한 합이 원하는 값보다 다시 같거나 더 커지면 포인터 B를 한칸씩 당기면서 합을 체크한다. 이과정에서 합이 같은 것을 count(check)한다
계속 이런식으로 반복 진행하면서 답을 찾고 두개의 포인터가 모두 배열 끝까지 도달하면 이 알고리즘은 종료해도 된다.
이 알고리즘의 장점은 O(N) 시간 복잡도로 문제를 해결할 수 있다는 점에 있다고 한다.
그리고 이 투포인터를 적용/사용 하려면 정렬을 되어 있거나 정렬을 해야한다고 한다.
정렬을 하면 이것도 시스템이 처리해야하는 작업이기에 내 생각으론 투포인터 알고리즘의 매력이 좀 떨어지는 것 같다.