[자료구조(연습)] [BJ10799] 쇠막대기

코드 플러스

🚩 문제 설명

https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

 

⏱️ 시간 복잡도
▪ 괄호 문자의 개수는 최대 10만이다.
▪ 그러므로 O(N^2)의 시간복잡도를 가지면 안되고 O(N)이나 O(NlogN)의 시간복잡도를 가져야한다.
▪ 괄호 문자를 훑으며 잘려진 쇠막대기의 개수를 구해야한다.
▪ 시간복잡도는 O(N)이라고 할 수 있다.

◾ 괄호 표현 구분

• 레이저 ➡ ()
• 쇠막대기 ➡ ( ~~ )

◾ 문제의 이해는 다음과 같다.

Algorithm
1. ( 을 만나면
- stack에 push 한다.
2. ) 을 만나면
2-1. idx와 top의 idx가 1 차이 날 때
- stack에서 pop 한다.
- stack에 담겨져 있는 요소 만큼 막대기 수를 더한다.
2-2. idx와 top의 idx가 1 차이 나지 않을 때
- 1 더한다.

 

 

 

---

 

 

 

✅ 입출력

1) 레이저와 쇠막대기를 표현하는 괄호문자가 주어진다.
return ➡️ 잘려진 쇠막대기의 갯수를 출력한다.

✔️ 예제 1

()(((()())(())()))(())

17

✔️ 예제 2

(((()(()()))(())()))(()())

24

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys

ans = 0
ins = sys.stdin.readline() # 괄호 입력
stack = [] # 스택 배열

top = -1 # 스택 top 의 인덱스
for idx, i in enumerate(ins):
    if i == '(':
        stack.append(idx)
        top = idx

    elif i == ')':
        if top == idx - 1:
            stack.pop()
            if stack:
                top = stack[-1]
            else:
                top = -1
            ans += len(stack)
        else:
            stack.pop()
            ans += 1
            if stack:
                top = stack[-1]
            else:
                top = -1

print(ans)

 

with 자바 (Java)

package problem.BJ;


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

//()(((()())(())()))(())
//-> 17
//(((()(()()))(())()))(()())
//-> 24


public class BJ10799_쇠막대기 {
	static int ans;
	static Deque<Character> stack = new ArrayDeque<>();


	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		char prev = '(';
		for (char ch : br.readLine().toCharArray()) {
			// 여는 괄호 (
			if (ch == '(') stack.push(ch);
			// 닫는 괄호 )
			else {
				stack.pop(); // 여는 괄호 빼기 (짝 맞추기)

				if (prev == '(') ans += stack.size(); // 레이저인 부분 ()
				else ans++; // ))
			}

			prev = ch;
		}

		System.out.println(ans);

	} // end main
}

💬 Point

➡️  stack 사용

◾ 스택 배열을 사용한다.

◾ top이라는 변수를 둬서 마지막 요소의 값을 넣는다.

◾ 만약 top과 idx의 차가 1이라면 레이저에 해당한다.

◾ 따라서, 나무 막대가 잘려지므로 stack에 담겨져있는 만큼 더한다.

◾ 1차이가 나지 않는다면 스택에 담겨있는 나무 막대가 끝나는 것이므로 1을 더해준다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 코드플러스 쇠막대기 파이썬

# 백준 10799 쇠막대기 파이썬

# 백준 쇠막대기 파이썬 java

---