자료구조
[자료구조] 5일차 스택으로 풀 수 있는 문제
홍시_코딩기록
2024. 4. 15. 23:53
올바른 괄호인지 판단하기
:짝이 맞는 지 확인하기
- 각 괄호를 하나씩 처리하기
- 괄호 문자열 특징 알아보기
특징
- 나중에 등장한 여는 괄호는 항상 먼저 등장한 여는 괄호보다 먼저 완성
- 닫히지 않은 괄호가 존재하면 올바르지 않음.
- 여는 괄호가 남김 없이 모두 완성되어야함.
올바른 괄호인지 판단하기 - 예시
- 괄호를 처음부터 하나씩 검토하기
- 여는 괄호라면 스택에 넣고, 닫는 괄호라면 스택에서 하나 제거
- 괄호 문자열을 처리한 결과에 따라 값 반환= (b) (a)가 아니거나, 스택이 비어있는 상태에서 닫는 괄호가 입력되었다면 올바른 괄호가 아님.
- = (a) 괄호 문자열을 모두 처리하고 나서 스택이 비어있다면 올바른 괄호
계산 순서 정하기
- 입력되는 닫는 괄호와 대응하는 여는 괄호를 찾기
- 스택에 저장하는 값을 ‘여는 괄호의 인덱스’로 하고 짝궁 여는 괄호 위치 찾기
스택으로 수열 만들기
수열 규칙
- 1부터 N까지의 모든 정수를 한 번씩 스택에 입력하고 출력하기
- 무조건 작은 수는 큰 수보다 먼저 입력(ex. 1보다 3이 먼저 입력되는 경우는 없음)
문제 풀이 방법
: 실제로 스택에 숫자들 넣어보면서 확인해보기
메모장 만들기
: 알파벳으로 된 한 문장을 저장할 수 있는 메모장 만들깅
메모장이 처리할 수 있는 명령어
: 커서를 기준으로 왼쪽, 오른쪽 문자열을 스택으로 생각할 수 있다.
스택 구현
- 커서를 기준으로 왼쪽 문자열과 오른쪽 문자열을 각각 스택으로 저장.
- 각 명령어에 대해 아 스택을 사용