[알고리즘] 쇠막대기

문제 링크

 

문제명 : https://www.acmicpc.net/problem/10799

 

문제탐색

기본 원리 탐색

• 입력된 문자열을 순차적으로 처리하면서 정답을 도출해 내야합니다.

 

시간복잡도와 알고리즘

• 시간제한 : 1초
  • 약 1억번의 연산이 가능하다고 가정합니다.
• 문자열 최대수 : 10만
  • 시간복잡도가 O(n²) 인 알고리즘은 약 100억회의 연산이 필요하므로 시간복잡도를 초과하게 됩니다.
  • 2중첩이상의 for문은 불가합니다.

 

=> stack을 활용하여 한번의 for문으로 "구현" 합니다.

 

코드설계하기

1. 라인을 입력받습니다.
2. 아래 규칙에따라 반복문을통해 문자열을 순회합니다.
3. ( 다음항목이바로 ) 일경우 레이저로 판단
4. 레이저가 아닌경우 ( 이 나오면 리스트에 값 1 하나 추가하며 정답에 +1
5. 만약 레이저로 판단될시, 리스트의 길이만큼 정답에 + 
6. ) 가 나온경우 리스트에서 값1 하나 제거

 

시도회차 수정사항

• 1회차 : 시간복잡도를 계산하지 못하고 이중for문으로 구현
  • => 스텍 활용

 

정답코드

thick_and_hard = input()

razer_pass=0 #레이저 판별을 위함
block=[] #막대를 담아두는곳
result=0 #정답을 담는곳

for work in range(len(thick_and_hard)):

    #이전 작업이 레이저작업일경우 패스
    if razer_pass==1: 
        razer_pass=0
        continue

    #레이저일경우
    if thick_and_hard[work] == '(' and thick_and_hard[work+1] ==')': 
        razer_pass=1 
        result+=len(block) #블록커팅
        continue

    #막대 등장
    if thick_and_hard[work] == '(':
        block.append(1)
        result+=1
    
    #막대 끝
    if thick_and_hard[work] == ')':
        block.pop(0)

print(result)