섹션 5. Stack, Queue(자료구조) 1. 올바른 괄호

문제

• 괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.
• (())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

입력

• 첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.

출력

• 첫 번째 줄에 YES, NO를 출력한다.

입출력 예제

---

풀이방식

이번 문제는 Stack 을 사용하여 푸는 문제이다.

---

설계과정

1. 입력받은 괄호들을 하나씩 분리해서 ' ( ' 와 ' ) ' 을 구분한다.

2. ' ( ' 를 스택에 넣는다.

3. ' ) ' 가 입력되면 ' ( ' 를 하나 스택에서 제거한다.

4. 결과적으로 스택이 비어있으면 YES, 비어있지 않으면 NO가 출력되게 한다.

---

풀이과정

1. 값들을 입력받는 코드를 작성한다.

 

2. String 형으로 메소드를 작성한다.

 

3. 결과값을 출력할  result와 Stack을 선언한다.

• result 는 YES로 초기값을 설정한다.
• Stack 은 입력받은 괄호 문자열을 하나씩 쪼개서 하나의 문자를 넣을 것이므로 Character로 선언한다.

4. toCharArray() 를 사용해서 입력받은 문자열을 하나의 문자로 쪼개서 비교한다.

• toCharArray() : 입력된 문자열을 문자 하나씩 분리해서 문자 배열을 생성함
• char x : 하나씩 쪼갠 문자열을 담는 변수

5. push() 를 사용해서 x가 ' ( ' 면 스택에 값을 넣는다. 

• push() : 스택에 값을 추가한다.

6. else 를 통해 ' ) ' 가 입력된 상황에서  스택이 비어있으면 NO를 리턴한다.

• ' ) ' 가 입력되었는데, 스택에는 ' ( ' 가 없으므로 이는 올바른 괄호가 아님을 의미한다.

7. 스택이 비어있으면 pop() 을 통해 스택에서 값을 제거한다.

• pop() : 스택에서 값을 제거한다.
• 스택에는 ' ( ' 만을 넣고 x가 ' ) '이면, 그와 짝이되는 ' ( '  즉, 가장 상단에 ' ( ' 을 스택에서 빼낸다.
• 아래 그림을 통해 자세히 이해해보자.

---

입력값 : ( ( ) ) )

    1) 처음에는 ' ( ' 가 들어오고, if문을 통해 스택에 값이 들어간다.

    2) 두번째에 ' ( ' 가 들어오고, 동일하게 if문을 통해 스택에 값이 들어간다.

    3) 세번째에 ' ) ' 가 들어온다. 이 때 스택은 비어있지 않으므로 else 문을 통해 스택에서 가장 상단의 값이 빠진다.

    4) 네번째에 ' ) ' 가 들어오고, 위와 같은 상황이므로 가장 상단의 값이 빠진다.

    5) 다섯번째에 ' ) ' 가 들어오고, 스택이 비어있으므로 else 문을 통해 NO가 리턴된다.

---

8. for문이 끝났는데도 스택에 값이 비어있지 않으면 NO를 리턴한다.

• ' ( ' 가 스택에 남아있다는 것은 ' ) ' 가 충분하지 않은 것이므로 이는 올바른 괄호가 아님을 의미한다.

 

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.