아래 글은 오늘 강의를 들은 자료구조/알고리즘 수업의 내용과 내가 푼 방식, 강사님이 푼 방식이다. 문제의 저작권 때문에 간략하게 정리해서 올리는 점 참고해 주시기 바란다.
[1, 2차원 배열탐색과 시뮬레이션]
수열 축소
길이가 N인 수열이 주어지면 인접한 두 수의 차이를 이용해 길이가 N-1인 수열을 만드시오. 또한 매개변수 m이 주어지는데 M번의 길이축소작업을 한 결과를 구하라.
ex)
[1, 2, 3, 4] => [-1, -1, -1]
📌 내가 푼 방법
function solution(nums, m){
let answer = [];
for (let i = 0; i<m; i++)
{
answer= [];
for(let j = 0; j<nums.length-1; j++)
{
answer.push(nums[j+1] - nums[j]);
}
nums = answer;
}
return answer;
}
console.log(solution([5, 3, 7, 9, -2], 2));우선 m번의 작업을 해야하므로 m번만큼 돌아야하며, 길이보다 1개만큼 작은 횟수를 돌면서 뺀 값을 answer라는 배열에 집어 넣는다. 그 후에 for문이 다 돌아간 이후에, nums배열을 answer와 같은 값으로 만들어 다음 순회를 대비한다. 최종적으로 남은 값들이 answer에 담긴다.
📌 강사님 방법
function solution(nums, m) {
let answer;
let n = nums.length;
for(let i =0; i<m; i++) {
for(let j = 0; j<n-1-i; j++) {
nums[j] = nums[j+1] - nums[j];
}
}
answer = nums.slice(0, n-m);
return answer;
}
console.log(solution([5, 3, 7, 9, -2], 2));새로운 변수를 선언해서 메모리를 사용하는 것 대신에 기존의 nums배열을 이용하여 뺀 값을 그 순간의 index에 넣고, 순회를 다 돈 후에 새로운 for문을 시작할때 반복되는 수 만큼 원소의 개수가 줄으니 조건식에
j<n-1-i를 하고 전체 for문이 끝나면slice함수를 이용하여 n-m개 만큼 잘라서 answer에 넣는다.
가장 높은 증가수열
길이가 N인 수열이 주어지면 이 수열에서 연속된 부분 증가수열을 찾고, 증가수열의 첫항과 마지막항의 차가 최대가 되는 값을 반환하여라
ex) [10, 2, 3, 4, 3, 5, 6, 7]
--> 증가수열은 [2, 3, 4] 와 [3, 5, 6, 7]이며 최대가 되는 반환 값은 7-3=4이다.
📌 내가 푼 방법
function solution(nums) {
let answer = 0;
let len = nums.length;
let tempArr = []
for(let i = 0; i< len; i++)
{
if(tempArr.length === 0) {
tempArr.push(nums[i]);
} else {
if(nums[i] > tempArr[tempArr.length-1]) {
if(i === len-1) {
tempArr.push(nums[i]);
let height = tempArr[tempArr.length-1] - tempArr[0];
answer = Math.max(answer, height);
}
tempArr.push(nums[i]);
} else {
let height = tempArr[tempArr.length-1] - tempArr[0];
answer = Math.max(answer, height);
tempArr = [];
tempArr.push(nums[i]);
}
}
}
return answer;
}
console.log(solution([8, 12, 2, 3, 7, 6, 20, 3]));tempArr이라는 새로운 배열을 만들어 그곳에 배열의 값 하나를 집어 넣고 그 수와 비교하여 증가하는 경우 넣고 그렇지 않을경우 높이를 계산하여(tempArr의 맨 처음 값과 맨 마지막 값 빼서 계산!) answer에 저장 해둔다. 만약 계속 증가하다가 끝나는 경우 그 경우를 따로 고려하여 높이 계산을 해주고 answer에 최댓값을 저장하여 최종적으로 반환시킨다.
📌 강사님 방법
function solution(nums) {
let answer = 0;
let acc = 0;
for(let i = 1; i<nums.length; i++)
{
if(nums[i-1] < nums[i]) {
acc += nums[i] - nums[i-1];
} else {
answer = Math.max(answer, acc);
acc = 0;
}
}
answer = Math.max(answer, acc);
return answer;
}
console.log(solution([8, 12, 2, 3, 7, 6, 20, 3]));증가수열이 있다고 했을 때, 둘의 차를 누적하여 구한다. 증가수열에 같은 값이 있으면 증가 수열이 아니다!
둘의 차를 누적하여 구하면 훨씬 코드가 간결해져서 이 방법이 더 좋은 것 같다. 마지막의 값을 위해 for문이 끝난 후,answer = Math.max(answer, acc);를 넣어준다.
풀이를 보고 신박해서 재미있었다.
가장 긴 수열
길이가 N인 수열이 주어지면 이 수열에서 연속으로 증가하거나, 연속으로 작아지는 부분 수열 중 가장 길이가 긴 수열을 찾아라.
ex) [4, 5, 5, 6, 7, 8, 7, 6, 5, 4, 8] => [8, 7, 6, 5, 4] 의 수열이 가장 길기 때문에 이 길이인 5를 반환시키면 된다.
📌 내가 푼 방법
없음풀이를 강사님 수업시간에 지워버려서 기존에 남아있는 내가 푼 방법은 없는데 아마 풀다가 못풀었던걸로 기억한다.
푸는 방법 기억하기!!!
📌 강사님 방법
function solution(nums) {
let answer = 0;
let up = 1;
let down = 1;
let maxup = 0;
let maxdown = 0;
for(let i = 1; i<nums.length; i++) {
if(nums[i-1] < nums[i]) up++;
else {
maxup = Math.max(maxup, up);
up = 1;
}
if(nums[i-1] > nums[i]) down++;
else {
maxdown = Math.max(maxdown, down);
down = 1;
}
}
maxup = Math.max(maxup, up); // 맨 끝자리를 위해
maxdown = Math.max(maxdown, down); // 맨 끝자리를 위해
answer = Math.max(maxup, maxdown);
return answer;
}
console.log(solution([5, 2, 4, 7, 6, 3, 9, 10, 11]));증가 수열의 길이와 감소 수열의 길이를 동시에 세어서 증가하는 경우에 아닌 값을 만날때는
up=1을 해주고 마찬가지로 감소하는 경우에 아닌 값을 만날 때down=1을 해주어 각각 가장 큰 값들을 변수maxup, maxdown에 보관하고, for문을 나와서도 마지막 값이 계속 증가 혹은 감소하는 값들을 세어 준다. 최종적으로 answer에는 maxup과 maxdown중 가장 큰 값이 들어간다.
바이토닉 수열
바이토닉 수열은 수열이 증가했다가 감소하는 수열을 말하고, [4, 5, 7, 5, 4]는 바이토닉 수열이지만 [5, 6, 6, 5, 4]는 같은 값이 연속으로 있어서 바이토닉 수열이 아니다. 바이토닉 수열인 경우 YES를 아닌 경우 NO를 반환하여라.
📌 내가 푼 방법
function solution(nums) {
let answer = "YES";
let inc = 0, dec = 0;
let cnt = 0;
for(let i = 0; i< nums.length-1; i++) {
if(nums[i] < nums[i+1]) {
if(dec > 0) {
if(cnt === 0){
cnt++;
dec = 0;
} else {
return "NO";
}
} else {
inc++;
}
} else if(nums[i] > nums[i+1]) {
if(inc > 0) {
if(cnt === 0) {
cnt++;
inc = 0;
} else {
return "NO";
}
} else {
dec++;
}
} else {
return "NO";
}
}
if(cnt === 0) {
return "NO";
}
return answer;
}
console.log(solution([1, 2, 3, 4, 5, 3, 1]));무수히 많은 if와 else, 변수들을 이용해서 조건들을 다 고려하여 바이토닉 수열인 경우를 반환하였다. --> 노가다로 푼거 같아서 강사님 방법을 잘 참고해야겠다.
📌 강사님 방법
function solution(nums) {
let i =0;
while(i+1 < nums.length && nums[i] < nums[i+1]) i++;
if(i === 0 || i=== nums.length-1) {
return "NO";
}
else {
while(i+1 < nums.length && nums[i] > nums[i+1]){
i++;
}
if(i !== nums.length-1) {
return "NO";
} else {
return "YES";
}
}
}
console.log(solution([1, 2, 3, 4, 5, 3, 1]));while이용하여 nums[i]를 계속 증가시키면서 증가하는 부분을 찾는데 처음 증가하는 부분에서 i가 0 또는 배열의 끝까지 간경우 바이토닉 수열이 아니기 때문에 NO를 반환시키고, 줄어드는 부분을 i로 증가시키면서 최종적으로 i의 값을 검사하였을 때, 배열의 끝에 도달한 경우면 YES를 반환하며 아닌경우 NO를 반환한다.
확실히 이 풀이가 깔끔한 것 같다.
퀴즈도 이와 비슷한 문제가 나와서 이 방법으로 풀려다가 여러개의 바이토닉수열의 길이를 비교하여 길이가 제일 긴 바이토닉수열의 길이를 반환시켜야해서 포기하고 무수히 많은 if와 else로 해결하였다..
거리 두기
자리가 0과 1의 배열로 주어지며 0은 아직 예약이 안된 자석이고 1은 예약이 된 자석이다. 최대한 멀리 떨어져 앉을 수 있는 거리를 반환하여라.
📌 내가 푼 방법
function solution(nums) {
let answer = 0;
let maxFar = 0;
let leftFar = 0;
let rightFar = 0;
for(let i = 0; i<nums.length; i++) {
if(nums[i] === 1) {
continue;
}
else {
}
if(leftFar === 0) {
maxFar = Math.max(maxFar, rightFar);
} else if(rightFar === 0) {
maxFar = Math.max(maxFar, letfFar);
} else {
maxFar = Math.min(leftFar, rightFar);
}
leftFar = 0;
rightFar = 0;
}
return answer;
}
console.log(solution([0, 0, 0, 0, 1, 0, 0, 1, 0, 1]))풀다가 if와 else로 해결하려다가 고려해야할게 많아져서 나중에 풀어야겠다고 생각했는데 오늘 강사님 설명 전에 풀지 못한 문제이다.
강사님의 설명이 신박했는데 잘 흡수해야겠다.
📌 강사님 방법
function solution(nums) {
let answer = 0;
let d = 1000;
let t = 1000;
let tempArr = [];
for(let i = 0; i<nums.length; i++) {
if(nums[i] === 0) {
d++;
tempArr.push(d);
}
else {
tempArr.push(0);
d = 0;
}
}
for(let i = nums.length-1; i>=0; i--) {
if(nums[i] === 0) {
t++;
if(tempArr[i] > t) {
tempArr[i] = t;
}
} else {
tempArr[i] = 0;
t = 0;
}
}
answer= Math.max(...tempArr); // 스프레드 연산자 활용!!!
return answer;
}
console.log(solution([0, 0, 0, 0, 1, 0, 0, 1, 0, 1]))이런 방법으로 푼다는게 신기하였는데 오른쪽으로 한번 세고 왼쪽으로 한번 세는 것이 포인트다. 처음에 변수값을 높은 값으로 잡은후 nums배열과 똑같은 길이만큼의
tempArr배열을 만든다. 그후에 오른쪽으로 돌면서 자리가 차있지 않은 '0'인 경우엔 d의 값을 넣어주면서 값을 1씩 증가시키고 그렇지 않은 '1'을 만났을 때는 d를 0으로 만들어주고 값을 넣어준다.
한번 오른쪽으로 돌고 난후, 왼쪽으로 돌면서 마찬가지로 처음에 값이 큰 변수를 선언한 후, 그 값이 현재tempArr에 있는 값중 작은 값을tempArr배열 값으로 둔다. 이렇게 하여 최종적으로 돌고나면tempArr에는 값이 남는데 그 값이 최대한 멀리 떨어져 앉을 수 있는 거리이다.
tempArr이라는 배열의 원소 중 최댓값을 얻고 싶을 때,Math.max(tempArr)으론 얻지 못하고 스프레드 연산자를 이용한Math.max(...tempArr)을 이용해야한다!
2차원 배열 1의 개수
0과 1로 구성된 2차원 배열이 주어지고 1의 개수가 가장 작은 행 번호 부터 출력하되 같은 행이 여러개이면 행 번호가 작은 것 부터 출력하여라.
📌 내가 푼 방법
function solution(nums) {
let answer = [];
let tempMap = new Map();
let cnt = 0;
let minValue = 100;
let indexKey = 0;
for(let i = 0; i<nums.length; i++) {
for(let j = 0; j<nums[i].length; j++){
if(nums[i][j] === 1)
{
cnt++;
}
}
tempMap.set(i, cnt);
cnt = 0;
}
for(let i = 0; i<nums.length; i++) {
for(let [key, value] of tempMap) {
if(value < minValue) {
indexKey = key;
minValue = value;
}
}
answer.push(indexKey);
tempMap.delete(indexKey);
indexkey = 0;
minValue = 100;
}
return answer;
}
console.log(solution([[1, 0, 0, 1], [0, 0, 0, 1], [1, 1, 0, 1], [0, 1, 0, 1]]));map을 이용하여 각 인덱스마다 1의 갯수를 센 후, 다시 반복문을 돌면서 value의 값이 가장 큰 경우의 값과 인덱스를 찾아서 저장한 후 answer에 넣고 그 map의 키 값을 지워서 구하였다.
📌 강사님 방법
function solution(nums) {
let answer = nums.map((row, i) => ({i, cnt:row.reduce((a, b) => a+b, 0)}))
.sort((a, b)=>a.cnt - b.cnt)
.map(ob => ob.i);
return answer;
}
console.log(solution([[1, 0, 0, 1], [0, 0, 0, 1], [1, 1, 0, 1], [0, 1, 0, 1]]));JavaScript의 고차함수(함수를 인자로 받는 함수)의 map과 reduce 이용하여 인덱스를 key로, 1의 개수를 더한 값을 value로 만들어서 오름차순으로 정렬한 뒤 다시 map을 이용하여 인덱스 값을 순서대로 answer에 넣는다.
고차함수를 이용하면 이렇게 깔끔하게 한줄로 적을 수 있어서 js의 함수를 이용하여 알고리즘을 푸는 연습을 많이 해야겠다!
행과열의 최솟값
자연수로 채워져 잇는 2차원 배열이 주어지고, 그 배열의 행과열의 최솟값을 구하여라.
📌 내가 푼 방법
function solution(nums) {
let answer = [];
let tempSet = new Set();
let index = 0;
let minValue = 1000000;
for(let i = 0; i<nums.length; i++) {
for(let j=0; j<nums[i].length; j++) {
if(nums[i][j] < minValue) {
minValue = nums[i][j];
index = j;
}
}
for(let j = 0; j<nums.length; j++) {
if(nums[j][index] < minValue) {
minValue = nums[j][index];
}
}
tempSet.add(minValue);
index = 0;
minValue = 1000000;
}
answer = Array.from(tempSet);
return answer;
}
console.log(solution([[4, 6, 22, 1], [9, 3, 10, 12], [30, 7, 20, 2], [15, 8, 5, 13]]));문제를 이해할 때 처음엔 각 원소마다 최솟값을 구해야해서 1, 3, 2, 5가 나와야 하지 않나 생각을 했는데 그냥 각 행의 최솟값의 행과 열을 검사하여 그 값이 최솟값이면 answer에 넣으면 된다. 따라서 각 행의 최솟값을 찾으면 index값을 기억해 두었다가 index를 고정으로 한 열을 검사하여 최솟값을 구해
tempSet이라는 임시 집합 변수에 넣는데 이는 중복을 방지하기 위함이다. 최종적으로 이 집합을 다시 배열로 변환시켜서 출력하였다. 출력에 맞게하려면 최종적으로 오름차순으로 sort를 해주어야하는데 코드에는 적지 않았다.
📌 강사님 방법
function solution(nums) {
let answer = [];
let N = nums.length;
let minValue = 1000000;
let index = 0;
for(let i =0; i<N; i++) {
for(let j = 0; j<N; j++) {
if(nums[i][j] < minValue) {
minValue = nums[i][j]
index = j;
}
}
let k = 0;
for(k = 0; k<N; k++) {
if(nums[k][index] < minValue) {
break;
}
}
if(k == N) {
answer.push(minValue);
}
minValue = 1000000;
index = 0;
}
return answer.sort((a, b) => a-b);
}
console.log(solution([[4, 6, 22, 1], [9, 3, 10, 12], [30, 7, 20, 2], [15, 8, 5, 13]]));풀이가 거의 비슷하지만, 각 행의 최솟값을 찾은 후, 그 값이 열을 비교하였을 때, 최솟값이 아니면 break를 통해 for문을 생략하여 그 열의 길이만큼 돌지 못하였으므로, answer의 원소로 들어가지 못하지만 최솟값인 경우 for문을 계속 돌고 난 후 그 변수 k가 그 열의 길이만큼 돌았으므로 answer배열에 넣어준다. 마지막에 반환하기 전에 오름차순으로 정렬하기 위해
answer.sort((a,b) => a-b);를 해준다.
봉우리
지도 정보가 NxN 격자판에 주어지는데 각 격자에 높이가 써져있고, 주변 테두리의 높이는 0이다. 자신의 상하좌우 숫자보다 큰 경우 봉우리 이며 이 봉우리가 몇개 있는지 반환하여라.
📌 내가 푼 방법
function solution(nums) {
let answer = 0;
let N = nums.length;
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
for(let i = 0; i<N; i++) {
for(let j = 0; j<N; j++) {
let flag = true;
for(let k = 0; k<4; k++) {
let nx = i+dx[k];
let ny = j+dy[k];
if(nx >= 0 && nx<N && ny>=0 && ny<N && nums[i][j] <= nums[nx][ny]) {
flag = false;
break;
}
}
if(flag){
answer++;
}
}
}
return answer;
}
console.log(solution([[5, 3, 7, 2, 3], [3, 7, 1, 6, 1], [7, 2, 5, 3, 4], [4, 3, 6, 4, 1], [8, 7, 3, 5, 2]]));이 문제의 포인트는 상,하,좌,우 방향을 미리 배열로 선언을 해두고 for문이 4번 돌아가게 하며 각 방향들을 비교하면서 위치가 벗어나는 것은 어차피 주변 테두리의 높이가 0이므로 신경쓰지 않아도 된다.
주변 테두리를 벗어나지 않으면서 주변의 높이가 자신 보다 크거나 같은경우 봉우리가 될 수 없으므로flag=true라고 선언해둔 것을 false로 바꾸어 break를 해주고 반복문을 종료시킨다. flag가 그대로 true인 경우에는 봉우리가 되므로 answer에 카운팅을 해준다.
📌 강사님 방법
같다.
