쇠막대기(stack 개념)
in Algorithm
여러 개의 쇠막대기를 레이저로 절단하려고 한다.
효율적인 작업을 위해서 쇠막대기를 아래에 서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다.
쇠막대기와 레 이저의 배치는 다음 조건을 만족한다.
• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
- 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. • 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. • 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.
아래 그림은 위 조건을 만족하는 예를 보여준다.
수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.
이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.
레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반 드시 레이저를 표현한다.
쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다. 위 예의 괄호 표현은 그림 위에 주어져 있다.
쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데,
위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고,
이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때,
잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.
▣ 입력예제 1 : ()(((()())(())()))(())
▣ 출력예제 1 : 17
▣ 입력예제 2 : (((()(()()))(())()))(()())
▣ 출력예제 2 : 24
<개념 & 문제 접근방식>
괄호가 문제에 들어있다면 10에 8은 stack문제라고 생각하면 된다.
여는 괄호를 넣으면 무조건 stack에 푸시
아는 괄호는 1. 여는 괄호 2. 막대기 시작점 이렇게 2가지 종류로 생각해볼 수 있다.
닫는 괄호는 1. 레이저의 괄호 2. 막대기 끝
닫는 괄호를 만나면 무조건 바로 앞의 괄호를 찾아봐야한다.
i번째가 닫는 괄호라면 i-1의 요소를 찾아 그게 여는 괄호인지 바로 체크를 해주고,
만약 바로 앞의 요소가 여는 괄호라면 i번째 괄호는 레이저의 닫는 괄호이다.
만약 바로 앞의 요소가 여는 괄호가 아니라면 i번째 괄호는 막대기의 끝 괄호라고 생각하면 된다.
막대기의 갯수는 stack에 들어있는 여는괄호의 갯수와 같다.
그리고, 닫는괄호를 만나면 앞의 여는 괄호를 무조건 하나 빼야한다.
왜냐면 레이저의 괄호이건, 막대기의 끝 괄호이건 stack에 들어있는 열린괄호는 제거해주어야함.
그리고 answer에다가는 +1 해주어야한다.
레이저로 자르면 막대기가 하나 생기기 때문에 +1해주어야함.
그리고 pop을 해주고 나면 (새로운 열린괄호가 들어오기전에) answer에서는 stack의 size를 누적시켜준다.
막대기의 객수를 누적해줘야하기때문에..
CASE 1
function solution(s){
let answer=0;
let stack=[];
for(let i=0; i<s.length; i++){ //idx를 뽑기 위해 for of문 안씀
if(s[i]==='(') stack.push('('); //열린괄호를 만나면 push하기
else{ //닫힌괄호라면
stack.pop(); //괄호를 제일 먼저 빼주어야함. if문 위에서 미리 빼줘야함
if(s[i-1]==='('){ //i-1(바로전)괄호가 열린괄호라면 => 레이저
answer+=stack.length; //stack에 쌓여있는 열린괄호 갯수를 넣어준다
}else{ //레이저가 아닌 막대기의 끝
answer++;
}
//stack.pop(); 이 위치에 하면 레이저까지 카운팅한다.
}
}
return answer;
}
let a="()(((()())(())()))(())";
console.log(solution(a));
출처 : 자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)를 보고 작성!
