아래 글은 오늘 강의를 들은 자료구조/알고리즘 수업의 내용과 내가 푼 방식, 강사님이 푼 방식이다. 문제의 저작권 때문에 간략하게 정리해서 올리는 점 참고해 주시기 바란다.
[스택, 큐, 데크 자료구조]
올바른 괄호
괄호가 입력되고, 괄호의 쌍이 올바르게 위치하는 것이면 "YES", 그렇지 않으면 "NO"를 출력하여라.
📌 내가 푼 방법
function solution(s) {
let answer = "YES";
let tempArr = [];
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
tempArr.push('(');
} else {
if (tempArr.length === 0) {
return "NO";
}
tempArr.pop();
}
}
if (tempArr.length > 0) {
answer = "NO";
}
return answer;
}
const s = "(()(())))(()";
console.log(solution(s));문자가 '('이면 그냥 배열에 넣고 배열 길이가 0인 상태에서 pop을 하려고 하면 쌍이 맞지 않으므로 바로 return NO를 해주고 전체 반복문이 끝나고 나서 임시 배열의 길이가 0이면 YES를 그렇지 않으면 NO를 반환시킨다.
📌 강사님 방법
풀이가 크게 다르지 않다.문제에 괄호 있으면 70~80퍼센트 스택문제!, 이번주 위클리 테스트에 문자열 압축 풀 때 스택사용해서 푸는 문제를 낼 것임.
cnt라는 변수를 사용하여(를 만나면 +1)를 만나면 -1을 해주어서 cnt가 0 이면 올바른 괄호(그러나 cnt가 중간에 음수가 되면 올바른 괄호가 아님!)
괄호문자제거
입력된 문자열에서 소괄호 () 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하여라.
📌 내가 푼 방법
function solution(s) {
let answer = 0;
let tempArr = [];
for (let i = 0; i < s.length; i++) {
if (s[i] === ')') {
let n;
while (n !== '(') {
n = tempArr.pop();
}
} else {
tempArr.push(s[i]);
}
}
return answer = tempArr.join("");
}
const s = "(A(BC)D)EF(G(H)(IJ)K)LM(N)";
console.log(solution(s));문자 ) 을 만나면 ( 을 만날 때까지 tempArr에서 문자를 제거해준다. (스택을 이용하라!)
📌 강사님 방법
풀이가 크게 다르지 않다.후위식 연산(postfix)
후위연산식의 결과값을 출력하라.
📌 내가 푼 방법
function solution(s) {
let answer = 0;
let tempArr = [];
for (let i = 0; i < s.length; i++) {
if (isNaN(parseInt(s[i], 10))) {
let first;
let second;
switch (s[i]) {
case '+':
second = tempArr.pop();
first = tempArr.pop();
tempArr.push(parseInt(first, 10) + parseInt(second, 10));
break;
case '-':
second = tempArr.pop();
first = tempArr.pop();
tempArr.push(parseInt(first, 10) - parseInt(second, 10));
break;
case '*':
second = tempArr.pop();
first = tempArr.pop();
tempArr.push(parseInt(first, 10) * parseInt(second, 10));
break;
case '/':
second = tempArr.pop();
first = tempArr.pop();
tempArr.push(parseInt(first, 10) / parseInt(second, 10));
break;
default:
return "Wrong input";
}
} else {
tempArr.push(s[i]);
}
}
answer = tempArr[0];
return answer;
}
const s = "352+*9-";
console.log(solution(s));숫자가 아닌 연산자가 나왔을 경우 그 연산자를 확인하여 switch case에 따라 나누어 계산 후 다시 stack에 넣어준다.
📌 강사님 방법
후위식 연산과 더불어 식을 이진트리로 그리는 방법과 전위, 중위, 후위식으로 만드는 방법에 대해서
강의를 하셨다.
function solution(s) {
let answer = 0;
let stack = [];
for (let x of s) {
if(!isNaN(x)) stack.push(Number(x));
else {
let rt = stack.pop();
let lt = stack.pop();
if(x==='+') stack.push(lt+rt);
else if(x==='-') stack.push(lt-rt);
else if(x==='*') stack.push(lt*rt);
else if(x==='/') stack.push(lt/rt);
}
}
answer = stack[0];
return answer;
}
const s = "232*+63-4*+";
console.log(solution(s));
전위: 부-> 왼-> 오 (1, 2, 4, 5, 3, 6 ,7)
중위: 왼 -> 부 ->오 (4, 2, 5, 1, 6, 3, 7)
후위: 왼 -> 오 -> 부 (4, 5, 2, 6, 7, 3, 1)
연속된 문자 지우기
문자열이 주어지면 연속된 문자를 제거하고 최종적으로 남는 문자열을 출력하라.
📌 내가 푼 방법
function solution(s) {
let answer;
let tempArr = [];
tempArr.push(s[0]);
for (let i = 1; i < s.length; i++) {
if (tempArr.length === 0) {
tempArr.push(s[i])
} else if (s[i] === tempArr[tempArr.length - 1]) {
tempArr.pop();
} else {
tempArr.push(s[i]);
}
}
answer = tempArr.join("");
return answer;
}
const s = "acbbcaa";
console.log(solution(s));문자 하나를 처음에 넣어두고 다음 문자를 넣으면서 배열의 마지막 원소와 현재 넣는 원소가 같으면 배열 안의 값을 하나 빼주고 넣고를 반복하여 최종 결과 값을 join함수로 묶어서 출력한다.
📌 강사님 방법
풀이가 거의 같다.공주 구하기
요세푸스 문제
📌 내가 푼 방법
function solution(N, K) {
let answer = [];
let repush;
for (let i = 0; i < N; i++) {
answer.push(i + 1);
}
while (answer.length !== 1) {
for (let i = 0; i < K - 1; i++) {
repush = answer.shift();
answer.push(repush);
}
answer.shift();
}
return answer[0];
}
console.log(solution(8, 3));앞의 원소중 K번째에 해당하는 원소가 아닌 경우 앞에서 뺏다가 다시 뒤에 넣어 배열의 길이를 유지시키면서 돌린다. 최종적으로 배열의 개수가 1이 남았을 때, 그것이 마지막으로 남아있는 사람이다.
📌 강사님 방법
function solution(n, k) {
let answer;
let queue = Array.from({
length: n
}, (v, i) => i + 1);
while (queue.length) {
for (let i = 1; i < k; i++) {
queue.push(queue.shift());
}
queue.shift();
if (queue.length === 1) answer = queue.shift();
}
return answer;
}
console.log(solution(8, 3));풀이가 비슷하다.
스택에 비해 큐로 푸는 문제는 새발의 피다.(다 BFS이런걸로 품)
교육과정 설계
필수과목이 CBA로 주어질 때, 총 과목 플랜을 무조건 C->B->A순으로 들어야한다. 이러한 조건을 만족하면 YES 그렇지 않으면 NO를 출력하여라
📌 내가 푼 방법
function solution(need, plan) {
let answer;
let tempArr = []
for (let i = 0; i < need.length; i++) {
tempArr.push(need[i]);
}
for (let i = plan.length - 1; i >= 0; i--) {
if (tempArr.length === 0) {
return "YES";
} else if (tempArr[tempArr.length - 1] === plan[i]) {
tempArr.pop();
} else {
continue;
}
}
if (tempArr.length === 0) {
answer = "YES";
} else {
answer = "NO";
}
return answer;
}
console.log(solution("CBA", "CBDBAGE"));필수과목을 배열에 넣어두고 plan을 거꾸로 돌면서 배열의 마지막 값과 돌면서 확인한 값이 같은경우 배열의 값을 지우고 최종적으로 배열의 길이가 0이 되면 정상적으로 plan을 설계했는 지 확인한다.
📌 강사님 방법
function solution(need, plan) {
let answer = "YES";
let queue = need.split("");
for (let x of plan) {
if (queue.includes(x)) {
if (x !== queue.shift()) return "NO";
}
}
if (queue.length > 0) return "NO";
return answer;
}
console.log(solution("CBA", "CABFGE"));
shift를 이용하여 for문을 정상적으로 돌리면서 includes를 사용하여 값이 안에있고, 맞는 지 확인한다. 안에 없으면 return "NO" 반환.
최소 매출
N일 동안의 매출 기록을 배열로 주고 연속된 K일 동안의 최소 매출액을 차례로 구하여라
ex)
[11, 12, 15, 20, 25, 10, 20, 13, 15, 19], 3 이렇게 주어지면
처음 11, 12 15중 최소 매출액은 11이며 이를 배열이 끝날 때 까지 반복!
📌 내가 푼 방법
function solution(nums, k) {
let answer = [];
let N = nums.length;
let minValue = 100000;
for (let i = 0; i <= N - k; i++) {
let tempArr = nums.slice(i, i + 3);
minValue = Math.min(...tempArr);
answer.push(minValue);
}
return answer;
}
const nums = [11, 12, 15, 20, 25, 10, 20, 13, 15, 19];
const k = 3;
console.log(solution(nums, k));slice로 잘라서 3개씩 배열을 나눈 후 그 최솟값들을 모아서 answer배열에 저장한다. => O(n^2) (slice O(n) 이어서)
시간복잡도 고려를 해야한다.
📌 강사님 방법
function solution(nums, k) {
let answer = [];
let deque = [];
for (let i = 0; i < k - 1; i++) {
while (deque.length > 0 && deque[deque.length - 1][0] > nums[i]) {
deque.pop();
}
deque.push([nums[i], i]);
}
for (let i = k - 1; i < nums.length; i++) {
while (deque.length > 0 && deque[deque.length - 1][0] > nums[i]) {
deque.pop();
}
deque.push([nums[i], i]);
answer.push(deque[0][0]);
if (deque[0][1] === i - k + 1) deque.shift();
}
return answer;
}
const nums = [11, 12, 15, 20, 25, 10, 20, 13, 15, 19];
const k = 3;
console.log(solution(nums, k));for문을 우선 한번 돌아서 deque에 넣을 값들을 찾고 그 이후로 끝까지 돌면서 deque에 있는 값들을 뽑아내면서 최소 매출액을 찾는다. 다시 한번 해보면 좋을 것 같다.
그런데 shift()함수에 대해서 알아보던중 shift함수또한 O(n)의 시간복잡도를 갖고 있어서 최종적으로 O(n^2)이 되는 것이 아닌가 질문하였는데 크게 신경 안써도 된다고 하셨다.
알고리즘 강의가 끝나고 간단하게 재귀에 대한 교육을 하셨는데
const n = 3;
function DFS(v) {
if (v === 0) return;
else {
DFS(v-1);
console.log(v);
}
}
DFS(n);다음과 같은 코드가 있을 때 재귀의 if~else 구조에 대해서 잘 알아두라고 하셨고, 재귀함수의 호출이 스택형태로 쌓이기 때문에 가장 마지막으로 호출된 재귀함수의 console.log가 먼저 찍히고 가장 처음으로 호출한 재귀함수의 console.log가 마지막으로 찍힌다는 것이었다.
