선생님 덕분에 스택이 이해가 되고 풀리는 것 같아요 ㅠㅠ!
234
지루한 메기
작성한 질문수 11
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 문의하기를 이용해주세요.
답변 1
continue를 사용하는 이유
0
101
2
정렬 가능 여부 판단하기
0
80
2
알고리즘 학습법 관련해서 질문드립니다.
0
95
1
코드 리뷰 부탁드립니다!
0
107
1
indexOf를 사용해서 풀어보았습니다 !!
0
75
1
저는 이런식으로 구현 해보았습니다 !!
0
69
1
12,13,14 강의 소리만 나오고 검은 화면입니다
0
110
3
반복문 최소화하고 indexOf 사용해서 풀어봤습니다
0
74
1
영상 보기 전에 직접 풀어봤습니다.
0
79
1
섹션1의 17번문제 이 풀이로 풀어도 될까요?
0
141
2
정규표현식으로 처리해도 상관없나요 ?
0
127
2
3칸씩 건너뛸 수 있을 경우
0
132
2
강의에 대해 질문있습니다.
0
144
2
Object와 Set을 이용해 풀어봤습니다.
0
128
2
이렇게 해도 되나요?
0
107
2
선생님 중복 단어나 중복관련 문제들은 set을 이용하면 좋을것 같습니다.
0
149
2
이렇게 풀어도 괜찮을까요?
0
145
1
이렇게 풀어도 괜찮을까요?
0
123
1
모든 아나그램 찾기에서 시간복잡도
0
106
1
코드리뷰 부탁드립니다.
0
138
1
for loop 탈출은 return 문으로 해도 되지 않나요?
0
133
1
투포인트알고리즘으로 풀어봤습니다.
0
147
0
코드 리뷰 부탁드립니다.
0
121
1
코드 맞게 작성한 거 아닌가여??
0
149
1