코테/코드스테이츠[JS]
Toy 문제 27
문제 세로와 가로의 길이가 각각 M, N인 마을지도가 배열로 주어졌을 때, '1'은 주민이 있는 집을 의미하고 '0'은 주민이 없는 땅을 의미합니다. 이 마을은 소문이 시작되면 하루에 상하좌우 한 칸 바로 옆에 있는 집으로 퍼집니다. 특정 주민의 집 (R, C)으로부터 어떤 소문이 시작될 경우, 마을 전체로 소문이 퍼지는데 걸리는 시간(일)을 리턴해야 합니다. /* 1. 시작: (1, 2)에서 시작, 소문이 퍼진 곳을 x로 표기 [ '0101', '01x1', '0110', '0100', ] 2. 1일 뒤 [ '0101', '0xxx', '01x0', '0100', ] 3. 2일 뒤 [ '0x0x', '0xxx', '0xx0', '0100', ] 4. 3일 뒤: 소문이 전부 퍼짐 (끝) [ '0x0x',..
Toy 문제 26
문제 정수를 요소로 갖는 배열을 입력받아 다음의 조건을 만족하는 LSCS*를 리턴해야 합니다. LSCS: 주어진 배열의 연속된 부분 배열*의 합을 구한다고 할 때, 이 중 가장 큰 값 Advanced LSCS를 계산하는 효율적인 알고리즘(O(N))이 존재합니다. 수도코드(해석) 2중for문을 사용하여서 해결이 가능하지만, N의2승 시간복잡도가 나오기 때문에 for문을 한번만 사용하여야 합니다. 이러한 해결을 값에 대한 비교를 한번에 2번하여 해결 가능합니다. 배열의 처음부터 시작하여 i번 째 인자 하나하나를 더해주면서 Math.max 를 이용하여 큰 값을 result에 담아주는 방식 입니다. 두개의 변수를 만들어 주어서 arr[0]을 담아놓습니다. 반복문이 시작하면서 arr[i]을 더하여 비교해줍니다. ..
Toy 문제 25
문제 세로와 가로의 길이가 각각 M, N인 방의 지도가 2차원 배열로 주어졌을 때, 1은 장애물을 의미하고 0 이동이 가능한 통로를 의미합니다. 로봇은 지도 위를 일분에 한 칸씩 상하좌우로 이동할 수 있습니다. 로봇의 위치와 목표 지점이 함께 주어질 경우, 로봇이 목표 지점까지 도달하는 데 걸리는 최소 시간을 리턴해야 합니다. 주의사항 M, N은 20 이하의 자연수입니다. src, dst는 항상 로봇이 지나갈 수 있는 통로입니다. src에서 dst로 가는 경로가 항상 존재합니다. 입출력 예시 let room = [ [0, 0, 0, 0, 0, 0], [0, 1, 1, 0, 1, 0], [0, 1, 0, 0, 0, 0], [0, 0, 1, 1, 1, 0], [1, 0, 0, 0, 0, 0], ]; let ..
Toy 문제 24
문제 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 입력 인자 1 : arr number 타입을 요소로 갖는 배열 arr[i]는 0 이상의 정수 arr.length 100,000 이하 출력 number 타입을 요소로 갖는 배열을 리턴해야 합니다. 배열의 요소는 오름차순으로 정렬되어야 합니다. arr[i] [1, 3, 21] 수도코드(해석) 기수정렬을 사용하는 문제입니다. 기수정렬은 낮은 자리수 부터 비교하여 정렬해간다는 것을 기본 개념으로 하는 정렬 입니다. 시간 복잡도는 O(d * (n + b)) == O(dn)으로 매우 빠른편이지만 부동 소숫점 실수 같이 자릿수가 없는 경우 정렬할 수 없는 것이 단점 입니다. 여러 블로그를 참고했지만 이 이미지가 제일 이해하기 쉽고 간결해..
Toy 문제 23
문제 2차원 M x N 배열을 나선형(spiral)으로 순회해야 합니다. 입력 인자 1 : matrix 세로 길이(matrix.length)가 M, 가로 길이(matrix[i].length)가 N인 2차원 배열 matrix[i]는 string 타입을 요소로 갖는 배열 matrix[i][j].length는 1 출력 string 타입을 리턴해야 합니다. 주의사항 순회는 좌측 상단 (0,0)에서 시작합니다. 배열의 모든 요소를 순서대로 이어붙인 문자열을 리턴해야 합니다. 입출력 예시 let matrix = [ ['A', 'B', 'C'], ['D', 'E', 'F'], ['G', 'H', 'I'], ]; let output = spiralTraversal(matrix); console.log(output); ..
Toy 문제 22
문제 2차원 N x N 배열을 시계 방향으로 90도 회전시킨 배열을 리턴해야 합니다. Advanced 세로와 가로의 길이가 각각 M, N인 2차원 M X N 배열을 시계방향으로 90도씩 K번 회전시킨 배열을 리턴해 보세요. 회전수가 두 번째 입력으로 주어집니다. 출력 2차원 배열을 리턴해야 합니다. 입출력 예시 const matrix = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16], ]; console.log(matrix[0][0]); // --> 1 console.log(matrix[3][2]); // --> 15 const rotatedMatrix = rotateMatrix(matrix); console.log(rotatedMatr..
Toy 문제 21
문제 아래와 같은 과정을 거쳐 부등호 수(inequalityNumber)를 만들 수 있습니다. 최대 9개의 부등호()가 주어집니다. 부등호의 좌우에는 0부터 9사이의 숫자가 한 번씩만 들어가야 합니다. 부등호를 만족하는 숫자의 조합을 차례대로 이어 붙여 만든 정수를 부등호 수라고 한다. 부등호 기호들을 입력받아 부등호를 만족하는 최대 부등호 수와 최소 부등호 수의 차이를 리턴해야 합니다. 주의사항 첫 자리가 0인 경우도 부등호 수에 포함되어야 합니다. 모든 입력에 답은 항상 존재합니다. 입출력 예시 let output = inequalityNumber(''); console.log(output); // --> 876 (897 - 021) output = inequalityNumber('> '); c..
Toy 문제 20
문제 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 주의사항 병합 정렬을 구현해야 합니다. arr.sort 사용은 금지됩니다. 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다. let output = mergeSort([3, 1, 21]); console.log(output); // --> [1, 3, 21] 수도코드(해석) 합병 정렬 또는 병합 정렬(merge sort)은 O(log n) 비교기반 정렬 알고리즘입니다. 재귀 함수를 통해서 왼쪽 오른쪽을 계속해서 나누고, 값 비교를 통해서 result라는 변수에 순서대로 넣는방식으로 코드를 짰습니다. 설명은 주석에.. 하지만 테스트를 돌렸을 때 조금 시간이 걸린것을 느꼈고 레퍼런스보다 효율이 낮다는 것을 느꼈습니다. 병..
Toy 문제 19
문제 문자열을 입력받아 다음의 조건을 만족하는 LPS*를 찾아 그 길이를 리턴해야 합니다. LPS: 주어진 문자열의 가장 긴 접두어이자 접미어(Longest Prefix which is also Suffix) non-overlapping: 접두어와 접미어는 서로 겹치는 부분이 없어야 합니다. 다시 말해, prefix와 suffix는 문자열의 동일한 인덱스에 위치한 문자를 요소로 가지면 안 됩니다. let output = LPS('abbbcc'); console.log(output); // --> 0 output = LPS('aaaa'); console.log(output); // --> 2 // prefix: str.slice(0, 2) // suffix: str.slice(2) // non-overla..
Toy 문제 18
문제 길이가 m, n이고 오름차순으로 정렬되어 있는 자연수 배열들을 입력받아 전체 요소 중 k번째 요소를 리턴해야 합니다. Advanced 단순히 처음부터 끝까지 찾아보는 방법(O(K)) 대신 다른 방법(O(logK))을 탐구해 보세요. let arr1 = [1, 4, 8, 10]; let arr2 = [2, 3, 5, 9]; let result = getItemFromTwoSortedArrays(arr1, arr2, 6); console.log(result); // --> 8 수도코드(해석) 두 배열을 합쳐서(concat) sort하고 해당 k위치에 해당되는 값을 뽑으면 되지않을까 라는 생각에 좀 혼란에 빠졌는데 sort의 시간복잡도 O(log N) 이고 K위치를 바로 출력하는건 O(1) 이니까 시간복..