String과 Array의 전환

1. 스프레드 연산자 사용하기

• 상황 예시
  문제에서 초기 파라미터로 문자열이 넘어왔는데, for문보다는 forEach로 코드를 작성하고 싶을 때 유용함.

let my_str = 'hello';
console.log([...my_str]);
//결과: > Array ["h", "e", "l", "l", "o"]

2. Array.prototype.join()과 String.prototype.split() 사용하기

• 상황 예시
  문자열을 거꾸로 뒤집고 싶은데 String.prototype에는 Array처럼 reverse 메소드가 없음. 그래서 이 때 배열로 전환해서 뒤집고 다시 문자열로 바꿔줄 때 유용

💡String.prototype.split()

split() 메서드는 String 객체를 지정한 구분자를 이용하여 여러 개의 문자열로 나눠서 그걸 담은 Array로 반환합니다.

💡Array.prototype.join()

join() 메서드는 배열의 모든 요소를 연결해 하나의 문자열로 만듭니다.
이 때, 추가적으로 separator라는 매개변수를 넘길 수 있는데, 넘겨주면 하나의 문자열로 이어붙일 때 해당 separator를 끼워넣으면서 붙여진다.

• Array.prototype.join() 사용 예시

const elements = ['Fire', 'Air', 'Water'];
console.log(elements.join('-'));
// expected output: "Fire-Air-Water"

• 문자열을 뒤집고 싶을 때는 위의 팁을 이용해서 다음과 같이 한 줄의 함수로 뒤집을 수 있다.
  (split("") → reverse() → join(""))

function getReverseStr(str) {
    return str.split("").reverse().join("");
}

N차원 Array 선언하기

JavaScript는 다른 언어와 다르게 2차원 배열 이상의 개념이 존재하지 않아서 처음부터 한번에 const arr = [][];와 같은 식으로 2차원으로 초기화하거나 선언할 수 없다. (물론 "한 번에" 2차원 배열을 만들어낼 수 없는 것이지 아예 2차원 배열을 사용할 수 없는 것은 아님.)

우선 2차원 배열을 선언 및 초기화 하는 방법을 알아보자.

1. Array.from() 활용하기

Array.from() 메서드는 유사 배열 객체(array-like object)나 반복 가능한 객체(iterable object)를 얕게 복사해 새로운 Array 객체를 만듭니다.

Parameter

• arrayLike: 배열로 변환하고자 하는 유사 배열 객체나 반복 가능한 객체
• mapFn: 배열의 모든 요소에 대해 호출할 맵핑 함수

/* 사용 예시 */

console.log(Array.from('foo'));
// Expected output: Array ["f", "o", "o"]

console.log(Array.from([1, 2, 3], x => x + x));
// Expected output: Array [2, 4, 6]

만약 [4, 5]짜리 2차원 배열을 만들고 싶다면

1. 길이 4짜리인 1차원 배열 먼저 초기화하고,
2. 1차원 배열 각각의 원소들을 길이 5짜리인 1차원 배열들로 바꿔서 매핑해주면 된다.

Array.from(Array(4), () => Array(5));

그런데 여기에서 모두 다 0으로 초기화하고 싶다면 Array.prototype.fill() 메소드를 체이닝 시키면 된다.

Array.from(Array(4), () => Array(5).fill(0));

문자열의 길이 관련

1. String.prototype.slice() 활용하기

- 상황 예시

`new_id`의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.

이 때는 굳이 if(new_id.length >= 16) 어쩌구저쩌구 하지 말고, 그냥 어차피 최대 15개까지만 문자를 가져가면 되는거니까 new_id.slice(0, 15)로 해도 상관이 없다! (15가 해당 문자열의 길이보다 넘쳐도 상관 없음)

깔끔한 코드를 쓰자!

String에서 Number로 전환하는 방법

String에서 Number로 전환하는 방법에는 다음과 같이 세 가지가 존재한다.

1. parseInt()
2. Math.floor()
3. ~~ 연산자

그런데, 코딩테스트에서 시간 초과를 최대한 방지하고 싶다면 ~~ 연산자를 쓰는 것이 매우매우 유리하다. 세 가지 방법 중에서 성능이 제일 좋고 시간이 적게 들기 때문!!
(참고: https://developer-alle.tistory.com/393)

소숫점 빨리 버리기

Math.floor() 보다는 우측 시프트 연산자를 0만큼 이동하는 것을 사용하는 것이 더 좋다.
ex) (5 / 2) >> 0

>> 는 비트연산자인데 자바스크립트 내장 객체 Math.floor() 를 이용하는 것 보다 더 빠른 성능을 보입니다. 
우측 시프트 연산자(>>)를 0만큼 이동하면 이는 소수점 아래를 버리는 것과 동일한 기능을 합니다.

문자열 원하는 부분끼리 조립하기

1. String.prototype.substring() 활용하기

사용방법

str.substring(indexStart[, indexEnd])

인자값

• indexStart: 반환문자열의 시작 인덱스
• indexEnd: 옵션. 반환문자열의 마지막 인덱스 (포함하지 않음.)

반환값

• 기존문자열의 부분 문자열을 반환합니다.

2. String.prototype.slice() 활용하기

사용방법은 String.prototype.substring()과 같다.

원하는 요소의 개수 세기

1. Array.prototype.filter() 활용하기

해당 방법은 원하는 요소 A의 개수만! 세는 방법이다.

const arr = [1, 2, 3, 1, 1, 1, 3, 4, 5];

//만약 1의 개수를 세고 싶다면,
let cnt = arr.filter(elem => elem === 1).length;

2. 내장 객체 Map을 활용한 방법

이 방법은 배열에 등장하는 모든 요소에 대해서 각각의 개수를 모두 기록하는 방법이다. (위의 방법이랑은 다르다)

• Map.prototype.set() 메소드와 Map.prototype.get() 메소드를 활용한다.
• Map.prototype.get() 메소드를 사용할 때 존재하지 않는 key값에 대한 리턴값은 undefined이고, 이를 원하는 값과 || 연산을 통해서 새로운 key 값을 만들면서 value를 설정해 줄 수 있다.

만약 0부터 카운트하고 싶다면 아래 코드를 참고하자.

const arr = [1, 2, 3, 1, 1, 1, 3, 4, 5];

var map = new Map();
arr.forEach(num => {
  map.set(num, (map.get(num) || 0) + 1);
});

'하나라도 만족하면'을 만났을 때

1. Array.prototype.some()을 활용한 방법

• 상황 예시

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

💡Array.prototype.some()

some() 메서드는 배열 안의 어떤 요소라도 주어진 판별 함수를 적어도 하나라도 통과하는지 테스트합니다. 만약 배열에서 주어진 함수가 true을 반환하면 true를 반환합니다. 그렇지 않으면 false를 반환합니다. 이 메서드는 배열을 변경하지 않습니다.

정렬하기

1. Array.prototype.sort()을 활용한 방법

JavaScript에서 Array.prototype.sort() 메소드를 사용할 것이라면 자신이 원하는 대로 정렬하기 위해서는 반드시 직접 compareFunc를 구현해야한다는 함정이 숨어있다.

sort 메소드에 따로 compareFunc를전달해주지 않으면 배열의 모든 요소를 문자열로 변환하고 유니 코드 코드 포인트 순서로 문자열을 비교하여 정렬된다. 그래서 만약에 1, 8, 2, 15]라는 배열이 있다고 해도 아무런 compareFunction 없이 sort()를 쓰게 된다면 문자 순서대로 [1, 15, 2, 8] 나오게 될 것이다.

따라서, 우리가 원하는 대로! 숫자의 정렬을 하기 위해서는 적절한 compareFunc를 넘겨주어야 하는데, 오름차순으로 정렬하기 원하는 경우 (a, b) => a - b라는 화살표함수를, 내림차순으로 정렬하기 원하는 경우 (a, b) => b - a라는 화살표함수를 전달해주면 된다.

그냥 a, b라고 하면 헷갈리므로 다음과 같이 이해하면 쉽겠다!
우선 Array.prototype.sort() 메소드가 어떤 원리로 돌아가는지 살펴보도록 하자.

sort 메소드는 compareFunc가 리턴하는 값에 따라 정렬되는 방식이 다르다.

1. 0을 리턴한 경우 → 아무런 변동 X
2. 양수를 리턴한 경우 → 오름차순
3. 음수를 리턴한 경우 → 내림차순

다음의 코드를 보자. (참고한 블로그: https://rkdvnfma90.tistory.com/232)

const arr = [1, 2, 3];
arr.sort((a, b) => b - a);

이렇게 있을 때, 파라미터 a, b에 각각 1, 2가 들어오겠다고 생각을 하겠지만, 사실은 2, 1이 들어온다. 그렇기 때문에 이 부분이 헷갈린다면 다음과 같이 이해하면 되겠다.

arr.sort((next, prev) => prev - next);

최대공약수(GCD) 구하기

1. 유클리드 호제법을 이용한 구현

💡 유클리드 호제법이란
두 수 A, B에 대해서 A > B 이고, A를 B로 나눈 나머지를 r이라고 할 때, GCD(A, B) == GCD(B, r)과 같다는 원리이다. (r이 0이라면 그 때의 B가 최대공약수이다.)

코드를 한 줄로 작성하면 다음과 같다.

const GCD = (num1, num2) => (num2 > 0 ? GCD(num2, num1 % num2) : num1);

여러 줄로 작성하면 다음과 같다.

function GCD(num1, num2) {
  if(num2 === 0) return num1;
  else return GCD(num2, num1 % num2);
}

주의할 점은, GCD 함수를 사용할 때 num1 > num2가 보장되도록 처리하여 넣어주어야 한다.

배열에서 중복 제거하기

1. 내장 객체 Set 사용하기

Set을 생성할 때, 생성자에 배열을 전달할 수 있으며, 이때, 모든 중복이 제거된 set 인스턴스가 생성된다.
이 set을 다시 배열로 변환하여 반환하고 싶다면, 다음과 같이 Spread Operation을 통하여 다시 배열로 변환할 수 있다.

const duplicatedArr = [1, 2, 1, 2, 3, 4, 5];

const mySet = new Set(duplicatedArr);
const uniqueArr = [...mySet]; // [1, 2, 3, 4, 5];

2. Array.prototype.from() 사용하기

const duplicatedArr = [1, 2, 1, 2, 3, 4, 5];

const mySet = new Set(duplicatedArr);
const uniqueArr = Array.from(mySet);

💡 Set 이해하기

Set는 순서가 없는, 중복되지 않은 데이터의 집합이다. Array와의 차이점을 이해하는 것이 무엇보다 중요하다.

배열(Array)는 데이터를 순서있게 저장한다. 그래서 인덱스(index)를 통해서 특정 위치에 저장되어 있는 데이터에 접근이 가능하다. 그리고 배열에는 동일한 값을 여러 번 저장할 수 있다. 값이 동일하더라도 인덱스가 틀리기 때문에 데이터의 중복이 문제되지 않는다.

반면에 Set는 얼핏 보기에는 배열과 비슷해보일 수 있지만 사실 결이 아주 다른 자료구조이다. 우선 세트는 데이터를 순서없이 저장한다. 따라서 배열처럼 인덱스를 통해서 접근할 수가 없다.

그리고 세트는 중복된 데이터를 허용하지 않는다. 즉, 기존에 세트에 있는 값을 또 추가해봤자 아무런 일도 생기지 않는다.

DFS, BFS

문제 유형에 따른 BFS, DFS 선택

문제에 따라서 DFS가 더 어울리는 유형이 있고, BFS가 더 어울리는 문제가 있다.
(출처: tsi0521님의 Velog)

• 그래프의 모든 정점을 방문해야 하는 문제
  → DFS를 쓰든, BFS를 쓰든 상관 없음.
• 검색 대상 그래프가 크거나 경로의 특징을 저장해둬야 하는 문제
  → DFS를 사용한다. (BFS는 경로의 특징을 가지지 못함)
• 검색 대상의 규모가 크지 않고 최단거리를 구해야 하는 문제
  → BFS를 사용한다. 왜냐하면 DFS로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, BFS로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리이기 때문.

구현상의 특징

• DFS(Depth-First Search / 깊이 우선 탐색)
  → 한 정점 깊이의 끝까지 탐색하므로 주로 재귀함수와 함께 사용한다.
• BFS(Breadth-First Search / 너비 우선 탐색)
  → 가까운 정점부터 탐색하므로 주로 Queue와 함께 사용한다.

요령

• Queue에서 맨 앞 원소를 빼는 작업을 Array.prototype.shift()로 하다가 시간 초과가 나는 것 같다면, 이 문제에서 해결한 방식처럼 queueIdx를 따로 둬서 실제로 shift하진 않지만 shift 한 효과를 내도록 해보자.

동적계획법(Dynamic Programming)

눈치 채기

• 보통 DP 문제에서 연산의 결과가 엄청나게 커지는 경우가 종종 있어서, 문제 조건 중에 어떤 수를 나눈 나머지를 리턴하라 하는 경우면 DP를 적용할 수 있는 가능성이 높다.
  ex) 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.
• 재귀를 쓰면 좋겠다는 느낌 + 근데 문제의 최대 입력을 봤을 때 그냥 재귀나 반복을 했을 때 분명 터지겠다는 느낌 + 뭔가 결과가 점점 누적되고 이전거를 그대로 사용해서 지금꺼를 업데이트 하면 되겠다는 느낌
• 처음부터 끝까지 경로를 가는데, 우하향 방향으로 제한하거나 어찌됐건 가는 방향을 좀 정해준다? 이러면 살짝 DP 느낌

깊은 복사

특이한 형태로 들어오는 배열의 형태를 그대로 가져오면서 내가 원하는 값들로 초기화해주고 싶을 때, 얕은 복사를 하게 되면 원본 배열도 바뀌어버린다. 이 때 다음과 같은 방법들을 사용하면 깊은 복사가 되어 원본이 변경되지 않는다.

1. JSON.stringify(), JSON.parse() 사용하기

• 상황 예시
  다음과 같이 특이한 배열이 들어와서 Dynamic Programming을 할 때 메모이제이션용 배열로 똑같은 형태로 만들어 초기화하고 싶을 때.

//피라미드 형태의 삼각형을 표현하는 특이한 모양의 배열
const triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]];

//저 형태를 그대로 따서 0으로 초기화하면서, 원본 배열은 변경하고 싶지 않을 때
const cache = JSON.parse(JSON.stringify(triangle));
cache.forEach(arr => {
  for(let i=0; i < arr.length; i++) arr[i] = 0;
});

console.log(triangle); // [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
console.log(cache); // [[0], [0, 0], [0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0, 0]]

문제 풀이 요령

답변을 먼저 제출하여, 효율성 테스트를 채점하는지 우선 확인합니다.
효율성을 채점하지 않는다면, 대부분 알고리즘이 10초이내에 돌아가게 만들면 됩니다.
그 다음, 문제의 제한 사항을 확인합니다.
여기서에서 배열을 총 길이들을 확인하여, 최대 가능한 연산횟수를 대충 유추할 수 있습니다.

예를 들어 [이모티콘 할인행사] 문제에서 users가 최대 100, emoticons가 최대 7의 길이를 갖습니다.
또한, 문제에서 할인율은 [10, 20, 30, 40] 4종류의 할인율만 가진다고 하였습니다.
대충 가질 수 있는 할인율을 계산해보자면, 약 16000(4의 7승)가지가 될겁니다.
그럼, 100 * 7 * 16000 = 1100만번의 연산을 수행합니다.
여기서 보조 연산이 들어가거나, 언어의 속도에 따라 추가적인 시간 소요가 일어납니다.
많은 연산이기는 하지만, 무지성으로 탐색해도, 1억번을 넘지 않으므로, 충분히 시간안에 통과가 가능합니다.
연산횟수가 1억 단위가 넘어가면, 시간 초과가 뜰가능성이 존재한다는 사실을 늘 염두하셔야 합니다.
이런 팁을 알면, 실제 코딩테스트를 풀 때, 사용할 알고리즘을 빠르게 유추해볼 수 있겠습니다.
(출처: 전현서님)