본문 바로가기

Problem Solving1213

[백준] 10799 쇠막대기 - Data Structure / Java • 문제 링크 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net • 풀이 과정 기본적으로 9012번 문제와 유사한 문제이다 [백준] 9012 괄호 - Data Structure / Java • 문제 링크 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄 graycode.tistory.com 입력받은 문자가 '(' 일 경우 스택에 push() 하고 ')' 일 경우 pop.. 2022. 6. 17.
[백준] 1406 에디터 - Data Structure / Java • 문제 링크 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net • 풀이 과정 두 개의 Stack 을 생성, 각각 stk, tmp 로 명칭하고 이를 활용해 커서의 움직임에 따른 문자열의 변화를 구현한다. 기본적으로 stk 이 커서의 왼쪽 영역, tmp가 커서의 오른쪽 영역이라고 인식하며 풀이한다. 각각의 명령어를 스택의 LIFO 구조를 활용하여 L, D, B 는 값이 비어있지 않은 경우 값을 이동 및 삭제, P $ 의 경우 할당된 값을 stk에 삽입한다. 두번째 입력을 예시로 들어 각각 스택의 값 변화를 나타내면.. 2022. 6. 16.
[백준] 1874 스택 수열 - Data Structure / Java • 문제 링크 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net • 풀이 과정 입력받은 수열을 input 배열에 저장하고 Stack 을 활용하여 구현한다. 1 ~ n 까지 오름차 순으로 스택에 push() 할 종료 조건이 오름차 순의 수가 n에 도달 시 인 while 문을 생성, 스택에 값이 삽입될 때마다 StringBuilder에 '+' 를 줄 바꿈과 함께 더한다. 스택이 비어있지 않고, peek() 함수로 반환한 스택의 맨 상.. 2022. 6. 15.
[백준] 1158 요세푸스 문제 - Data Structure / Java • 문제 링크 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net • 풀이 과정 문제에 제시된 7(n), 3(k) 입력 값으로 순열의 변화를 나타내면 아래와 같다. 1 2 3 4 5 6 7 -> 4 5 6 7 1 2 -> 7 1 2 4 5 -> 4 5 7 1 -> 1 4 5 -> 1 4 -> 4 이렇게 붉은 색으로 마킹한 k번째 수들이 모여 3 6 2 7 5 1 4 요세푸스 순열이 구해진다. 우선 1 ~ n 까지 오름차순으로 Queue 에 저장 후, k-1 번의 횟수만큼 큐의 맨 앞의 값을 poll()하여 큐의 맨 뒤로 삽입한다. 이런식으로 k번째 수가 큐의 맨 앞에 위치하게 되며 해당 값을 요세푸스 순.. 2022. 6. 14.
[백준] 9012 괄호 - Data Structure / Java • 문제 링크 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net • 풀이 과정 문제에 제시된 조건에 의해 올바른 괄호 문자열이 되기 위해선 여는 괄호 '(' 가 존재 시 반드시 이에 대응하는 닫는 괄호 ')' 가 존재하여야 한다. 기본적으로 올바른 괄호는 여는 괄호에서 시작되고 입력받은 문자가 여는 괄호일 시 스택에 순차적으로 push(), 닫는 괄호일 시 스택에 쌓여있는 여는 괄호 하나를 pop() 하여 해당 괄호가 열고 닫는 괄호 쌍으로써 존재하는 지 검사한다. 모든 괄호를 검.. 2022. 6. 13.
[백준] 10866 덱 - Data Structure / Java • 문제 링크 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net • 풀이 과정 Deque(양방향 Queue) 자료구조에 관련된 기본적인 동작들을 구현하는 문제. 이전에 풀이한 10828, 10845 문제 구현방식에서 switch case 조건문으로 구현하였다. 덱은 양방향에서 데이터를 처리할 수 있으므로 그와 관련된 명령어의 정확한 의미를 파악하여 구현해야한다. 덱의 앞, 뒤에 데이터를 삽입하는 명령은 각각 offerFirst(), offerLast() 로 구현, 덱의 앞, 뒤의 데이터를 삭제 및.. 2022. 6. 12.

티스토리툴바