스택

[JAVA] 백준 1460번 【에디터】

이 문제는, 스택으로 해결하였다. 시간 제한이 까다롭기 때문에, 스택을 사용하였고 스택을 사용했어도, 마지막에 출력하는 과정에서 println을 사용하면 시간초과가 난다. 따라서 BufferedReader 와 BufferedWriter를 사용했다. 이 문제가 요구하는 기능을 구현하기 위해서는 2개의 스택이 필요하다. 커서를 기준으로 왼쪽 데이터를 모아둘 스택과 오른쪽 데이터를 모아둘 스택로 사용할 것이다. 스택의 경우, 배열처럼 사이즈가 고정되어 있는 것이 아니기 때문에 활용하기 매우 편하다!! dmih 11 B B P x L B B B P y D D P z 예제 처럼, 입력해보며 원리를 파악해보겠다. 먼저, 초기값으로 dmih 가 입력되므로 에디터 모습은 오른쪽과 같고 커서를 기준으로 왼쪽 스택에는 위..

[JAVA] 백준 10799번 【쇠막대기】

이 문제는 Stack 클래스를 이용해서 해결하였다. 포인트는, 나눠진 쇠 막대기를 어떤 조건일 때, 어떤 값을 더해야하는지 파악하는 것이다. 차근차근 하나씩 그려보면, 바로 이해가 된다. 위와 같은 상황이 있다고 가정할때, '(' 가 있으면 스택에 '(' 를 계속 push 해주고 ')' 가 나올때 pop을 해주고 나서 조건을 따져봐야 한다. 첫 번째, ')' 를 만났다. 바로 이전 문자가 '(' 이므로 레이저임을 알 수 있다. 만약 ')' 를 만났을 때, 이전 문자가 ')' 라면 레이저가 아닐 것이다. 아무튼, 레이저가 발사되고, 남은 두개의 '(' 의 끝은 알 수 없지만, 확실한 건 현재 스택의 사이즈 만큼의 조각이 생긴다는 사실이다. 즉, result = result + stack.size(); 가 ..

[JAVA] 백준 9012번 【괄호】

위 문제는, Stack 클래스를 사용해서 풀어도 된다. 근데, 문제를 잘 이해하고, Stack 데이터 구조를 잘 알 고 있으면 굳이 Stack을 사용하지 않아도 풀린다. 나같은 경우는 Stack을 사용하지 않았다...ㅎ 먼저 VPS 가 될 수 있는 조건은 괄호가 짝을 이뤄야 하고, 감쌀 수 있는 형태로 입력되야 한다는 것이다. 규칙 1. [ () () ( ] 의 경우 괄호가 짝을 이루지 못하므로 VPS가 아니다. 규칙 2. [ () () )( ] 의 경우 괄호의 갯수는 짝을 이루지만, )( 가 감쌀 수 없는 형태이므로 VPS 가 아니다. 이 규칙을 생각해서, 초기값 0으로 지정한 변수를, " ( " 가 입력되면 +1 을 하고 " ) " 가 입력되면 -1을 하도록 하고 최종 값이 0이 되면 괄호가 짝을 이..

[JAVA] 백준 10828번 【스택】

백엔드 스쿨에서 한번 했었던, 스택 구현하기 문제였다. 스택이 어떤 데이터 구조인지 알면, 더 쉽게 풀 수 있지만, 몰라도 위 설명을 보고 위 기능을 구현하는 매서드를 만들면 충분히 해결할 수 있다. 먼저, 명령어 수가 10000개 주어지므로, 모든 명령어가 push인 경우에도 데이터 공간은 10000개면 충분하기 때문에, 클래스 변수로 index = -1, 10001 크기의 int 배열을 생성하였다. 그리고 5개의 static 메서드를 구현하였다. push 의 경우 데이터를 저장만하면 되므로, index를 전위연산자로 1 증가시켜준 후 배열에 입력하였다. pop은 index가 -1을 가리키고 있으면 스택이 비어있다는 의미이므로 조건식을 활용해 index가 -1인 경우 -1을 출력하게 하였고, 그 외는,..