[SWEA] 1218. 괄호 짝짓기

 

[SWEA] 1218. 괄호 짝짓기

 

 

 

예를 들어 아래와 같은 문자열은 유효하다고 판단할 수 있다.

아래와 같은 문자열은 유효하지 않은 문자열이다. 붉은색으로 표시된 괄호의 짝을 찾을 수 없기 때문이다.

 

 

[입력]

각 테스트 케이스의 첫 번째 줄에는 테스트케이스의 길이가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트케이스가 주어진다.

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 유효성 여부를 1 또는 0으로 표시한다 (1 - 유효함, 0 - 유효하지 않음).

 

 

[풀이]

 

이 문제는 스택을 이용해야한다.

Java util의 스택을 이용해주었다.

열린괄호는 무조건 넣고 닫힌 괄호 발견시 스택의 맨위 괄호가 어떤건지 검사한 후 짝이 맞으면 스택에서 빼낸다. 

짝이 안 맞는 닫힌 괄호는 스택에 넣는다.

작업이 끝나고 스택이 모두 비면 짝이 맞아서 다 빼냈다는 말이니 유효성을 1로 한다.

 

 

 

public class al218 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		Stack<Character> s = new Stack<>(); //괄호 넣을 스택 생성
		HashMap<Character,Character> map = new HashMap<>(); 
        //같은 괄호 짝지어서 HashMap에 key,value로 저장
		map.put(')', '(');
		map.put(']', '[');
		map.put('}', '{');
		map.put('>', '<');
		
		StringBuffer sb = new StringBuffer();
		
		for(int test_case = 1; test_case <= 10; test_case++)
		{
		
			int n = sc.nextInt();
			char[] data = sc.next().toCharArray();
			int result = 0;
			
			for (int i = 0; i < n; i++) {
				char t = data[i];
				if(t == ')' || t == ']' || t == '}' || t == '>') { //닫힌 괄호 발견시 제일 위 괄호 검사
					if(s.peek() == map.get(t)) { //닫힌 괄호의 열린 괄호 짝과 같으면 스택에서 빼내기
						s.pop();
					}else {
						s.push(data[i]); //아닐 시에는 짝없는 닫힌 괄호 저장
					}
				}
				else{
					s.push(data[i]); //열린 괄호는 무조건 저장
				}
			}
			if(s.isEmpty()) { //스택이 비어있으면 짝맞는 괄호가 전부 나간 것
				result = 1;
			}
			sb.append("#" + test_case + " " + result + "\n");
			s.clear();
		}
		
		System.out.println(sb.toString());
	}

}

 

• 20,432 kb메모리
• 144 ms실행시간
• 1,037코드길이
• Pass결과