## Frog River One

### 문제

개구리가 X 까지 가고 싶은데, X까지 가기 위해서는 1부터 X를 모두 지나가야 한다. 예를 들어보자.


```
이렇게 배열이 주어져 있고

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4

5까지 가고 싶다고 가정했을때, A[6]까지는 1~5의 지점이 모두 존재하기 때문에 갈수 있으며, 해당 인덱스인 6을 리턴한다. 
하지만 갈 수 없을 경우 -1을 리턴하면 된다.
```

### 풀이

```javascript
function solution(X, A) {
 
 // X 까지 가고 싶다면, 1~X 까지의 숫자가 모두 존재해야한다.
 let sum = (X * (X + 1)) / 2
 
 // 등장했던 숫자인지 아닌지 판별한다.
 // 이럴거면 굳이 Set을 안써도 되긴하네
 const appear = new Set()

 for (let i=0; i < A.length; i++) { 
 const target = A[i]
 
 // 전에 없던 숫자만
 if (!appear.has(target)) {
 // 숫자를 노출 목록(?) 에 더하고
 appear.add(target)

 // 합계에서 하나씩 뺸다
 sum -= target
 
 // 0 이 된다면 바로 그 index다
 if (sum === 0) {
 return i
 }

 // 만약 0 보다 작아진다면 이미 글러먹었으므로 리턴한다.
 if (sum < 0) {
 return -1
 }
 }
 }
 
 return -1
}
```

## 해설

배열 관련 문제가 나온다면 항상 최초 한번의 순회로 어떻게 잘 승부 볼 수 있을지 고민해보자

https://app.codility.com/demo/results/trainingKDYYTF-8AU/

## Frog River One ### 문제  개구리가 X 까지 가고 싶은데, X까지 가기 위해서는 1부터 X를 모두 지나가야 한다. 예를 들어보자.   ``` 이렇게 배열이 주어져 있고  A[0] = 1 A[1] = 3 A[2] = 1 A[3] = 4 A[4] = 2 A[5] = 3 A[6] = 5 A[7] = 4  5까지 가고 싶다고 가정했을때, A[...

Codility - Frog River One

<h2 id="frog-river-one">Frog River One</h2>
<h3 id="문제">문제</h3>
개구리가 X 까지 가고 싶은데, X까지 가기 위해서는 1부터 X를 모두 지나가야 한다. 예를 들어보자.
<pre><code>이렇게 배열이 주어져 있고

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4

5까지 가고 싶다고 가정했을때, A[6]까지는 1~5의 지점이 모두 존재하기 때문에 갈수 있으며, 해당 인덱스인 6을 리턴한다. 
하지만 갈 수 없을 경우 -1을 리턴하면 된다.
</code></pre>
<h3 id="풀이">풀이</h3>
<pre class="language-javascript"><code class="language-javascript">function solution(X, A) {
 
 // X 까지 가고 싶다면, 1~X 까지의 숫자가 모두 존재해야한다.
 let sum = (X * (X + 1)) / 2
 
 // 등장했던 숫자인지 아닌지 판별한다.
 // 이럴거면 굳이 Set을 안써도 되긴하네
 const appear = new Set()

 for (let i=0; i &#x3C; A.length; i++) { 
 const target = A[i]
 
 // 전에 없던 숫자만
 if (!appear.has(target)) {
 // 숫자를 노출 목록(?) 에 더하고
 appear.add(target)

 // 합계에서 하나씩 뺸다
 sum -= target
 
 // 0 이 된다면 바로 그 index다
 if (sum === 0) {
 return i
 }

 // 만약 0 보다 작아진다면 이미 글러먹었으므로 리턴한다.
 if (sum &#x3C; 0) {
 return -1
 }
 }
 }
 
 return -1
}
</code></pre>
<h2 id="해설">해설</h2>
배열 관련 문제가 나온다면 항상 최초 한번의 순회로 어떻게 잘 승부 볼 수 있을지 고민해보자
<a href="https://app.codility.com/demo/results/trainingKDYYTF-8AU/">https://app.codility.com/demo/results/trainingKDYYTF-8AU/</a>

## Triangle

### 문제

길이 N의 배열 A가 주어진다. 

(P, Q, R)은 삼각형이 될 수 있는데, 이는 

- 0 ≤ P < Q < R < N 
- A[P] + A[Q] > A[R]
- A[Q] + A[R] > A[P]
- A[R] + A[P] > A[Q]

라는 조건을 만족 하기 때문이다.

```
A[0] = 10 
A[1] = 2 
A[2] = 5
A[3] = 1
A[4] = 8
A[5] = 20

은 0, 2, 4 (10, 5, 8)로 삼각형을 만들 수 있으므로 1을 리턴한다. 그러나 만들 수 없다면 0을 리턴한다.
```

주어진 A 배열에서 삼각형을 만들 수 있는 3개의 조합이 존재하는지 확인해서, 존재한다면 1을, 아니라면 0을 리턴해라.

### 풀이

```javascript
function solution(A) {
 const sorted = A.sort((a, b) => a - b)
 
 for (let i=0; i<sorted.length-2; i++) {
 
 const a = sorted[i]
 const b = sorted[i+1]
 const c = sorted[i+2]
 
 if (a + b > c && b + c > a && a + c > b) {
 return 1
 }
 }
 
 return 0
}
```

https://app.codility.com/demo/results/training6R2NPK-JJH/

## Triangle ### 문제 길이 N의 배열 A가 주어진다. (P, Q, R)은 삼각형이 될 수 있는데, 이는 - 0 ≤ P < Q < R < N - A[P] + A[Q] > A[R] - A[Q] + A[R] > A[P] - A[R] + A[P] > A[Q] 라는 조건을 만족 하기 때문이다. ``` A[0] = 10 A[1] ...

Codility - Triangle

<h2 id="triangle">Triangle</h2>
<h3 id="문제">문제</h3>
길이 N의 배열 A가 주어진다.
(P, Q, R)은 삼각형이 될 수 있는데, 이는
<ul>
<li>0 ≤ P &#x3C; Q &#x3C; R &#x3C; N</li>
<li>A[P] + A[Q] > A[R]</li>
<li>A[Q] + A[R] > A[P]</li>
<li>A[R] + A[P] > A[Q]</li>
</ul>
라는 조건을 만족 하기 때문이다.
<pre><code>A[0] = 10 
A[1] = 2 
A[2] = 5
A[3] = 1
A[4] = 8
A[5] = 20

은 0, 2, 4 (10, 5, 8)로 삼각형을 만들 수 있으므로 1을 리턴한다. 그러나 만들 수 없다면 0을 리턴한다.
</code></pre>
주어진 A 배열에서 삼각형을 만들 수 있는 3개의 조합이 존재하는지 확인해서, 존재한다면 1을, 아니라면 0을 리턴해라.
<h3 id="풀이">풀이</h3>
<pre class="language-javascript"><code class="language-javascript">function solution(A) {
 const sorted = A.sort((a, b) => a - b)
 
 for (let i=0; i&#x3C;sorted.length-2; i++) {
 
 const a = sorted[i]
 const b = sorted[i+1]
 const c = sorted[i+2]
 
 if (a + b > c &#x26;&#x26; b + c > a &#x26;&#x26; a + c > b) {
 return 1
 }
 }
 
 return 0
}
</code></pre>
<a href="https://app.codility.com/demo/results/training6R2NPK-JJH/">https://app.codility.com/demo/results/training6R2NPK-JJH/</a>

## Number of Disc Intersections

### 문제

N개의 디스크가 존재하고, 디스크는 각각 0~ N-1의 번호를 가진다. 이는 A라는 배열에서 표현되는데, `A[N]` 는 해당 디스크의 반경을 의미한다. 

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

![discs](https://codility-frontend-prod.s3.amazonaws.com/media/task_static/number_of_disc_intersections/static/images/auto/0eed8918b13a735f4e396c9a87182a38.png)

이 때, 교차하는 디스크의 수를 구하라.

### 풀이

```javascript
function solution(A) {
 const length = A.length
 let intersections = 0
 
 // 시작 점과 끝점을 저장하는 새로운 배열을 만든다.
 // [ [ -1, 1 ], [ -4, 6 ], [ 0, 4 ], [ 2, 4 ], [ 0, 8 ], [ 5, 5 ] ]
 const info = A.map((disc, index) => [index - disc, index + disc])
 
 // 이를 시작점이 작은 순대로 배열한다.
 // [ [ -4, 6 ], [ -1, 1 ], [ 0, 4 ], [ 0, 8 ], [ 2, 4 ], [ 5, 5 ] ]
 const sorted = info.sort((a, b) => a[0] - b[0])
 
 // 가장 바깥에 있는 원부터 돈다
 for (let i=0; i < sorted.length; i++) {
 // const targetStart = sorted[i][0]
 const targetEnd = sorted[i][1]
 
 // 그 다음 것 부터 돈다
 for (let j=i+1; j < sorted.length; j++) {
 const compareStart = sorted[j][0]
 // const compareEnd = sorted[j][1]
 
 // 겹치는 경우에만
 if (compareStart <= targetEnd) {
 intersections += 1
 // 겹치는 횟수가 특정 횟수를 넘어가면 -1을 리턴하랜다.
 if (intersections > 10000000) {
 return -1
 }
 } else {
 // 시작점 순으로 정렬했으므로, 이 이후는 안봐도 안겹친다. 따라서 break
 break
 }
 }
 }
 
 return intersections
}
```

하나씩 고민해보자. 1과 5과 교차하기 위해서는 어떻게 해야할까? 둘 사이의 거리는 일단 4다. 두 반지름 (반경)의 합이 4를 넘어야 한다. for 문을 돌면서 둘 사이의 차이와 반지름의 합을 계산해서 구해보면 될까?

라고 했지만 타임아웃 에러가 났다. for문을 이중으로 돌아야 하기 때문에 `O(N^2)`복잡도가 나온다. break가 없어서 빼도 박도 못한다. 

둘이 겹치는지 안겹치는지 확인해볼 수 있는 방법이 있을까? 각 그리는 원마다 시작점과 끝점을 `[s, e]` 식으로 저장해 두었다가, 비교 대상의 끝점과 시작점이 겹치는지 확인해보면 될 것이다.

https://app.codility.com/demo/results/training86S6RE-49X/

## Number of Disc Intersections ### 문제  N개의 디스크가 존재하고, 디스크는 각각 0~ N-1의 번호를 가진다. 이는 A라는 배열에서 표현되는데, `A[N]` 는 해당 디스크의 반경을 의미한다.   ``` A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0 ```  ![discs]...

Codility - Number of Disc Intersections

## Max Product of Three

### 문제

길이 N인 배열 A가 주어졌을때, 임의로 세개의 숫자를 곱했을 때 가장 큰 값을 만들 수 있는 배열의 Index를 리턴해라.

```
A[0] = -3
A[1] = 1
A[2] = 2
A[3] = -2
A[4] = 5
A[5] = 6

2, 4, 5번째를 곱하면 60을 만들수 있고 이것이 가장 큰 경우 이므로, 60을 리턴하면된다.
```

### 풀이

```javascript
function solution(A) {
 
 const sorted = A.sort((a, b) => a - b)
 const size = sorted.length
 
 let biggest = 0

 biggest = sorted[size-1] * sorted[size-2] * sorted[size-3]
 
 if (sorted[0] < 0 && sorted[1] < 0 && sorted[size-1] > 0) {
 
 const possible = sorted[0] * sorted[1] * sorted[size-1]
 
 if (possible > biggest) {
 biggest = possible
 }
 } 
 
 return biggest
}
```

하나 조심해야 할 것은, 두 개의 음수 * 한개의 양수 조합으로도 큰 수를 만들 수 있다는 것이다. 따라서 무조건 큰 값 세개를 곱해버리면 안된다. 따라서 가장 큰 수를 만들 수 있는 경우의 수는 아래와 같다.

- 숫자가 큰 순서대로 세개를 곱하거나
- 음수이하의 가장 작은 숫자 두개를 곱하고 가장 큰 양수를 곱하거나

또 하나 조심해야할 것은, `sort()`다. 그냥 아무 함수 없이 sort했더니, 제대로 정렬하지 못했다. (졸아서 그런거라고 치자)

> compareFunction이 제공되지 않으면 요소를 문자열로 변환하고 유니 코드 코드 포인트 순서로 문자열을 비교하여 정렬됩니다. 예를 들어 "바나나"는 "체리"앞에옵니다. 숫자 정렬에서는 9가 80보다 앞에 오지만 숫자는 문자열로 변환되기 때문에 "80"은 유니 코드 순서에서 "9"앞에옵니다.

한국 말이 더 어렵다 (....)

> If compareFunction is not supplied, all non-undefined array elements are sorted by converting them to strings and comparing strings in UTF-16 code units order. For example, "banana" comes before "cherry". In a numeric sort, 9 comes before 80, but because numbers are converted to strings, "80" comes before "9" in the Unicode order. All undefined elements are sorted to the end of the array.

비교 함수가 정의 되지 않는다면, 모든 요소를 string으로 변환하고 이 string을 UTF-16 코드로 변환해서 비교 한다는 것이다.

```javascript
const a = [-1, -10, -9, -5, -7]
const sorted = a.sort()
console.log(sorted) // [-1, -10, -5, -7, -9]]
```

숫자 비교 시에는 절대 compareFunction을 비우지말자 - 

[출처](https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort)

https://app.codility.com/demo/results/trainingCGB84G-ST8/

## Max Product of Three ### 문제  길이 N인 배열 A가 주어졌을때, 임의로 세개의 숫자를 곱했을 때 가장 큰 값을 만들 수 있는 배열의 Index를 리턴해라.  ``` A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6  2, 4, 5번째를 곱하면 60을 만들수 있고 이것이 가장 큰 ...

Codility - Max Product of Three

## Distinct

### 문제

배열 A안에 unique한 숫자가 몇 개 있는지 리턴하라.

### 풀이

```javascript
function solution(A) {
    return [...new Set(A)].length
}
```

Set을 활용하면 쉽게 풀 수 있다. Set이 아니더라도 object등을 활용해보면 된다.


https://app.codility.com/demo/results/training4VKM6Q-5SX/

## Distinct ### 문제  배열 A안에 unique한 숫자가 몇 개 있는지 리턴하라.  ### 풀이  ```javascript function solution(A) {     return [...new Set(A)].length } ```  Set을 활용하면 쉽게 풀 수 있다. Set이 아니더라도 object등을 활용해보면 된다.   https:...

yceffort

Codility - Frog River One

Codility - Triangle

Codility - Number of Disc Intersections

Codility - Max Product of Three

Codility - Distinct