알고리즘(Python, JavaScript) - 쇠막대기

Input

1
arrangement = "()(((()())(())()))(())"

Expected Output

1
return = 17

Objective

  • A stick can be placed on a stick that is longer.
  • Endpoints cannot be overlapped.
  • Each stick has at least one laser cut.
  • Laser does not cut at the endpoint.
  • Parentheses that are closed right after opened represent lasers.

Condition

  • arrangement.length <= 100,000
  • opening.length == closing.length

코드

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(arrangement):
    opened_count, final_count = 0, 0
    arrangement = arrangement.replace("()", "0")
    
    for val in arrangement:
        if val == "0":
            final_count += opened_count
        elif val == "(":
            opened_count += 1
        else:
            opened_count -= 1
            final_count += 1
        
    return final_count

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function solution(arrangement){
    var opened_count = 0; 
    var final_count = 0;
	arrangement = arrangement.replace(/\(\)/g, "0");
    for (var i in arrangement) {
        var val = arrangement.charAt(i);
        if (val === "0"){
            final_count += opened_count;
        }   
        else if (val === "(") {
            opened_count++;
        }   
        else {
            opened_count--;
            final_count++;
        }
    }
    return final_count
}

Comments

  • ()는 반드시 레이저를 표현하기때문에 ()를 하나의 원소로 표현하기 위히해 “0”으로 치환합니다.
  • () represents laser so replace them with one length element such as 0.
  • arrangement를 하나씩 탐색할때 괄호는 여는 (를 만날때마다 쇠막대기가 하나씩 쌓이는 행위를 의미합니다.
  • Exploring each element of arrangement, opening paranthsis represent stacking one layer of stick.
  • 쌓임이 유지되다 레이저를 만나면 쌓인 레이어만큼 총 조각이 늘어나게 됩니다.
  • While exploring and stacking layers, when you meet laser, as manay as current layer, you will gain total pieces.
  • 쌓임이 유지되다 )를 만나면 유지되고 있는 레이어가 줄어듭니다.
  • While stakcing layers, when you meet ), current number of layers loses 1.
  • (를 만나면 레이어수인 opened_count를 늘리고 레이져를 만나면 만난 당시의 opened_count 만큼 총 조각 수인 final_count를 늘립니다.
  • When you meet (, increase opened_count(current number of layers). When you meet “)”, decrease opened_count. When you meet “0”(laser), incrase final_count as much as opened_count.