6-19 TIL

Algorithm

괄호 회전하기

function solution(s) { 
    let count = 0
    for(let i=0; i<=s.length-1;i++) {
        let stack = []
        let str = ""
        str += s.slice(i)
        if(i>0) str += s.slice(0,i)
        stack.push(str[0])
        for(let j=1; j<=str.length-1;j++){
            stack.push(str[j])
            if(str[j]===")"){
                if(stack[stack.length-2]!=="(") break;
                else {
                    stack.pop()
                    stack.pop()
                }

            }
            if(str[j]==="}"){
                if(stack[stack.length-2]!=="{") break;
                else {
                    stack.pop()
                    stack.pop()
                }
            }
            if(str[j]==="]"){
                if(stack[stack.length-2]!=="[") break;
                else {
                    stack.pop()
                    stack.pop()
                }
            }
        }
        if(stack.length===0) {
            count++
        }
    }
    return count;
}

조금 지저분한 코드 같긴 하면서도 이해가 되긴 되는데 깔끔한 코드로 좀 더 활용하는 방법을 써야할 것 같다. 객체를 활용했으면 더 좋을 코드일 듯하다

• 괄호 닫힘을 확인할 stack과 회전한 문자열을 둘 str을 선언하고 회전한 문자열을 구하는 건 slice를 사용한다.
• stack에 미리 첫번째 괄호를 집어 넣은뒤 반복문을 돌려 닫히는 괄호가 나온지 확인한다.
• 만약 닫힌 괄호가 나왔을 때 바로 직전 괄호가 해당 괄호의 열린 괄호가 아니라면 반복문을 바로 종료시킨다
• 아니라면 pop()을 2번 발생시켜 한쌍의 괄호를 제거한다
• 검사가 끝나고 모든 괄호가 닫혀있을 경우 stack의 원소가 존재하지 않기 때문에 length가 0일때 count를 올려준다

function solution(s) {
    if(s.length % 2 === 1) return 0;

    let answer = 0;
    const mapping = { "}" : "{", "]" : "[", ")" : "("};

    for(let i = 0; i < s.length; i++) {
        const stack = [];
        const rotate = s.slice(i) + s.slice(0, i);
        let flag = true;

        for(let j = 0; j < s.length; j++) {
            if(rotate[j] === "[" || rotate[j] === "(" || rotate[j] === "{" )
                stack.push(rotate[j]);
            else {
                const last = stack.pop();
                if(last !== mapping[rotate[j]]) {
                    flag = false
                    break;
                }
            }
        }
        if(flag) answer++;
    }
    return answer;
}

• 먼저 괄호가 짝이 이루어지면 무조건 2로 나눴을 때 0이여야 하기 때문에 조건을 건다
• 객체를 활용해서 미리 각자 괄호를 매핑한다
• 반복문을 돌리면서 slice로 문자열을 구한뒤에 반복문을 실행
• 열린 괄호일때 push만 하고 닫힌 괄호일때 pop()으로 마지막 stack괄호를 빼고 만약 괄호가 매핑한 괄호와 맞지 않다면 false처리 한 뒤 break한다
• 마지막으로 flag가 true면 답을 1 증가시킨다

CS

Promise를 사용한 비동기 통신과 async, await를 사용한 비동기 통신의 차이

여러번 다루는 것 같은데 그만큼 자주 쓰이는 내용이긴 하다
js는 동기적인 언어지만 서버 데이터 요청하는 등 대기시간이 긴 작업의 경우 비동기 작업을 하기 때문

function printAnimals() {
  const animals = getAnimals(); //응답시간이 길경우
  console.log(animals);   //먼저 실행      
}

printAnimals();  // undefined

이런 문제가 생기기 때문에 비동기 처리 방식을 사용한다.
다만 Promise와 async await 의 용도는 똑같지만 다른 점이 분명 있다

차이점

• async는 Promise에 비해 간결하다. 거의 비슷하긴 하지만 들여쓰기도 라인 차지도 훨씬 적다
• async는 에러 핸들링에 유리하다. Promise의 then을 사용하면 내부에 추가적인 catch문을 적어야 하면 try-catch와 함께할 때 catch문이 중복되느 경우도 있다.
  async를 사용할 경우 하나의 catch만 해주면 된다
• async는 에러 위치를 찾기 쉽다! 연속으로 호출 할때 Promise는 then으로 여러번 중복되다 보니 찾기가 어려울 수 잇는데 async await은 에러 위치를 쉽게 특정할 수 있다

async function sample() {
  const data1 = await sampleFunc();      // 문제 발생시 data1값이 유효치 않음
  const data2 = await sampleFunc2(data1);
  return data2;
}

Reference

자료구조 stack과 queue

오늘 푼 알고리즘에 stack이 있었기에 한번 다뤄보고 가자

stack

쌓아 올린다는 것을 의미하는데 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조
후입 선출(LIFO, Last-in-first-out)
특징

• 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있다
• top으로 정한곳을 통해서만 접근 가능
• top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있음
• 삽입되는 새 자료는 top이 가리키는 자료 위에 쌓임
• 스택에서 자료를 삭제할 때도 top을 통해서만 가능
• 스택에서 top을 통해 삽입하는 연산을 push, top을 통한 삭제하는 연산 pop

활용 예시
후입 선출을 활용해서 여러 분야에서 활용 가능

• 웹 브라우저 방문기록(뒤로가기)
• 역순 문자열 만들기
• 실행 취소
• 후위 표기법 계산
• 수식의 괄호 검사

queue

줄을 서서 기다리는 것인데 선입 선출 방식(FIFO, First in first out)의 자료구조이다

특징
정해진 곳을 통해서 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.
이때 삭제 연산만 수행되는 곳을 프론트(front), 삽입 연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산작업만 수행된다.
이때, 큐의 리어에서 이루어지는 삽입 연산을 인큐(enQueue) 프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부른다

• 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
• 큐는 들어올 때 rear를 들어오지만 나올때는 front부터 빠지는 특성
• 접근 방법은 가장 첫 원소와 끝 원소로만 가능
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

즉, 뮤에는 프론트 원소는 가장 먼저 큐에 들어왔던 첫번재 원소가 되는 것이고 리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 된다.

활용예시
큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용

• 우선 순위가 같은 작업예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색 (BFS, Breadth-First Search)구현
• 캐시(Cacahe)구현

이때 javascript는 shift를 사용하는데 시간 복잡도가 O(n)으로 사용시 주의해야 한다. 앞의 한칸을 제거하며 배열 요소들을 앞으로 한칸씩 이동시키다 보니 배열 길이에 비례하여 시간이 소요된다.
pop과 push는 O(1)의 시간복잡도를 가진다