여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다.
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.
쇠막대기와 레이저의 배치는 다음 조건을 만족한다.
function solution(s) {
let answer = 0;
let stack = s.split('');
let stick = 0;
let wasClosed = 0;
while (stack.length > 0) {
let tmp = stack.pop();
if (tmp == ')') {
if (wasClosed == 1) {
stick = stick + 1;
} else {
wasClosed = 1;
}
} else {
if (wasClosed == 1) {
answer = answer + stick;
} else {
answer = answer + 1;
stick = stick - 1;
}
wasClosed = 0;
}
}
return answer;
}
function solution(s){
let answer=0;
let stack=[];
for(let i=0; i<s.length; i++){
if(s[i]==='(') stack.push('(');
else{
stack.pop();
if(s[i-1]==='(') answer+=stack.length;
else answer++;
//stack.pop(); 이 위치에 하면 레이저까지 카운팅한다.
}
}
return answer;
}
공통적으로 stack
을 활용하여 문제를 풀었다. javascript의 기본 자료형인 array
에 push()
와 pop()
함수가 있기 때문에 스택의 형태로 문제를 풀 수 있었다. 또한 공통적으로 O(2n)
의 시간복잡도로 문제를 풀었다.
나의 풀이의 경우 가장 먼저 쇠막대와 레이저의 표현인 s
를 split()
하여 stack
에 저장했다. 하지만, 정답 풀이의 경우 모든 s
에 대해 반복하는 반복문을 사용하고, '('이 등장하는 경우 해당 값들을 저장하고, stack.length
를 현재 깔려있는 쇠막대의 갯수로서 측정하기 위해 stack
을 사용했다. 따라서 시간복잡도는 같지만 별도로 wasClosed
와 stick
변수의 사용을 줄일 수 있었기 때문에 가독성이 더 높았다.