[TDL] 05/09 Today's-Done-List

- 자료구조 / 알고리즘 (Js ver.) 강의

강의로 스택 학습.
Hello Coding으로 재귀 및 호출 스택 학습.

---

17:50 오후 회고 스터디 (만족도 : 6)

계획을 달성하지 못했고, 생각만큼 집중이 좋지 않았기에 6점.

---

- 자료구조 / 알고리즘 (Js ver.) 강의

• 괄호 짝 찾기
  • 괄호의 짝 별 위치를 [시작, 끝]으로 찾아 2차원 배열 형태로 반환.
  • 위치 시작 값은 0으로 시작하며, 하나라도 짝이 맞지 않을 경우 빈 배열 반환
  • 예시)

입력 값	출력 값
(a*(b+c)+d)	[[3, 7],[0,10]]
(a*b+c)+d)+e)	[ ]

let result = [];
let stack = [];

for (let i = 0; i < str.length; i++) {
    if (str[i] == "(") {
        stack.push(i);
    } else if (str[i] == ")") {
        if (stack.length == 0) {
            return [];
        }

        result.push([stack.pop(), i]);
    }
}
if (!stack.length == 0) {
    return [];
}

return result;

• 적용할 방식
  • 괄호가 페어로 있는지, 있다면 "("를 stack에 push 하여 저장. 없다면 빈 배열 반환
  • 괄호 페어끼리 index 구해서 result에 push
• 해결 방법
  1. str의 length만큼 반복문을 돌려서, str안에 "("가 있다면 stack에 index를 저장해놓는다.
  2. 그리고, str안에 ")"가 있다면, stack에 저장해 놓은 "("의 index를 pop 해서 result에 [ "(" , ")" ]로 push
     만약에 stack의 length가 0이라면 stack에 저장해놓은 "("가 없는 것으로, 페어가 되지 않으니 빈 배열 반환.
  3. 페어가 맞다면, 반복문을 다 돌고 난 후에는 stack에 빈 객체가 반환되어야 하는데,
     그렇지 않을 경우에는 짝이 맞지 않은 것이기 때문에 빈 배열을 반환해서 오류? 상태라고 나타내 준다.

---

 

• 접시 꺼내기
  • 접시가 a, b, c, d 순으로 한쪽이 막혀 있는 세척기에 들어간다고 할 때,
    b, a, c, d 순으로 꺼내기 위해서는 push, push, pop, pop, push, pop, push, pop 순으로 꺼내면 된다.
    push/pop으로 접시가 꺼내져야 하는 동작을 계산하는 프로그램을 작성하시오.
    (접시 꺼내는 push/pop 연산 동작을 push -> 0, pop -> 1로 변환하여 배열로 반환)

입력 값	출력 값
bacd	[0, 0, 1, 1, 0, 1, 0, 1]

let result = [];
	let dish = str.split("").sort().join(""); // abcd
	let stack = [];
	let dish_index = 0;

	for (let i = 0; i < str.length; i++) {
		while (stack.length == 0 || stack[stack.length - 1] < str[i]) {
			stack.push(dish[dish_index++]);
			result.push(0);
		}

		if (stack.length == 0 || stack[stack.length - 1] > str[i]) {
			return [];
		} else {
			stack.pop();
			result.push(1);
		}
	}

	return result;

• 적용할 방식
  • 접시의 순서 : 현재는 내가 이해하기 쉽게 하나의 입력 값으로만 설정해놓았지만
    보통은 bacd인 경우에는 abcd로, asdfg인 경우에는 adfgs로 설정해서 비교해야 함.
  • 접시를 꺼내야 할 때 즉, 세척기 안에 있는 알파벳이 작을 때 push
  • stack 맨 위의 접시와 비교해서 빈 배열을 반환할 것인지, pop을 할 것인지.
• 해결 방법
  1. 입력받은 값에 split(""). sort(). join("")을 하여, 알파벳을 순서대로 정렬
  2. stack의 length가 0이거나 stack이 비교해야 될 대상 str[i]보다 작다면 반복문을 돌린다.
     ==> stack이 0이라면, 나중에 꺼낼 대상이 없으니 push를 해줘서 비교해야 함.
     ==> abcd 순으로 점점 커지는 건데 만약 str[0]가 b일 경우 ab만 세척기 안으로 들어올 때까지 push
     ==> 만약 str[i]가 d일 경우에는 abcd 모두 다 세척기 안으로 들어올 때까지 push를 해준다.
  3. dish의 index를 증가시키며, 하나하나 push를 해주며, push가 일어날 때마다 result에 0을 넣어준다.
  4. 이렇게 반복문을 다 돌았다면, 보통 자기보다 같거나 큰 값을 만나게 되는데
     만약 stack의 length가 0이거나, str[i]이 가장 끝 데이터보다 작을 경우에는 정상이 아니므로 빈 배열 반환.
     그렇지 않다면 세척기에 넣어야 하는 알맞은 알파벳이기에
     stack의 최상단에 있는 알파벳을 pop을 해주고, result에 1을 넣어준다.
     • 만약 dabc순으로 꺼내려면 dabc 또한 abcd를 비교하면서 세척기에 넣어야 하는데,
       처음 알파벳이 d니까 abcd를 다 stack에 push 해서 [a, b, c, d] d를 pop 한다.
       그 뒤에 a를 꺼내야 하는데, c와 b가 가로막고 있기 때문에 pop을 하지 못한 채로 false 되어 빈 배열 반환.

 

---

22:50 저녁 회고 스터디 (만족도 : 7)

[○]  1. 스택 강의 + hello coding 알고리즘 책
[○]  2. 스택 알고리즘 3문제
[ Χ ] 3. leetcode에서 배열, 연결 리스트 관련 문제 풀어보기

---

알고리즘 문제 풀 때, 아직 어떻게 접근해야 할지 감이 잘 안 잡혀서 기본적인 문제들도 생각보다 오래 걸린다ㅠ
내가 똑똑한 사람이 아니니깐 문제를 많이 풀어보는 수밖에 없을 것 같다ㅠㅠㅠ 방댕이 싸움이다...

---

[ 출처, 참고 : 제로베이스 프런트엔드 스쿨 ]