반응형
1. 문제
https://school.programmers.co.kr/learn/courses/30/lessons/178870#qna
2. 코드
처음 푼 코드) 타임아웃. 이번에는 해결해보려고 별 짓을 다했다 ㅋㅋㅋ 나름..내선에서..
function solution(sequence, k) {
let candidate = [];
let min = 999996;
let sum = 0;
for(let i=sequence.length-1;i>=0;i--){
sum += sequence[i];
if(sum === k) {
candidate.push([i,i]);
min = 0;
}else{
for(let j=i-1;j>=0;j--){
sum += sequence[j];
if(sum === k){
candidate.push([j,i]);
if(i-j < min) min = i-j;
break;
}
}
}
sum = 0;
}
for(let i=candidate.length-1;i>=0;i--){
if(candidate[i][1] - candidate[i][0] === min)
return candidate[i];
}
}
정답)
이 방식은 포인터(이것도 슬라이딩 윈도우라고 하나..?) + 1중 for문을 사용하는 방식이다. 2중 for문이 아니라 그런가.. 시간이 무지하게 줄었다.
function solution(sequence, k) {
let answer = []; // 정답이 될 수 있는 후보를 담을 배열
let sum = 0;
let head = 0; // 포인터
let min = sequence.length;
let result = []; // 답
for(let i = 0; i<sequence.length;i++){
sum += sequence[i];
if(sum > k){
// 작아질 때까지 앞에 값을 빼줌
while(sum > k){
sum -= sequence[head++];
}
}
if(sum===k){ // k와 같다면 후보에 추가
answer.push([head,i]);
}
}
answer.forEach((el)=>{
if(min > el[1] - el[0]){
min = el[1] - el[0];
result = [el[0],el[1]];
}
})
return result;
}
이해에 도움이 된 블로그)
투포인터로 푸는 방법도 있다. 또 너냐 투포인터? 투포인터는 개념은 간단한데 문제를 보고 이걸 투포인터로 풀어야겠다는 생각이 안드는게 문제다!!! 난도 높은 문제들에 많이 나오던데...
https://sasca37.tistory.com/319
복기
6/22
반응형
'프로그래머스 > 구현' 카테고리의 다른 글
[구현] 프로그래머스 '수식 최대화' - js (0) | 2023.05.15 |
---|---|
[구현] 프로그래머스 '방금그곡' - js (1) | 2023.05.13 |
[투포인터] 프로그래머스 '보석 쇼핑' - js (1) | 2023.05.09 |
[투포인터] 프로그래머스 '두 큐 합 같게 만들기' - js (0) | 2023.05.08 |
[구현] 프로그래머스 '메뉴 리뉴얼' - js (0) | 2023.05.06 |