## Nesting

### 문제

`(`와 `)`로 이루어진 문자열이 있다. 이 문자열의 `(` `)` 짝이 맞게 이루어져 있는지 확인하라.

### 풀이

```javascript
function solution(S) {
    const split = S.split('')
    const stack = []
    for (let i of split) {
        // 여는 괄호라면 스택에 하나씩 넣는다
        if (i === '(') {
            stack.push(true)
        // 닫는 괄호라면
        } else {
            // 닫는괄호인데 여는괄호가 없다면 이미 글러먹었다
            if (stack.length === 0) {
                return 0
            // 하나 있으면 꺼낸다
            } else {
                stack.pop()
            }
        }
    }
    
    // 스택이 깔끔하게 비어있으면 1을 리턴한다.
    return stack.length === 0 ? 1 : 0
}
```

https://app.codility.com/demo/results/training8N66E9-5ZY/

## Nesting ### 문제  `(`와 `)`로 이루어진 문자열이 있다. 이 문자열의 `(` `)` 짝이 맞게 이루어져 있는지 확인하라.  ### 풀이  ```javascript function solution(S) {     const split = S.split('')     const stack = []     for (let i of split...

Codility - Nesting

## Fish

### 문제

길이 N으로 이루어진 비어있지 않은 배열 A, B가 주어진다. 배열 A는 물고기의 크기를, B는 물고기의 움직임을 나타내는데, 0일 경우 위로, 1일 경우 아래로 간다. 만약 두마리의 물고기가 만날 경우, 더 사이즈가 큰 물고기가 잡아먹어버린다. 이 때 살아남는 물고기의 수를 구하라.

```bash
A[0] = 4 B[0] = 0
A[1] = 3 B[1] = 1
A[2] = 2 B[2] = 0
A[3] = 1 B[3] = 0
A[4] = 5 B[4] = 0

0번 물고기는 위로 간다
1번 물고기는 밑으로 가는데, 2번 물고기는 위로 간다. 이 때 1번 물고기는 2번 물고기를 먹는다
마찬가지로 3번 물고기도 먹고, 
그러나 4번물고기는 5로 1번 물고기보다 덩치가 크므로 4번 물고기가 1번물고기를 먹는다

이때 그래서 살아남는 물고기는 2마리다.
```

### 풀이

```javascript
function solution(A, B) {
 
 // 하류로 가는 물고기를 쌓는 스택
 const stack = []
 let count = 0
 
 for (let i=0; i < A.length; i++) {
 // 물고기가 하류로 가면 그 물고기의 크기를 스택에 쌓는다
 if (B[i] === 1) {
 stack.push(A[i])
 } 
 // 물고기가 상류로 갈경우
 else {
 // 하류행 물고기가 있는지 계속해서 확인한다
 while (stack.length > 0) {
 // 하류행 물고기가 있으면 한마리 씩 맞짱 뜬다
 // 하류행 물고기가 더 크면 패배
 if (stack[stack.length - 1] > A[i]) {
 break
 } 
 // 상류행 물고기가 더 크면 하류행 물고기 하나의 숨통을 끊는다
 else {
 stack.pop()
 }
 } 
 
 // 그렇게 상류행 물고기를 다 이겨야 생존 카운트를 올릴 수 있다.
 if (stack.length === 0) {
 count += 1 
 }
 }
 }
 
 // 최종 생존 명단은 하류로 가는 물고기 중 살아남은 물고기 + 상류로 갔는데 살아남은 물고기다.
 return stack.length + count
}
```

## Fish ### 문제  길이 N으로 이루어진 비어있지 않은 배열 A, B가 주어진다. 배열 A는 물고기의 크기를, B는 물고기의 움직임을 나타내는데, 0일 경우 위로, 1일 경우 아래로 간다. 만약 두마리의 물고기가 만날 경우, 더 사이즈가 큰 물고기가 잡아먹어버린다. 이 때 살아남는 물고기의 수를 구하라.  ``` A[0] = 4    B[0] =...

Codility - Fish

<h2 id="fish">Fish</h2>
<h3 id="문제">문제</h3>
길이 N으로 이루어진 비어있지 않은 배열 A, B가 주어진다. 배열 A는 물고기의 크기를, B는 물고기의 움직임을 나타내는데, 0일 경우 위로, 1일 경우 아래로 간다. 만약 두마리의 물고기가 만날 경우, 더 사이즈가 큰 물고기가 잡아먹어버린다. 이 때 살아남는 물고기의 수를 구하라.
<pre class="language-bash"><code class="language-bash">A[0] = 4 B[0] = 0
A[1] = 3 B[1] = 1
A[2] = 2 B[2] = 0
A[3] = 1 B[3] = 0
A[4] = 5 B[4] = 0

0번 물고기는 위로 간다
1번 물고기는 밑으로 가는데, 2번 물고기는 위로 간다. 이 때 1번 물고기는 2번 물고기를 먹는다
마찬가지로 3번 물고기도 먹고, 
그러나 4번물고기는 5로 1번 물고기보다 덩치가 크므로 4번 물고기가 1번물고기를 먹는다

이때 그래서 살아남는 물고기는 2마리다.
</code></pre>
<h3 id="풀이">풀이</h3>
<pre class="language-javascript"><code class="language-javascript">function solution(A, B) {
 
 // 하류로 가는 물고기를 쌓는 스택
 const stack = []
 let count = 0
 
 for (let i=0; i &#x3C; A.length; i++) {
 // 물고기가 하류로 가면 그 물고기의 크기를 스택에 쌓는다
 if (B[i] === 1) {
 stack.push(A[i])
 } 
 // 물고기가 상류로 갈경우
 else {
 // 하류행 물고기가 있는지 계속해서 확인한다
 while (stack.length > 0) {
 // 하류행 물고기가 있으면 한마리 씩 맞짱 뜬다
 // 하류행 물고기가 더 크면 패배
 if (stack[stack.length - 1] > A[i]) {
 break
 } 
 // 상류행 물고기가 더 크면 하류행 물고기 하나의 숨통을 끊는다
 else {
 stack.pop()
 }
 } 
 
 // 그렇게 상류행 물고기를 다 이겨야 생존 카운트를 올릴 수 있다.
 if (stack.length === 0) {
 count += 1 
 }
 }
 }
 
 // 최종 생존 명단은 하류로 가는 물고기 중 살아남은 물고기 + 상류로 갔는데 살아남은 물고기다.
 return stack.length + count
}
</code></pre>

## Brackets

### 문제

문자열 S가 주어지고, S는 다음 경우 일 때 참을 반환해야 한다.

- S가 비어있는 경우
- `(U)` or `[U]` or `{U}` 의 형태로 괄호안에 문자열이 있는 경우
- 괄호가 짝이 맞게 닫혀있는 경우

예를 들어

`{[()()]}`는 괄호가 알맞게 들어있지만, `([)()]`는 그렇지 못하다. (짝은 맞지만 잘못닫혀있음)괄호가 올바르게 형성되어 있는 경우 1, 아니면 0을 리턴하자.

### 풀이

```javascript
function solution(S) {
    const splited = S.split('')
    
    const stack = []
    
    for (let i of splited) {
        // 여는 거
        if (i === '{' || i === '[' || i ==='(') {
            stack.push(i)
        } else {
            if (stack.size === 0) return 0
            
            // 닫는 것이라면 가장 최근에 열었던 것이랑 비교 한다.
            const pop = stack.pop()
            
            if (i === ')') {
                if (pop !== '(') {
                    return 0
                }
            }
            
            if (i === '}') {
                if (pop !== '{') {
                    return 0
                }
            }
            
            if (i === ']') {
                if (pop !== '[') {
                    return 0
                }
            }
            
        }
    }
    
    return stack.length === 0 ? 1 : 0
}
```

여는 괄호라면 stack에 넣고, 닫는 괄호라면 스택에 맨지막 괄호와 비교해서 적절한 괄호인지 확인한다.

https://app.codility.com/demo/results/training9MREFG-CYW/

## Brackets ### 문제  문자열 S가 주어지고, S는 다음 경우 일 때 참을 반환해야 한다.  - S가 비어있는 경우 - `(U)` or `[U]` or `{U}` 의 형태로 괄호안에 문자열이 있는 경우 - 괄호가 짝이 맞게 닫혀있는 경우  예를 들어  `{[()()]}`는 괄호가 알맞게 들어있지만, `([)()]`는 그렇지 못하다. (짝은 맞...

Codility - Brackets

## Missing Integer

### 문제

주어진 배열 A에 빠져 있는 가장 작은 양의 정수를 구하시오

```
A=[1, 3, 6, 4, 1, 2] 이라면 답은 5
A=[1, 2, 3] 이라면 답은 4
A=[-1, -3] 이라면 답은 1
```


### 풀이

```javascript
function solution(A) {
 // 배열 길이 만큼 false로 채워진 체커를 생성
 const checker = Array(A.length).fill(false)
 
 // A를 돌면서 양의 정수라면 해당 checker의 index를 true로 바꿔준다.
 for (let i=0; i<A.length; i++) {
 if (A[i] > 0) {
 checker[A[i]-1] = true
 }
 }
 
 // 가장 가까운 false위치를 찾는다.
 const index = checker.indexOf(false)
 // 없으면 모든 수가 다 차있는 것이므로 길이 + 1, 아니라면 해당 index + 1을 리턴한다.
 return index === -1 ? checker.length + 1 : index + 1
}
```


### 해설

문제와 관련된 해설은 아니고, indexOf는 일반적인 배열을 for 

https://app.codility.com/demo/results/training8EH9VG-2JS/

## Missing Integer ### 문제  주어진 배열 A에 빠져 있는 가장 작은 양의 정수를 구하시오  ``` A=[1, 3, 6, 4, 1, 2] 이라면 답은 5 A=[1, 2, 3] 이라면 답은 4 A=[-1, -3] 이라면 답은 1 ```   ### 풀이  ```javascript function solution(A) {     // 배열 길...

Codility - Missing Integer

<h2 id="missing-integer">Missing Integer</h2>
<h3 id="문제">문제</h3>
주어진 배열 A에 빠져 있는 가장 작은 양의 정수를 구하시오
<pre><code>A=[1, 3, 6, 4, 1, 2] 이라면 답은 5
A=[1, 2, 3] 이라면 답은 4
A=[-1, -3] 이라면 답은 1
</code></pre>
<h3 id="풀이">풀이</h3>
<pre class="language-javascript"><code class="language-javascript">function solution(A) {
 // 배열 길이 만큼 false로 채워진 체커를 생성
 const checker = Array(A.length).fill(false)
 
 // A를 돌면서 양의 정수라면 해당 checker의 index를 true로 바꿔준다.
 for (let i=0; i&#x3C;A.length; i++) {
 if (A[i] > 0) {
 checker[A[i]-1] = true
 }
 }
 
 // 가장 가까운 false위치를 찾는다.
 const index = checker.indexOf(false)
 // 없으면 모든 수가 다 차있는 것이므로 길이 + 1, 아니라면 해당 index + 1을 리턴한다.
 return index === -1 ? checker.length + 1 : index + 1
}
</code></pre>
<h3 id="해설">해설</h3>
문제와 관련된 해설은 아니고, indexOf는 일반적인 배열을 for
<a href="https://app.codility.com/demo/results/training8EH9VG-2JS/">https://app.codility.com/demo/results/training8EH9VG-2JS/</a>

## Max Counters

### 문제

숫자 N이 주어진다. 이 숫자 N은 모든 요소가 0인 길이 N인 배열을 의미한다. 그리고 배열 A가 존재한다. 

```
숫자 N이 5로 주어지고, 배열 A는 [3, 4, 4, 6, 1, 4, 4] 라고 가정하자.

초기 값 [0, 0, 0, 0 0]
A[0] = 3, 3번째 (3-1번째) 요소의 크기를 1 늘린다.
- [0, 0, 1, 0, 0]
A[0] = 4, 4번째 (4-1번째) 요소의 크기를 1 늘린다.
- [0, 0, 1, 1, 0]
A[0] = 4, 4번째 (4-1번째) 요소의 크기를 1 늘린다.
- [0, 0, 1, 2, 0]
A[0] = 6, 모든 숫자의 크기를 현재 가장 큰 값으로 맞춘다.
- [2, 2, 2, 2, 2]
....

최종 결과는 
- [3, 2, 2, 4, 2]
```

### 풀이

```javascript
function solution(N, A) {
 // 0으로 초기화된 길이 N의 배열을 만든다.
 const array = Array(N).fill(0)
 // 배열 내 최대 값
 let max = 0
 // 마지막 max counter의 기준이 되었던 수
 let maxCounter = 0
 for (let i=0; i<A.length; i++) {
 // 모든 숫자를 올려야 하는 경우
 if (A[i] > N) {
 // maxCounter에 다같이 올라가는 최대 숫자를 저장해 둔다.
 maxCounter = max

 // 하나씩만 올리면 되는 경우 
 } else {
 
 // 현재 숫자가 maxCounter보다 작을 경우 maxCounter로 초기화 한다.
 if (array[A[i] - 1] < maxCounter) {
 array[A[i] - 1] = maxCounter
 }
 
 // 그리고 +1을 한다
 array[A[i] - 1] += 1 
 
 
 // 이렇게 새롭게 세팅된 숫자가 배열의 최대값인지 확인한다.
 if (max < array[A[i] - 1]) {
 max = array[A[i] - 1]
 }
 
 }
 }

 // 배열의 값이 maxCounter보다 작다면 그 값으로 리턴한다. 
 return array.map((i) => i < maxCounter ? maxCounter : i)
}
```

## 해설

처음에는 저 maxCounter액션을 array를 map을 돌면서 +1 을 해줬더니 timeout 에러가 났다. 그도 그럴 것이 안그래도 배열을 n회 순환하는데, +1 을하면서 또 순환하면 복잡도가 `O(N^2)`이 될 것이기 때문이다. 그래서 최대한 배열을 한번에 순환하는 방식으로 해결하고자 노력했다.

https://app.codility.com/demo/results/training7YGA6S-4D7/

## Max Counters ### 문제  숫자 N이 주어진다. 이 숫자 N은 모든 요소가 0인 길이 N인 배열을 의미한다. 그리고 배열 A가 존재한다.   ``` 숫자 N이 5로 주어지고, 배열 A는 [3, 4, 4, 6, 1, 4, 4] 라고 가정하자.  초기 값 [0, 0, 0, 0 0] A[0] = 3, 3번째 (3-1번째) 요소의 크기를 1 늘린...

yceffort

Codility - Nesting

Codility - Fish

Codility - Brackets

Codility - Missing Integer

Codility - Max Counters