-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
선생님 덕분에 스택이 이해가 되고 풀리는 것 같아요 ㅠㅠ!
22.03.06 02:47 작성 조회수 142
0
접근방식이 헷갈릴때 접근방식만 듣고 다시 풀어보면 바로 풀리네요 ㅜㅜ 항상 감사해요!!
- tip. () 괄호가 나오는 문제는 보통 stack 활용하면 된다.
> 문제 : 쇠막대기와 레이저의 배치를 나타내는 괄호가 주어졌을 때, 레이져로 잘린 쇠막대기 조각의 총 개수를 출력해라
> 입력 :
1. 모든 레이저는 ‘( )’ 으로 표현된다.
2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.
- 조건 1) 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
=> 긴 쇠막대기 위에 놓을때 쇠막대기의 양 끝점은 겹치지 않고, 완전히 그 안에 포함되게 놓인다.
- 조건 2) 쇠 막대기를 자르는 레이저는 1개 이상이다.
- 조건 3) 레이저는 쇠막대기의 양 끝점과 겹치지 않는다.
## 접근방식
1. stack 스택자료구조 활용하기!
2. 나열된 괄호를 조회하며 쇠막대기 왼쪽 끝인, ( 여는 괄호를 만날경우? ( 여는 괄호가 반복되면 쇠막대기 개수가 추가된다.
=> 쇠막대기 ( 를 모두 stack[]에 담아준다. (쇠막대기 개수 증가)
3. ) 닫는 괄호를 만날경우? => stack []에 있는 "("여는 괄호 1개를 제거한다.
**")" 닫는괄호는 꼭 두가지 경우를 생각해야한다.**
4. 레이져인 경우 => stack[] 가장 위(바로 직전)에 여는 괄호일 경우 "()" 레이져
4-1. 레이져가 나올때마다 "()" => stack[] ( 여는괄호 하나 제거 후,
4-2. Stack[]에 남아있는 괄호의 개수(잘려진 쇠막대기 조각 개수)를 더해준다.
5. 쇠막대기의 끝인 경우 => stack[] 가장 위에 있는 괄호가 ")" 닫는 괄호일 경우 쇠막대기의 마지막 끝이다.
5-1. ) 닫는괄호의 짝인 ( 여는괄호를 stack[]에서 삭제하며 +1 을 더해준다.
=> 쇠 막대 한개가 완성되면, 레이져로 잘리고 남은 쇠조각 1개만 남기 때문에 +1을 해주는 것이다.
## 풀이
1. 개수를 세줄 변수 cnt를 선언하고 초기값 0 할당, ( 괄호를 담을 변수 stack선언하고 [] 할당한다.
2. for 문으로) str 괄호가 정렬되어있는 문자열을 순서대로 모두 조회한다.
3. if문) ( 를 만날 경우?
=> stack []에 반복해서 (를 담아준다. => push()
4. else문) ) 를 만날 경우?
5. if 문) str[i-1] 직전 요소가 "("인 경우?
=> stack[]맨 위의 (를 제거한다. => pop()
=> stack[]에 담긴 요소개수 stack.length 를 cnt에 더해준다.
6. else문) str[i-1] 직전 요소가 ")"인 경우?
=> stack[] 맨 위의 (를 제거한다. => pop()
=> cnt 개수에 +1을 더해준다.
7. 모든 요소를 조회하여, for 문이 종료되면 레이져로 잘린 쇠조각의 개수 cnt를 출력한다.
### 선생님 풀이와 다른 점
")" 를 만날 경우? 무조건 stack[]의 맨 위 ( 괄호를 제거해야하니깐, 아래 코드처럼 적으면 pop()을 한번만 실행하면된다.
else {
stack.pop();
if (str[i - 1] === "(") {
cnt += stack.length;
} else {
cnt++;
}
-->
<script>
function solution(str) {
let cnt = 0;
let stack = [];
for (let i = 0; i < str.length; i++) {
if (str[i] === "(") {
stack.push(str[i]);
} else {
if (str[i - 1] === "(") {
stack.pop();
cnt += stack.length;
} else {
stack.pop();
cnt++;
}
}
}
return cnt;
}
let str = "()(((()())(())()))(())";
console.log(solution(str));
</script>영 관련 문의는 1:1 문의하기를 이용해주세요.
답변을 작성해보세요.
0
답변 1