[자료구조] 5일차 스택으로 풀 수 있는 문제

올바른 괄호인지 판단하기

:짝이 맞는 지 확인하기

1. 각 괄호를 하나씩 처리하기
2. 괄호 문자열 특징 알아보기

특징

1. 나중에 등장한 여는 괄호는 항상 먼저 등장한 여는 괄호보다 먼저 완성
2. 닫히지 않은 괄호가 존재하면 올바르지 않음.
3. 여는 괄호가 남김 없이 모두 완성되어야함.

올바른 괄호인지 판단하기 - 예시

1. 괄호를 처음부터 하나씩 검토하기
2. 여는 괄호라면 스택에 넣고, 닫는 괄호라면 스택에서 하나 제거
3. 괄호 문자열을 처리한 결과에 따라 값 반환= (b) (a)가 아니거나, 스택이 비어있는 상태에서 닫는 괄호가 입력되었다면 올바른 괄호가 아님.
4. = (a) 괄호 문자열을 모두 처리하고 나서 스택이 비어있다면 올바른 괄호

계산 순서 정하기

• 입력되는 닫는 괄호와 대응하는 여는 괄호를 찾기
• 스택에 저장하는 값을 ‘여는 괄호의 인덱스’로 하고 짝궁 여는 괄호 위치 찾기

 

 

스택으로 수열 만들기

수열 규칙

• 1부터 N까지의 모든 정수를 한 번씩 스택에 입력하고 출력하기
• 무조건 작은 수는 큰 수보다 먼저 입력(ex. 1보다 3이 먼저 입력되는 경우는 없음)

문제 풀이 방법

: 실제로 스택에 숫자들 넣어보면서 확인해보기

 

메모장 만들기

: 알파벳으로 된 한 문장을 저장할 수 있는 메모장 만들깅

 

메모장이 처리할 수 있는 명령어

: 커서를 기준으로 왼쪽, 오른쪽 문자열을 스택으로 생각할 수 있다.

 

 

 

스택 구현

 

1. 커서를 기준으로 왼쪽 문자열과 오른쪽 문자열을 각각 스택으로 저장.
2. 각 명령어에 대해 아 스택을 사용