## 2-2 Odd Occurrences in array

### 문제

숫자로 이뤄진 배열에서 홀수 번 등장하는 숫자를 찾아서 리턴해라.

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

7은 한번만 등장하므로 7을 리턴해야 한다.
```

### 풀이

```javascript
function solution(A) {
 // 등장하는 숫자를 저장한다. 
 const map = {}
 
 // 숫자를 순회한다
 for (let i=0; i <= A.length - 1; i++) {
 const target = A[i]
 // 해당 숫자가 존재한다면 해당 키를 제거한다.
 if (map[target]) {
 delete map[target]
 // 해당 숫자가 존재하지 않는다면 (처음등장했다면) 추가한다.
 } else {
 map[target] = true
 }
 }
 
 // 리턴한다.
 return +Object.keys(map)[0]
}
```

### 해설

믿거나 말거나 성능은 `O(N) or O(N*log(N))` 가 나왔는데, 생각보다 key-value객체에 key값으로 접근하는 속도가 빠른듯.

https://app.codility.com/demo/results/trainingBF4N34-BBK/

## 2-2 Odd Occurrences in array ### 문제  숫자로 이뤄진 배열에서 홀수 번 등장하는 숫자를 찾아서 리턴해라.  ``` A[0] = 9  A[1] = 3  A[2] = 9 A[3] = 3  A[4] = 9  A[5] = 7 A[6] = 9  7은 한번만 등장하므로 7을 리턴해야 한다. ```  ### 풀이  ```javascri...

Codility - Odd Occurrences in array

## 2-1 Cyclic Rotation

### 문제

배열 A가 주어지고 이를 K번 각 배열의 요소를 오른쪽으로 이동시켰을 때, 그 결과를 리턴하시오.

```
A = [3, 8, 9, 7, 6]
K = 3

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]
```

### 풀이

```javascript
function solution(A, K) {
    // 오른쪽으로 움직여야 하는 횟수
    const sliceTimes = K % A.length
  
    // 회전할 필요가 없거나, 회전을 배열 길이 만큼 한다면 그냥 배열을 리턴한다.
    if (sliceTimes === 0 || sliceTimes === A.length) {
      return A;
    }
      
    // 배열을 잘 잘라서 리턴한다.
    return [...A.slice(A.length - sliceTimes), ...A.slice(0, A.length - sliceTimes)]
}
```

### 해설

문제와 관련이 없지만, [splice](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice)는 원본 배열에 영향을 미치고, [slice](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/slice)는 원본 배열에 영향을 미치지 않는다.

https://app.codility.com/demo/results/trainingYUK5SH-UVZ/


## 2-1 Cyclic Rotation ### 문제  배열 A가 주어지고 이를 K번 각 배열의 요소를 오른쪽으로 이동시켰을 때, 그 결과를 리턴하시오.  ``` A = [3, 8, 9, 7, 6] K = 3  [3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7] [6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9] [7, 6, 3, 8...

Codility - Cyclic Rotation

## 1-1 Binary Gap

### 문제

숫자 N을 이진수로 바꿨을때, 1과 1사이에 있는 0의 개수가 가장 많이 연속해 있는 0의 개수를 구하라.

```
9는 이진수로 바꿀 경우 1001, 이경우 0의 최대 개수는 2.
529는 이진수로 바꿀 경우 1000010001, 이경우 0의 최대 개수는 3.
20은 이진수로 바꿀 경우 10100, 이 경우 0의 최대 개수는 1. (100은 1로 둘러 쌓여 있지 않음)
15는 이진수로 바꿀경우 1111 이므로, 0의 개수는 0개
```

### 풀이

```javascript
function solution(N) {
 // 2진법으로 변환
 const binary = N.toString(2)
 // 1로 쪼갠다.
 const splitted = binary.split(1)
 
 // 두개 이하로 쪼개질 경우, 1이 한개 밖에 없으므로 값은 0
 if (splitted.length <= 2) {
 return 0
 } else {
 // 마지막 나누기는 의미가 없다. 
 // '' 이거나 1로 막혀있지 않다면 숫자가 나올 것이므로
 splitted.pop()
 // 제일 
 return splitted.reduce((p, c) => c.length > p ? c.length : p , 0)
 }
}
```

### 해설

배열의 마지막 요소를 `pop`하는 것만 기억하면 될 듯.

https://app.codility.com/demo/results/training3C4SN2-EXK/

## 1-1 Binary Gap ### 문제  숫자 N을 이진수로 바꿨을때, 1과 1사이에 있는 0의 개수가 가장 많이 연속해 있는 0의 개수를 구하라.  ``` 9는 이진수로 바꿀 경우 1001, 이경우 0의 최대 개수는 2. 529는 이진수로 바꿀 경우 1000010001, 이경우 0의 최대 개수는 3. 20은 이진수로 바꿀 경우 10100, 이 경우...

Codility - Binary Gap

<h2 id="1-1-binary-gap">1-1 Binary Gap</h2>
<h3 id="문제">문제</h3>
숫자 N을 이진수로 바꿨을때, 1과 1사이에 있는 0의 개수가 가장 많이 연속해 있는 0의 개수를 구하라.
<pre><code>9는 이진수로 바꿀 경우 1001, 이경우 0의 최대 개수는 2.
529는 이진수로 바꿀 경우 1000010001, 이경우 0의 최대 개수는 3.
20은 이진수로 바꿀 경우 10100, 이 경우 0의 최대 개수는 1. (100은 1로 둘러 쌓여 있지 않음)
15는 이진수로 바꿀경우 1111 이므로, 0의 개수는 0개
</code></pre>
<h3 id="풀이">풀이</h3>
<pre class="language-javascript"><code class="language-javascript">function solution(N) {
 // 2진법으로 변환
 const binary = N.toString(2)
 // 1로 쪼갠다.
 const splitted = binary.split(1)
 
 // 두개 이하로 쪼개질 경우, 1이 한개 밖에 없으므로 값은 0
 if (splitted.length &#x3C;= 2) {
 return 0
 } else {
 // 마지막 나누기는 의미가 없다. 
 // '' 이거나 1로 막혀있지 않다면 숫자가 나올 것이므로
 splitted.pop()
 // 제일 
 return splitted.reduce((p, c) => c.length > p ? c.length : p , 0)
 }
}
</code></pre>
<h3 id="해설">해설</h3>
배열의 마지막 요소를 <code>pop</code>하는 것만 기억하면 될 듯.
<a href="https://app.codility.com/demo/results/training3C4SN2-EXK/">https://app.codility.com/demo/results/training3C4SN2-EXK/</a>

## 연결리스트

연결리스트, Linked List 는 각 노드들이 한 줄로 연결되어 있는 방식으로 각 노드는 데이터와 포인터 (다음 노드의 정보)를 가지고 있다. 연결리스트는 일반적인 배열과 다르게 삽입과 삭제가 `O(1)`에 가능하다는 장점이 있다. 하지만 특정 n번 째 정보를 찾는 데에는 `O(n)`시간이 걸린다는 단점도 있다.

![단일 연결 리스트](https://upload.wikimedia.org/wikipedia/commons/thumb/9/9c/Single_linked_list.png/800px-Single_linked_list.png)

![이중 연결 리스트](https://upload.wikimedia.org/wikipedia/commons/thumb/c/ca/Doubly_linked_list.png/800px-Doubly_linked_list.png)

이중 연결리스트는 이 포인터에 앞, 뒤 정보가 모두 담겨 있다.

![원형 연결 리스트](https://upload.wikimedia.org/wikipedia/commons/thumb/9/98/Circurlar_linked_list.png/800px-Circurlar_linked_list.png)

마지막 노드의 포인터가 첫 번째 노드를 가르킨다.

## 구현

먼저 가장 최초에 있는 노드를 `header`라고 부르고, 맨 마지막에 있는 노드를 `tail`이라고 부른다. 또한 일반적인 배열과는 다르게, 배열의 시작을 1로 하고, 0번째 노드는 비어있는 노드로 가정한다. 이는 구현에 있어 조금 더 편하게 하기 위함이다.

그리고 구현해볼 메소드는 다음과 같다.

- print: 리스트를 볼 수 있도록 프린트 한다.
- getAt(n): n번째 노드를 꺼낸다.
- insertAt(n, node): n번째에 `node`를 삽입한다.
- insertAfter(prev, new): `prev`이후에 `new`를 삽입한다.
- popAt(n): n번째 노드를 삭제한다.
- popAfter(prev): `prev` 이후 노드를 삭제한다.
- size: 전체 노드 개수를 계산한다.
- traverse: 전체 노드를 배열로 리턴한다.

### python

#### Node

```python
class Node:
 def __init__(self, item):
 self.data = item # 데이터 정보
 self.next = None # 다음 노드 정보
```

#### Linked List

```python
class LinkedList:
 def __init__(self):
 self.size = 0
 self.head = Node(None)
 self.tail = None

 def traverse(self):
 result = []
 curr = self.head
 while curr.next:
 curr = curr.next
 result.append(curr.data)
 return result

 def getAt(self, n):
 if n < 0 or n > self.size:
 return None

 i = 0
 curr = self.head
 while i < n:
 curr = curr.next
 i += 1
 
 return curr

 def insertAfter(self, prev, new):
 # 새로운 노드의 다음 노드는 이전 노드의 다음 정보
 new.next = prev.next
 # prev가 tail일 경우
 if prev.next is None:
 self.tail = new
 # 이제 이전 노드의 다음 노드는 사로운 노드
 prev.next = new
 self.size += 1


 def insertAt(self, n, new):
 if n < 1 or n > self.size + 1:
 return False

 # tail에 들어갈 경우
 if n != 1 and n == self.size + 1:
 prev = self.tail
 else:
 prev = self.getAt(n - 1)

 return self.insertAfter(prev, new)

 def popAfter(self, prev):
 popData = prev.next.data
 ## tail 을 제거하려고 할때 
 if prev.next.next is None: 
 self.tail = prev
 prev.next = None
 else:
 prev.next = prev.next.next
 
 self.size -= 1

 return popData

 def popAt(self, n):
 if n < 1 or n > self.size:
 raise IndexError

 # head일 경우
 if n == 1:
 prev = self.head
 else: 
 prev = self.getAt(n - 1)
 
 return self.popAfter(prev)

 def print(self):
 if self.size == 1:
 print("this linked list is empty")
 else:
 print(self.traverse())
```

## 연결리스트 연결리스트, Linked List 는 각 노드들이 한 줄로 연결되어 있는 방식으로 각 노드는 데이터와 포인터 (다음 노드의 정보)를 가지고 있다. 연결리스트는 일반적인 배열과 다르게 삽입과 삭제가 `O(1)`에 가능하다는 장점이 있다. 하지만 특정 n번 째 정보를 찾는 데에는 `O(n)`시간이 걸린다는 단점도 있다.  ![단일 연결 리스트...

알고리즘 - 연결 리스트

## 요구사항

한 엘리먼트안에서 특정한 키워드를 다른 색싱으로 바꿔서 출력하는 것이다.

아래 예시를 살펴보자

### before

```jsx
<Text>카카오 페이지 카카오 스토리 카카오톡</Text>
```

### after

```jsx
<Text>
 <Text color="blue">카카오 </Text>페이지
 <Text color="blue">카카오 </Text>스토리
 <Text color="blue">카카오</Text>톡
</Text>
```

## 의식의 흐름

특정 키워드가 포함되어 있는지, 그리고 그것을 따로 뽑아 낼 수 있는 가장 간단한 방법은 무엇일까? 바로 [split](https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/String/split) 일 것이다.

```javascript
const splitResult = '카카오 페이지, 카카오 스토리, 카카오톡'
splitResult.split('카카오') // ["", " 페이지, ", " 스토리, ", "톡"]
```

그러나 여기서 두 가지 몰랐던 사실을 알게 된다.

1. 첫 문자에 seperator 가 동일하게 나올 경우, 앞에 ""가 무조건 나온다.
2. text === seperator 면 결과는 빈 문자열 두개다.

```javascript
const splitResult = '카카오'
splitResult.split('카카오') //  ["", ""]
```

> 문자열에서 separator가 등장하면 해당 부분은 삭제되고 남은 문자열이 배열로 반환됩니다. separator가 등장하지 않거나 생략되었을 경우 배열은 원본 문자열을 유일한 원소로 가집니다. separator가 빈 문자열일 경우, str은 문자열의 모든 문자를 원소로 가지는 배열로 변환됩니다. separator가 원본 문자열의 처음이나 끝에 등장할 경우 반환되는 배열도 빈 문자열로 시작하거나 끝납니다. 그러므로 원본 문자열에 separator 하나만이 포함되어 있을 경우 빈 문자열 두 개를 원소로 가지는 배열이 반환됩니다.

평소에 잘 몰랐던 split의 심오한 철학이 많이 있으니 가서 확인해보는 것도 좋을 듯 하다.

암튼 첫 번째 결과물은 이렇다.

```typescript
const [initial, ...rest] = text.split(highlight)
<Text>
 {rest.reduce(
 (partialResult, current) =>
 [
 ...partialResult,
 <Text
 key={highlight + current}
 color={highlightColor}
 inlineBlock
 size={fontSize}
 whiteSpace="pre"
 >
 {highlight}
 </Text>,
 current,
 ],
 [initial],
 )}
</Text>
```

[reduce](https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce) 를 활용해서, 처리했다.

근데 어차피, map으로 돌면서 하는게 더 간단하지 않을까 하는 아이디어가 나왔다.

## 결과

```typescript
const initial = text.split(highlight)
<Text>
 {initial.map((normal, i) =>
 i > 0 ? (
 <>
 <Text
 key={highlight + i.toString()}
 color={highlightColor}
 inlineBlock
 size={fontSize}
 whiteSpace="pre"
 >
 {highlight}
 </Text>
 {normal}
 </>
 ) : (
 <>{normal}</>
 ),
 )}
</Text>
```

`i > 0` 을 처리한 이유는, 어차피 첫번째 엘리먼트는 무조건 하이라이트가 안되는 텍스트가 오기 때문이다! 첫단어가 일치하는 단어라면 ""가 올 것이고, 일치 하지 않는 단어라면 그 단어 그대로 올라오기 때문에 첫번째 단어는 별도처리를 하지 않아도 된다.

그리고 두번째 엘리먼트 부터 해당 text가 있어서 쪼개진 단어가 올것이기 때문에, 앞에 하이라이트 텍스트를 붙여주고, 그 다음 평범한 단어를 붙여주면 된다.

## 요구사항 한 엘리먼트안에서 특정한 키워드를 다른 색싱으로 바꿔서 출력하는 것이다. 아래 예시를 살펴보자 ### before ```jsx <Text>카카오 페이지 카카오 스토리 카카오톡</Text> ``` ### after ```jsx <Text> <Text color="blue">카카오 </Text>페이지 <Text color="bl...

yceffort

algorithm

Codility - Odd Occurrences in array

Codility - Cyclic Rotation

Codility - Binary Gap

알고리즘 - 연결 리스트

리액트 텍스트 하이라이트 만들기