프로그래머스의 Lv2. 연속된 부분 수열의 합는
23-04-06에 나온 문제로 알고리즘 중에
투포인터를 활용해서 풀 수 있는 문제 중 하나이다.
해당 문제의 풀이 공유 이전에 코드를 공유한다.
class Solution {
public int[] solution(int[] sequence, int k) {
//투포인터
int p1 = 0, p2 = 0;
int[] answer = {p1, p2};
int sum = sequence[p1];
if(sum == k) return answer;
while(p1 < sequence.length-1 && p2 < sequence.length-1){
while(p2 <= sequence.length-1 && sum < k)
sum+=sequence[++p2];
while(p1 <= sequence.length-1 && sum > k)
sum-=sequence[p1++];
while(sum == k){
if(answer[1] == 0)//최초 갱신
answer = new int[] {p1,p2};
else{//길이가 짧을 때만 갱신
if(answer[1]-answer[0] > p2 - p1)
answer = new int[] {p1, p2};
}
sum-=sequence[p1++];//길이 조정해서 while 탈출, 계속 탐색
}
if(answer[1] != 0 && answer[1]-answer[0] == 0) return answer;
//최적화//가장 짧은 순간
}
return answer;
}
}TMI
우선 나의 한계와 어려워 하는 부분에 대해 미리 밝힌다.
나는 투포인터 또는 이분 탐색에서 최상위 while문 즉 탈출 조건에서 아직 헤맨다.
문제를 접했을 때 해당 부분을 적절하게 작성하지 못해 시간을 소모하고,
indexError가 발생하고, 정확하게 이렇게 해야한다!
이렇게 이해가 여전히 부족하다. 더 많은 시간을 투자해야 할 것 같다.
알고리즘(투포인터)
투포인터 알고리즘은
말 그대로 두 개의 변수를 활용해 해당 문제를 적절하게 풀이 하는 경우를 말한다.
가장 대표적인 유형은 이번 '연속된 부분수열의 합'이라고 말하고 있듯,
배열의 부분합이 정말 정말 대표적인 문제들에 해당한다.
해당 알고리즘을 알고 있으면, 시간 초과가 발생하지 않지만 해당 알고리즘 개념을 이용하지 않은 이중 For문을 돌리면 O(N^2)으로 시간초과가 발생하는 유형의 문제다.
투포인터는 배열을 탐색하는 과정이 한 번만 이루어지는데 이 개념이
나는 처음에 이해가 안 됐다. while 문을 여러 개를 쓰는데 배열을 한 번만 탐색한다??
위의 내용 때문이었는데, 이게 우문이라는 걸 지금은 이해하고 있다.
while문을 여러 개를 쓰건, for문을 여러 개를 쓰건 사실, O(N^2)이 되느냐,
O(N)이 되느냐는 조건에 따라 달라진다는 점을 미리 밝힌다.
조건이 적절하게 주어진다면 for문을 써도 괜찮다.
하지만 해당하는 조건절의 추가에 대한 고민 요소가 그나마 적은 while문을
활용해 주로 투포인터와 같은 알고리즘이 구현된다는 점을 미리 밝힌다.
(위의 내용이 이해가 안 된다면 댓글로 질문을 주세요... 투포인터는 배열을 한 번만 탐색하게 조건들을 적절하게 주는 부분의 아이디어를 짠다! 이 부분이 저는 핵심이라고 생각합니다.)
시간초과에 관하여(제한사항을 통해)
문제 링크를 통해 확인했겠지만
제한사항
5 ≤ sequence의 길이 ≤ 1,000,000
1 ≤ sequence의 원소 ≤ 1,000
sequence는 비내림차순으로 정렬되어 있습니다.
5 ≤ k ≤ 1,000,000,000
k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.
위와 같은 제한 사항을 가진다.
배열의 길이만 해도 최대 100만번의 연산을 시도한다.
이런 걸 단순
for문으로(i = 0; 배열.length; i++) {
for문(j = 0; 배열.length; j++) {
}
}위와 같이 작성하면 시간 복잡도는
배열길이 * 배열길이이고 최악의 상황을 상정하는 빅오(O) 표기법으로 O(N^2)
으로 1,000,000,000,000 즉 10^12이 된다.
C언어를 기준으로 컴퓨터의 1초 연산을 1,000,000,000번(10억번)
10^9으로 상정하기 때문에
(출처:이코테(이것이 취업을 위한 코딩테스트다. 나동빈 저서. 49page 11번째 줄))
위와 같이 최악의 상황이 아니더라도 충분히
10.0초 이상(10^10이상)의 (프로그래머스 자바 시간 초과 기준)
연산 발생의 여지가 충분한 문제다.
그렇기 때문에 이중 for문은 위의 범위 때문에라도 머릿 속에서 지워야 한다.
사실, 위의 문제는 투포인터 말고 Map을 이용한 풀이도 가능한데,
(투포인터의 경우, Map을 활용하는 방법도 존재한다. 해당 경우가
시간 복잡도가 가장 적다.
위와 같은 풀이는 아직 내가 익숙하지 않아서... 추가되면
추가라고 게시글을 바꾸도록 하겠다...)
긴 주저리 끝에 투 포인터를 써야 하는 이유를 알았다.
어떻게 구현한 건지 상세하게 이야기 해 보자.
구현 상세(진짜 상세해서 엄청 김)
1. 투포인터를 위한 pointer 변수 선언 및 초기화
left/ right, start/end, p1/p2...etc
다양한 쌍의 명명법이 있다. 그리고 투포인터라는
개념이 나중에 좀 더 익숙해지면 포인터를 1개만 두는 게 아니라
3개, 4개를 두는 등의 변용이 가능하다.
그렇기 때문에 개인적으로는 p1/p2명명법을 주로 사용하는 편이고
이분탐색의 경우에는 left/right, start/end를 기분에 따라 쓰는 편.
변수를 제한조건에 따라 적절하게 Type을 선언해주면 된다.
- 1 ≤ sequence의 원소 ≤ 1,000
- 5 ≤ k ≤ 1,000,000,000
위와 같은 조건이므로, int면 충분하다.
k를 구하는 것인데 k의 범위가
(Integer.MAX_VALUE)2^32 -1 =2,147,483,647
보다 적으므로. int 여도 충분하다.
TMI
(Long.MAX_VALUE) 2^64 -1 = 9,223,372,036,854,775,807
10^18이상이면 BigInteger또는 String을 통해 풀기를 추천한다.
-1이 붙는 이유는 0부터 세기 때문.
그리고 변수 선언은 0으로 해두겠다.
배열의 탐색을 위해서 0번 인덱스에서 부터
끝까지 탐색을 위한 것이기 때문에, 둘 다 0, 0으로 시작
TMI
start, end를 두는 이유 중 하나로
배열의 탐색을 처음과 끝 부터 해야하는 경우도
투포인터 문제로 등장한다.
해당 경우 때문에 start/end,left/right와 같은 변수 명명법이 사용된다.
2. 부분합을 확인해 줄 변수 선언 및 초기화
나는 단순하게 int sum이라는 변수를 선언했으며
해당 값이 k인지를 판단해야한다.
우선 둘다 0,0이기 때문에 두 변수 중 하나로
배열의 첫값을 부분합으로 초기화한다.
만약, 이때 sum이 k 일 수도 있기 때문에
int[] answer 배열을 만들고 기본값으로 {0,0};을 둔다.
위 문제의 경우에는 부분합이 존재하지 않는 경우를 주지 않았는데,
만약 부분합이 존재하지 않는 경우가 주어진다면, 해당 문제에서
반환하기를 희망하는 값으로 변용해 줄 필요가 있다.
가령 {}이렇게 빈 배열로 만들어서 반환해 달라고 했는데
해당 부분을 miss하고 어디서 틀렸는지 모르는 경우가
나는 많았기에 Tip 아닌 Tip
위의 문제를 빈배열로 만들어야 한다면, 맨마지막 반환값 부분에서
나는 간단하게 삼항 연산자를 쓸 것 같다.
return sum != k && answer[0] == 0 && answer[1] ==0 ? new int[] {} : answer;위와 같은 형태가 될 것 같다.
뭐 그래서 위의 코드를 보면 자연스럽게 우선의 최적화로
sum의 k 여부를 확인해 주고 맞다면 바로 반환하게 값을 만들어 주었다.
(뭐 대부분 아니겠지만, 위의 최적화 형태가 추후에도 나오므로 미리 끄적)
이제부터 본격적으로 while문을 설계해 투포인터를 구현해
배열을 탐색한다.
코드 구조를 보면 while을 4개나 썼다.
while(p1 < sequence.length-1 && p2 < sequence.length-1){
while(p2 <= sequence.length-1 && sum < k)
sum+=sequence[++p2];
while(p1 <= sequence.length-1 && sum > k)
sum-=sequence[p1++];
while(sum == k){
if(answer[1] == 0)//최초 갱신
answer = new int[] {p1,p2};
else{//길이가 짧을 때만 갱신
if(answer[1]-answer[0] > p2 - p1)
answer = new int[] {p1, p2};
}
sum-=sequence[p1++];
//길이 조정해서 while 탈출, 계속 탐색
}
if(answer[1] != 0 && answer[1]-answer[0] == 0) return answer;
//최적화//가장 짧은 순간
}더 줄일 수 있을지도 모르겠지만
나는 우선 위와 같이 만들었다.
심지어
while문 위의 2개는 중괄호까지 생략해 버리고 있는데
해당 내용을 먼저 TMI로 정리하고 가자.
TMI 중괄호의 영역 표시.
이미 레벨2를 풀고 계신 분들이라면 충분히
기본 개념에 빠삭하겠지만
말 그대로 TMI. 그리고 저의 정리를 위한 뭐 그런 겁니다!
내가 본 자바 기본 서적은 윤성우의 열혈 자바라는 책으로
해당 서적의 내용을 기억하는 대로 작성한 것이다.(페이지 펴서 확인해 볼 수는 있는데 그러면 한참 찾을 거 같아서...틀린 부분 있으면 코멘트 해주시면 감사하겠습니다!)
기본적으로 C계열의 컴파일러 프로그래밍 언어에서 문장을 끝냈다는 표시는 ';' 세미콜론(한국어로 쌍반점이라고 한다네요. 써 본적 없음..출처는 위키백과)
으로 컴파일러는 '구분'을 한다.
따라서 ;이 나타나면 컴파일러는 해당 문장이 끝났다고 판단한다.
여기서 {}가 주어진다면 중괄호는 하나의 문단과 같은 역할을 하며 이러한 문단은 여러개의 문장을 담을 수 있다.
즉, while문 다음에 나타난 첫;(세미콜론)을 통해 중괄호의 시작이 없다면 while문은 종료가 된다.
앞서 말했듯 while(){처럼; ... ;} 중괄호로 시작하면
중괄호 전체를 처리하는 과정을 하나의 while의 단위로 본다.
정말 정말 개인적으로 {} 부분이 늘어져서 코드가 길어져 보이는 구분을 안 좋아해서...(파이썬이 이래서 편한 건가요?_들여쓰기 잘못하면 아작나긴 하는데 파이썬은...)
위와 같이 작성하는 경우가 요즘 따라 많아진 것 같다.
안 좋은 습관이면 고쳐야 하는데, Stream 같은 거 쓰고 하면서
마냥 안 좋게만 보이지도 않아서, 혹여 안 좋은 습관이면
코멘트 부탁드립니다...(근거나 사례로 설명해 주시면 더욱더 감사)
- TMI 끝
길고 긴 TMI를 지나...
다시 while문의 구조로 돌아와 보자.
우선 최상위를 이야기 하기 전에
내부 while문 3개를 이야기 해보자. 내부에 있는 구조를
이해하고 최상위 탈출조건을 이해하는 게 더 좋기 때문이다.
//내부 while문 3개
while(p2 <= sequence.length-1 && sum < k)
sum+=sequence[++p2];
while(p1 <= sequence.length-1 && sum > k)
sum-=sequence[p1++];
while(sum == k){
if(answer[1] == 0)
answer = new int[] {p1,p2};
else{
if(answer[1]-answer[0] > p2 - p1)
answer = new int[] {p1, p2};
}
sum-=sequence[p1++];
}
if(answer[1] != 0 && answer[1]-answer[0] == 0)
return answer;첫 번째 while문
나는 기본적으로
p2를 더해주는 쪽의 포인터로 움직여서 이동해
sum을 더해주고 sum이 더 작다면 p2를 움직여서, sum에 더해주는 방식이다
여기서 ++prefix를 사용해 값이 대입되기 전에 p2를 이동시켜주는 부분을 구현했다.
위와 같은 구현을 한 이유는 포인터가 둘 다 같은 시작점에서 시작하기 때문인데, 위와 같이 하지 않으면
0값이 중복으로 연산되기 때문에 위와 같이 구현했다.
물론 p2++; 하고 더해줄 수도 있다.
그러면 중괄호를 써야했기에...나의 코딩 스타일과
간단하게 쓴다는 목표를 위해!
++prefix 를 복습한다는 느낌으로 구현.
위의 탈출 조건을 두 가지로 작성했는데
강의에서도 봤지만
(필자는 제로베이스 백엔드스쿨 9기를 수강 중)
위와 같은 조건의 형태가 주로 쓰인다.
(강의가 문제와 적합하지 않지만 보통 2가지 들어가더라...)
간단하게 작지 않으면(크거나 같으면) 탈출하라를 기본 골자로 하고
p2의 값이 최대 인덱스를 넘지 못하게 설정.
두 번째 while문
두 번째는 위의 형태를 이해했다면 쉽게 이해할 수 있다.
값이 목표치 보다 크다면 부분 배열의 크기를 줄여주는 형태다.
이 경우에는 postfix++를 활용해서. 현재의 값이 빠져나가고
p1이 이동하는 형태로 구현 되었다.
이렇게 하면 자연스럽게 sum값의 줄어듬을 구현하고
p1이 갈 수 있는 한게치를
ArraysIndexOutOfBounds 예외를 피하기 위해
길이-1로 설정
역시 중괄호를 생략해 한 줄로 구현!
위와 같이 했으면 sum 보다 크면 빼줘야 하니까.
sum보다 큰 값이 유지가 안 되면(작거나 같아지면)
탈출하게 조건을 썼다.
위와 같은 조정이 이루어진 이후
while(sum == k)이 나온다.
세 번째 while문
해당 부분이 꽃이라 할 수 있겠다.
여기는 아직 중괄호를 삭제하는 법을 고민하지 못했다.
스트림을 써야하지 싶다.
첫번째 if의 경우, answer[1] == 0;으로 (p2)초기화 해준 것을 기억할 것이다.
이에 따라서 값이 바뀐 상태에서 초기화 해줄 최초의 기준을 주었다. 해당 상태라면 아래의 if문
if(answer[1]-answer[0] > p2 - p1)
answer = new int[] {p1, p2};에 에러가 발생할 수 있기 때문에 위와 같은 조건이 등장한다.
위와 같은 초기화 과정이 없으면 무조건 0-0이 우세하기 때문!
일단 한 번만 쓰고 말 조건이어서 간단하게 한줄 코딩
뒤이어서
else가 중요한 부분인데
해당 문제는 부분합이 여러개가 나올 수 있다. 특히
부분합이 가장 적은 값을 구해야 하는데
그래서 맨위에 최적화로 부분합이 해당 숫자 하나인 경우에는
바로 반환할 수 있는 조건식이 작은 최적화로 쓰인 것.
뒤를 더 볼 필요가 없기 때문
게다가 구간이 같다면 앞의 인덱스를 출력하라고 했기
때문에
위와 같이 크기가 작기만 하면 새로운 배열을 만들어
초기화 해주는 전략을 썼다.
만약, 이 문제가 아주 조금 더 복잡해 진다면,
인덱스를 뒤에 있는 값으로 하라고 하더라도
위의 if문을 활용하면 된다. 길이가 크거나 같다면
바꿔주면 되니까.
대신 이 경우에는
최적화로 넣어준 부분들을 빼줘야 할 것이다.
뭐 위와 같은 문제를 본 적은 없지만
세상은 넓고 생각의 틀을 조금 바꿔서
문제를 위한 문제인 별찍기 문제도 세상에는
존재하니까 얼마든지 나올 수 있다고 생각하고
추가로 생각해 봤다.
TMI로 시간을 질질 끄는 이유는 위의 내용이 거의 끝이기 때문!
마지막으로!!
해당 기본 while문이 동작할 수 있게, 그리고sum값을 깨주고
계속 탐색을 하기 위해
p1을 이동시켜 준다. 기본적으로 p1이 더 작은 경우를
보장하게 설계되었고,
만약 해당 상태에서 p1 = 배열 인덱스의 끝.
이런 상황이었더라도 상관은 없다.
이제 마지막으로 알아볼 최상위 while문의 종료조건이 있기 때문!
드디어 끝!? 최상위 while문
while(p1 < sequence.length-1 && p2 < sequence.length-1){
}하지만 아쉽게도 맨처음 밑밥을 깔았듯이
나는 위의 조건을 정확하게 이해하고 있지는 않다.
여러 조합을 통해 적절하게 찾아낸 것.
위의 문장은 p1과 p2가
둘 다 배열의 -2까지만을 허용하고 있다.
왜 마지막값까지를 허용 안하는 것인가?!
만약 마지막값을 허용하고, 해당 값들을 준다면
ArrayIndexOutOfBoundsException가 발생하는데
추측을 해 보면 첫번째 while에서
p2가 마지막 인덱스에 해당하는 상태로 sum보다
작은 값이 들어오고 이에 따라
인덱스 에러가 발생하는 것으로 보인다.
그럼 첫 번째 조건만 클리어 되면 되지 않을까?
라고 생각하고 여러가지 조합을 해 봤지만
적확하게 경우를 추리지는 못했다는 아쉬움과
공부해야 할 부분이 여전히 남아있다는 확실성을
기록으로 남겨두며 길고 긴 풀이를 끝마친다!
만약 이걸 다 읽어 주셨으면 정말 감사 :)
