[알고리즘] 쇠막대기 (백준 10799번)

10799번: 쇠막대기

 스택 사용 문제이다. 생각보다 해결 방법을 떠올리는 데 시간이 오래 걸렸다. 막대기가 겹쳐져있다는 조건 때문에 당황했다. 

 다른 사람들은 더 효율적인 방법으로 하긴 했는데 우선 내가 한 방법은 레이저를 나타내는 "()" 괄호쌍을 다른 문자로 대체하고 닫힌 괄호 ')'를 만났을 때 괄호쌍 대신 저장해놓은 문자들을 pop해서 개수를 센 뒤 문자 개수 +1 만큼 결과값에 더하는 방법을 택했다.

 

import org.omg.PortableInterceptor.INACTIVE;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {


	static void solution() throws  Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String str = br.readLine();

		Stack<Character> stack = new Stack<>();

		int result = 0;

		for(int i = 0;i < str.length();i++)
		{
			char c = str.charAt(i);

			if(c == ')')
			{
				if(str.charAt(i-1) == '(')
				{
					stack.pop();
					result += stack.size();
				}
				else
				{
					result++;
					stack.pop();
				}
			}
			else
			{
				stack.push(c);
			}
		}

		bw.write(result+"");

		bw.close();
	}




	public static void main(String[] args) {

		try
		{
			solution();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}


}

 

 더 최적화된 방법으로는 stack에는 열린 괄호만 삽입하고 "()"을 만날 때마다 결과값에 현재 stack의 크기를 더해주고

그냥 닫힌 괄호만 만났을 때는 결과값 + 1을 해주는 방법이 있다. 물론 닫힌 괄호를 만날때마다 stack의 열린 괄호들은 pop 해준다.

 

import org.omg.PortableInterceptor.INACTIVE;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {


	static void solution() throws  Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String str = br.readLine();

		Stack<Character> stack = new Stack<>();

		int result = 0;

		for(int i = 0;i < str.length();i++)
		{
			char c = str.charAt(i);

			if(c == ')')
			{
				if(str.charAt(i-1) == '(')
				{
					stack.pop();
					result += stack.size();
				}
				else
				{
					result++;
					stack.pop();
				}
			}
			else
			{
				stack.push(c);
			}
		}

		bw.write(result+"");

		bw.close();
	}




	public static void main(String[] args) {

		try
		{
			solution();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}


}