자바스크립트 스택 문제 풀이 정리, 기린의 시야

이번 문제는 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

---