Stack3 [알고리즘] 에디터 (백준 1406번) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수� www.acmicpc.net 자료구조를 적절히 사용해서 시간 효율성을 따지는 문제이다. 함부로 내장 라이브러리를 사용하게 된다면 O(NM) 시간이 걸리기에 무조건 시간초과가 발생한다. 때문에 한 번에 명령에 O(1) 시간이 걸려야하므로 총 O(M) 시간에 문제를 해결해야 한다. Solution 기본적으로 ArrayList, LinkedList 등은 내부적으로 값을 삽입, 조회, 삭제 시 O(N)시간이 걸리기에 사용해선 안된다. 난 Stack 2개를 활용해서 커서를 기준으로 왼쪽 문자열 스택.. 2020. 8. 31. [알고리즘] 쇠막대기 (백준 10799번) 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저� www.acmicpc.net 스택 사용 문제이다. 생각보다 해결 방법을 떠올리는 데 시간이 오래 걸렸다. 막대기가 겹쳐져있다는 조건 때문에 당황했다. 다른 사람들은 더 효율적인 방법으로 하긴 했는데 우선 내가 한 방법은 레이저를 나타내는 "()" 괄호쌍을 다른 문자로 대체하고 닫힌 괄호 ')'를 만났을 때 괄호쌍 대신 저장해놓은 문자들을 pop해서 개수를 센 뒤 문자 개수 +1 만큼 결과값에 더하는 방법을 택했다. import org.omg.PortableInterceptor.INACTIVE; imp.. 2020. 8. 30. [자료구조] 스택 (Stack) 스택 (Stack) 자료를 한 방향으로만 쌓는 자료구조 LIFO (Last In First Out 후입선출 : 마지막에 들어온 것이 가장 먼저 나간다) push : 스택에 data를 넣는 것 pop : 스택 맨 위의 data를 빼는 것 peek : pop과 유사하게 맨 위의 data를 반환하지만 스택에서 제거하지는 않는다. top : 가장 마지막에 추가된 data의 위치 (가장 맨위) 가장 마지막에 push 한 data가 가장 먼저 pop 된다. 오버플로우 (Overflow) : 자료가 스택 크기를 넘어서서 더 이상 push 하지 못할 때 발생 언더플로우 (Underflow) : 스택에 자료가 남아있지 않아서 더 이상 pop하지 못할 때 발생 배열로 구현해보기 public class Main { stat.. 2020. 8. 26. 이전 1 다음
