이번에 알아볼 것은 굉장히 유명한 자료구조 삼대장들인 스택(Stack), 큐(Queue), 데크(Deque) 입니다. 스택 (Stack) 스택은 자료구조의 맨 위에서만 삽입과 삭제가 일어나는 자료구조 입니다. 포인터가 맨 위를 가르키고 있어, 데이터의 가장 위에서만 삽입과 삭제가 일어나지요. 가장 나중에 들어간 원소가 가장 빨리 나오는 LIFO(Last in - First out) 구조 입니다. PUSH를 통해 원소를 삽입, POP을 통해 원소를 꺼냅니다. 이는 쌓아놓은 접시와 비슷합니다. 접시를 쌓을 때는 보통 가장 윗 접시부터 꺼내 쓰곤하죠? 컨트롤 + z를 눌러 뒤로가기를 하는 것도, 브라우저의 뒤로가기도 스택의 예시 중 하나입니다. 자바의 Stack 클래스 출력 : 10, 10, 5, 3 자바에서..
https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 난이도 : 실버 4 태그 : 자료구조, 문자열, 스택 설명 모든 왼쪽 괄호는 오른쪽 괄호와 맞아야 합니다. [](), [()] 등은 맞지만, ([], ([)] 등은 맞지 않습니다. 스택을 활용하기 좋은 문제일 것 같네요. [()]을 예로 들겠습니다. 첫 번째 글자 : [ stack에 문자를 넣습니다. 현재 스택 : [ 두 번째 글자 : ( stack이 비어있지 않으나, 가장 ..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 난이도 : 실버 2 태그 : 자료구조, 스택, 연결리스트 시도 1 간단히 생각해보면, 스택이나 리스트 하나를 만들어두고 커서의 위치를 담을 cursorIdx 변수를 만들어 특정 위치에서 add 혹은 remove를 하면 쉽게 풀릴 것 같네요 import java.util.StringTokenizer fun main() = with(System.`in`.bufferedReader()) { val wor..
https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 난이도 : 실버 4 태그 : 자료구조, 스택 설명 각 단어끼리 이으면서, 선이 교차가 되면 안됩니다. 이는 스택을 사용해서 구현할 수 있겠는데요. BAAB 와 같이 주어지면, B를 스택에 넣습니다. (현재 스택 : B) A를 스택에 넣습니다. (현재 스택 : BA) A를 스택에 넣습니다. (현재 스택 : BAA) 새롭게 들어온 원소 A가 바로 앞에 있던 원소 A와 같으니, 제거합니다. (현재 스택 : B) ..
https://www.acmicpc.net/problem/23253 23253번: 자료구조는 정말 최고야 위 그림처럼 책이 쌓여 있으므로, 첫 번째 더미 - 두 번째 더미 - 첫 번째 더미 - 두 번째 더미 순으로 꺼내면 책 번호순으로 나열할 수 있다. www.acmicpc.net 난이도 : 실버 5 태그 : 구현, 애드 혹, 스택, 자료 구조 설명 책 더미의 맨 위에있는 책을 꺼내, 순서대로 나열할 수 있는가에 대한 문제입니다. 책더미의 맨 위에서 꺼내는 것이므로, 책 더미가 애초에 내림차순으로 정렬되어 있지 않으면 책을 순서대로 나열하는 것은 항상 불가능합니다. 즉, 쌓여있는 책의 번호를 입력받고, 이게 내림차순 정렬이 되어있는가만 판단하면 됩니다. 소스코드 import sys # 책의 개수, 책의 ..
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 스택, 문자열 설명 문제의 지문에 문자열의 길이는 1~1,000,000 로 명시되어 있습니다. 가장 쉽게 풀 수 있는 방법은 replaceAll 메소드를 사용하는 것 이겠지만, 문자열의 길이를 보니 시간초과, 메모리 초과 등이 날 것이 당연하네요. 따라서, 저는 Stack 자료구조를 사용하여 해당 문제를 풀이하였습니다. 스택에 하나씩 문자열을 ..
https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 난이도 : 실버 4 알고리즘 분류 : 자료구조, 스택 스택(Stack) 자료구조를 이용하여 풀 수 있는 문제 입니다. 소스코드 import java.io.BufferedReader import java.io.InputStreamReader lateinit var stack: IntArray var ptr = -1 fun main() { val br = BufferedReader(..