일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 자바스크립트 문제 풀이
- 자바스크립트코딩테스트
- Baekjoon
- next13
- stack문제
- 제로베이스
- 프로그래머스
- lodash
- 리액트
- JavaScript
- 자바스크립트 알고리즘
- Next.js13
- 리액트쿼리
- 자바스크립트 알고리즘 문제
- CSS
- 자바스크립트 문제풀이
- 타입스크립트
- 알고리즘문제풀이
- Next
- 자바스크립트 연결리스트
- JS
- NPM
- 프론트엔드
- HTML
- 자바스크립트 문제
- 자바스크립트
- react
- leetcode문제풀이
- leetcode
- til
- Today
- Total
코드노트
자바스크립트 스택 문제 풀이 정리, 기린의 시야 본문
이번 문제는 stack을 활용해도 되고 그렇지 않아도 풀 수 있는 문제였다.
stack을 연습중이기 때문에 stack을 활용해서 푼 풀이를 정리하려고 한다.
문제 설명
- 기린은 앞쪽만 볼 수 있다.
- 다른 기린을 몇마리 볼 수 있는지 총 합을 구하는 문제 이다.
- 기린은 자기 앞에 있는 기린들을 볼 수 있는데 자기보다 작거나 같은 기린만 볼 수 있다.
- 자신보다 큰 기린이 나오게 되면 볼 수 없다.
- 입력은 기린 별 키의 값이 들어오며 다른 기린을 볼 수 있는 총합을 구해서 반환하면 되는 문제이다.
처음에 이 문제를 보고 stack을 활용해서 어떻게 풀어야하지? 라는 생각을 했다.
key, value를 활용해서 풀 수 있는 문제 였다.
예를 들어[ 5, 2, 4, 2, 6, 1 ] 의 키를 가진 기린들이 있으면
-> 이쪽 방향으로만 볼 수 있다.
5의 키를 가진 기린은 2, 4, 2의 키를 가진 기린을 볼 수 있고 나머지는 6의 키를 가진 기린 때문에 가려서 보이지 않는다.
5 = 3
2의 키를 가진 기린은 4에 가려서 아무 기린도 보지 못한다.
2 = 0
4의 키를 가진 기린은 2의 키를 가진 기린을 보고 6의 키를 가진 기린 때문에 가려서 보이지 않는다.
4 = 1
2의 키를 가진 기린은 6에 가려서 아무기린도 보지 못한다.
2 = 0
6의 키를 가진 기린은 1의 키를 가진 기린을 볼 수 있다.
6 = 1
1의 키를 가진기린은 마지막 기린이기에 아무도 보지 못한다.
1 = 0
이렇게 자기 앞의 기린을 볼 수 있는 총 합을 구하면 5마리의 기린이 답이다.
stack을 활용해서 문제를 푸는 방법은?
- 우선 코드를 보기전 문제를 이해하려면 정리를 해야한다.
- 우선 stack에 기린의 키를 넣어준다.
- 그리고 자신보다 큰 키를 가진 기린이 나올때까지 stack에 넣어준다.
- 자신보다 큰 기린이 나오게 되면 pop을 시키고 나보다 큰 키를 가진 기린과 stack에 있는 기린의 사이의 기린들의 수를 계산한다.
문제 풀이
let giraffe = [10, 3, 7, 4, 12, 2]
function answer(giraffe) {
let result = 0;
let stack = [];
giraffe.push(Number.MAX_SAFE_INTEGER);
for (let i = 0; i < giraffe.length; i++) {
console.log(stack);
while (stack.length !== 0 && stack[stack.length - 1]["key"] < giraffe[i]) {
// 높이 계산
result += i - stack.pop()["value"] - 1;
}
stack.push({ key: giraffe[i], value: i });
}
console.log(stack);
return result;
}
- stack 배열을 만든다.
- 마지막 기린을 비교할 높은 정수 값을 giraffe에 push해 준다.
- for 문을 통해서 giraffe.length 만큼 순회한다.
- while문을 통해서 stack의 길이가 0이 아니고 stack의 마지막 요소의 key값보다 giraffe[i]의 크기를 비교해 작은 기린이라면?
* result에 index - stack에 있는 마지막 요소의 index값 - 1을 해준다.
// 그 이유는 index로 계산하면 기린과 기린사이의 기린의 수를 알 수 있다.
/* 그리고 -1을 해주는 이유는 사이의 기린의 수만 구해야 하기 때문이다.
* 예를 들어 2번째 기린과 4번째 기린이 있으면 4 - 2는 2이다.
/* 그러나 2번째 기린과 3번째 기린의 사이의 수는 1이다. 그렇기 때문에 -1을 해준다.
- while문으로 조건을 확인하여 실행 후 stack에 push를 해준다.
* push를 할 때에는 index값으로 계산할 수 있도록 key와 value값으로 넣어주어 index값도 같이 넣어준다.
이해하기 쉽도록 실행되는 순서를 나열 했다.
giraffe = [ 10, 3, 7, 4, 12, 2]
i = 0
stack = [];
result = 0;
while stack의 길이가 0이 아니면서 stack의 마지막 요소 (0)가 10( giraffe[0] )보다 작은가?
- stack 의 길이가 0이기 때문에 pass
stack에 { key : 10( giraffe[0] ), value: 0( i ) } push 시킨다.
i = 1
stack = [ { key : 10( giraffe[0] ), value: 0( i ) } ];
result = 0;
while stack의 길이가 0이 아니면서 stack의 마지막 요소(10)가 3( giraffe[1] )보다 작은가?
- stack 의 길이는 0이 아니지만, stack의 마지막 요소는 10이다 10 < 3이 아니기 때문에 pass
stack에 { key : 3( giraffe[1] ), value: 1( i ) } push 시킨다.
i = 2
stack = [
{ key : 10( giraffe[0] ), value: 0( i ) }
{ key : 3( giraffe[1] ), value: 1( i ) }
];
result = 0;
while stack의 길이가 0이 아니면서 stack의 마지막 요소(3)가 7( giraffe[2] )보다 작은가?
- stack 의 길이는 0이 아니고, stack의 마지막 요소는 3이다 3 < 7이 되기 때문에 조건 만족
- result += i - stack.pop()["value"] - 1
//result += 2 - 1 - 1
- 마지막 요소인 3을 pop시키고 다시 while
- stack 의 길이는 0이 아니고, stack의 마지막 요소는 10이다 10 < 7이 되기 때문에 pass
stack에 { key : 7( giraffe[2] ), value: 2( i ) } push 시킨다.
i = 3
stack = [
{ key : 10( giraffe[0] ), value: 0( i ) }
{ key : 7( giraffe[2] ), value: 2( i ) }
];
result = 0;
while stack의 길이가 0이 아니면서 stack의 마지막 요소(7)가 4( giraffe[3] )보다 작은가?
- stack 의 길이는 0이 아니고, stack의 마지막 요소는 7이다 7 < 4가 되기 때문에 pass
stack에 { key : 4( giraffe[3] ), value: 3( i ) } push 시킨다.
i = 4
stack = [
{ key : 10( giraffe[0] ), value: 0( i ) }
{ key : 7( giraffe[2] ), value: 2( i ) }
{ key : 4( giraffe[3] ), value: 3( i ) }
];
result = 0;
while stack의 길이가 0이 아니면서 stack의 마지막 요소(4)가 12( giraffe[4] )보다 작은가?
- stack 의 길이는 0이 아니고, stack의 마지막 요소는 4이다 4 < 12이 되기 때문에 조건 만족
- result += i - stack.pop()["value"] - 1
- result += 4 - 3 - 1 // 현재 i값에서 key 4의 value값인 3을 빼고 1을 빼준다.
- result = 0
- 마자막 요소인 4를 pop시키고 다시 while
- stack 의 길이는 0이 아니고, stack의 마지막 요소는 7이다 7 < 12이 되기 때문에 조건 만족
- result += 4 - 2 - 1 // 현재 i 값에서 key 7의 value값인 2를 빼고 1을 빼준다.
- result = 1
- 마지막 요소인 7을 pop시키고 다시 while
- stack 의 길이는 0이 아니고, stack의 마지막 요소는 10이다 10 < 12이 되기 때문에 조건 만족
- result += 4 - 0 - 1 // 현재 i 값에서 key 10의 value값인 0을 빼고 1을 빼준다.
- result = 4
- 마지막 요소였던 10을 pop 시키고 다시 while
- stack의 길이는 0이다 pass
stack에 { key : 12( giraffe[4] ), value: 4( i ) } push 시킨다.
i = 5
stack = [
{ key : 12( giraffe[4] ), value: 4( i ) }
];
result = 4;
while stack의 길이가 0이 아니면서 stack의 마지막 요소(12)가 2( giraffe[5] )보다 작은가?
- stack 의 길이는 0이 아니고, stack의 마지막 요소는 12이다 12 < 2가 되기 때문에 pass
stack에 { key : 2( giraffe[5] ), value: 5( i ) } push 시킨다.
i = 6 // Number.MAX_SAFE_INTEGER 로 추가해주었기 때문에 length가 하나 더 추가 되었다.
stack = [
{ key : 12( giraffe[4 ), value: 4( i ) }
{ key : 2( giraffe[5] ), value: 5( i ) }
];
result = 4;
while stack의 길이가 0이 아니면서 stack의 마지막 요소(2)가 MAX( giraffe[6] )보다 작은가?
- stack 의 길이는 0이 아니고, stack의 마지막 요소는 2이다 2 < MAX가 되기 때문에 조건 만족
- result += i - stack.pop()["value"] - 1
- result += 6 - 5 - 1
- result = 4
- 마지막 요소였던 2를 pop시키고 다시 while
- stack 의 길이는 0이 아니고, stack의 마지막 요소는 12이다 12 < MAX가 되기 때문에 조건 만족
- result += 6 - 4 - 1
- result = 5
- 마지막 요소였던 12를 pop시키고 다시 while
- stack 의 길이는 0이기 때문에 pass
stack에 { key : 9007199254740991( giraffe[6] ), value: 6( i ) } push 시킨다.
for 문 종료
return result = 5
값은 5
'Code note > 자바스크립트 알고리즘 문제풀이' 카테고리의 다른 글
LeetCode 6. Zigzag Conversion 자바스크립트 문제 풀이 (0) | 2022.09.24 |
---|---|
자바스크립트 스택 알고리즘 문제 풀이, 괄호 계산 (0) | 2022.09.24 |
LeetCode 58. Length of Last Word 문제풀이 자바스크립트 (0) | 2022.09.21 |
leetcode 35. Search Insert Position 문제 풀이 자바스크립트 (0) | 2022.09.21 |
자바스크립트 stack 알고리즘 문제 풀이 / 알파벳 순서대로 꺼내기 (0) | 2022.09.21 |