본문 바로가기

스택9

[자바] 프로그래머스 - 크레인 인형뽑기 게임 (Lv1, Java) 문제 : Programmers-크레인 인형뽑기 게임 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 시뮬레이션 문제에서 제시된 대로 구현만 해주면 된다. 스택 배열 자체로 구해도 문제 없으나, 로직 구성상 스택을 활용하면 더 깔끔하게 구현 가능하다 배열 자체에서 진행해도 되지만, 실수를 확실히 줄일 수 있고 더 맞는 자료구조가 있다면 그걸 쓰는게 맞다고 본다. 이 문제의 경우 각 열에 대해 스택 자료구조를 사용하고, 바구니도 스택을 사용할 시 코드 설계가 매우 깔끔해지고 실수의 여지도 많이 줄어든다. 그러니 스택을 사용해서 한번 구현해보자. 예를들어 코드상의 stk[]과 basket은 다음과 같은 스택 구조를 나.. 2022. 9. 17.
백준 1918 자바 - 후위 표기식 (boj 1918 java) 문제 : boj1918 전공자라면 과제로 한 번씩 해봤을 그 녀석이다. 후위 표기식으로 변환하는건 스택을 활용하면 된다. 실제 계산을 할 필요가 없고, 단순히 중위 표기식을 후위 표기식으로 바꾸기면 하면 되므로 실제 연산 결과를 유지하지 않아도 되서 더 쉽게 짤 수 있다(원래대로라면 'A'~'Z'도 스택에 넣어서 연산자에 따라 실제 연산이 진행되야 하지만, 이 문제의 경우 단순히 화면상에 출력만 하면 되므로). 이 문제와는 관계없지만 후위 표기식을 활용해 실제 계산해서 공학 계산기처럼 동작하는 자바 코드는 여기(깃헙)에 있다(오래전에 짠거라 좀 코드가 안이쁘긴하다). 다음과 같이 동작한다. INPUT : 23.3 * (sin3+ 2.5)/ 43.2 OUTPUT : 1.3766071245476987 INP.. 2022. 3. 31.
백준 17162 자바 - 가희의 수열놀이 (Small) (BOJ 17162 JAVA) 문제 : boj17162 mod가 최대 10^2라서 뭐 복잡한 알고리즘 필요없이 풀 수 있다. 결국 나누었을 때 0, ..., mod-1인 수가 어느 idx 위치에 있냐가 중요하다. 이걸 빨리 알 수 있으면 되는건데, mod가 10^2이니깐 대충 O(Q * mod) 정도의 시간복잡도만 가져도 풀 수 있다. 그럼 해볼만한게 많이 있다. 내 경우엔 어차피 맨 뒤에서만 수가 추가되고 빠지니 스택을 사용했다. 그리고 mod개 만큼의 스택을 마련했다. 스택배열을 arr이라고 하고, 현재 넣을 위치를 idx라고 하겠다. 그럼 각 쿼리에 대해 다음과 같이 대응할 수 있다. --- [ 쿼리 : 1 num ] arr[num % mod]에 num을 추가하고 idx++ -> O(1) [ 쿼리 : 2 ] 최대 10^2개인 a.. 2022. 3. 18.
백준 17245 자바 - 히스토그램 (BOJ 17245 JAVA) 문제 : boj17245 일단 단순화 시켜서 생각해보기 위해 좌측부터 우측으로 점차 증가하는 형태와 점차 감소하는 형태를 나눠서 생각해봤다. 1. 우선 높이(h)가 같거나 증가하는 경우이다. 이전과 비교해서 값이 같거나 증가하고 있다면, 아직까지는 넓이를 계산하는 것이 의미가 없다. n개를 모두 입력받았거나, 이후 감소하는 구간을 만나기 전까지는 넓이를 계산하지 않고 있다가 맨 마지막 지점에서만 계산해주면 된다. 직관적으로 맨 마지막 지점을 포함한 상태에서 다음과 같이 이전 높이들을 확인하면 될 것임을 예상할 수 있다. 즉, 높이가 동일하거나 증가하는 경우 맨 마지막 지점에서 이전 지점 모두 중 의미가 있는 넓이는 모두 계산할 수 있다. 2. 다음은 높이(h)가 감소하는 경우이다. 이번엔 좌측에서 우측으.. 2022. 1. 13.
백준 7585 자바 - Brackets (BOJ 7585 JAVA) 문제 : boj7585 괄호를 제외한 나머지 문자는 모두 쓸모없다. 예를들어 '예제 입력1'은 다음과 동일한 데이터이다. 이제 올바른 괄호쌍인지만 판단하면 되는데, 스택을 사용하면 간단하다. 1. 여는 괄호 (, {, [ 를 만날 시 스택에 해당 괄호를 넣는다. 2. 닫는 괄호 ), }, ] 를 만날 시 스택에서 하나를 pop한다. pop한 결과가 동일한 형태의 여는 괄호가 아닐 경우 (예를들어 ']'에서 pop을 하니 '('가 나온 경우) Illegal이다. 3. 최종적으로 1, 2의 과정을 문자열 끝까지 진행하고 스택에 남은게 아무것도 없다면 Legal, 뭐라도 남아있다면 쌍이 안맞는 것이니 Illegal이다. 코드 : github import java.io.BufferedReader; import .. 2021. 12. 11.
백준 4882 자바 - 정규형 (BOJ 4882 JAVA) 문제 : boj4882 지문에 제대로 낚였다.. 문제를 잘못이해해서 꽤 오래동안 맞왜틀 외치고 있었다. ㅠ 가장 깊은 레벨부터 AND로 지정하고, 이후 올라갈수록(레벨 숫자가 낮아질수록) AND - OR - AND - OR - ... 이렇게 지정해야 하는 문제였다. 문제 예시에서 '가장 위'가 AND라고 멋대로 생각해버린데다가 한글 번역본에서 '가장 낮은 레벨에 있는 트리는 AND 트리'라고 해버려서 당연히 '낮은' 레벨이니깐 레벨1부터 AND라고 계속 생각하고 맞왜틀 외치고 있었음 ㅡㅡ; 심지어 예제도 그렇게 풀면 다 맞다;; 결론적으로 도저히 내 코드에 문제점을 못찾겠어서 혹시나하고 영어 원본으로 보고 알아채고 맞출 수 있었다('The trees at the deepest level are AND-t.. 2021. 12. 2.
자료구조 큐, 스택, 덱 (Queue, Stack, Deque) Queue, Stack, Deque(=Double-ended Queue) 큐, 스택, 덱은 배열, 리스트와 함께 선형 자료구조에 속하는 자료구조들이다. 사실 큐, 스택, 덱의 모든 기능은 리스트(이하 '리스트'라는 단어는 모두 Linked List를 뜻함)만 사용해서도 시간복잡도 마저 동일하게 동작할 수 있다. 즉, 어찌보면 스택, 큐, 덱은 리스트에 포함되는 자료구조라고 볼 수 있다. 그럼에도 큐, 스택, 덱은 분명 리스트와는 별개의 자료구조로 정의되어 사용되고 있다. 이건 일종의 컨셉, 규칙에 해당한다고 생각한다. 술먹고 있는데 상대방이 갑자기 병따개를 준다. 병따달라는 의도를 바로 파악할 수 있다. 술먹다가 이번엔 상대방이 멀티툴을 갑자기 준다. 물론 멀티툴엔 병따개가 있다. 하지만 난 멀티툴을 받.. 2021. 10. 11.
백준 3015 자바 - 오아시스 재결합 (BOJ 3015 JAVA) 문제 : https://www.acmicpc.net/problem/3015 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/03000/BOJ_3015.java 우선 체크를 어느 방향으로 할 지 정해보자. 전 왠지 입력 다 받고 풀기보단 입력 받으면서 바로바로 풀고 싶었기에 N번째 사람을 입력받을 때 그 이전사람들을 체크해보기로 했다(입력 받으면서 바로바로 하려면 그 이후 사람에 대한 정보는 없으므로 그 이전 사람들만 가지고 생각해야한다!). 방향을 저와 같이 정했다면, 이번에 입력된 사람보다 키가 작은 이전사람은 의미가 없다는 것을 알 수 있다. (위와 같이 4명까지 확인했다. 그리고 5명째를 확인하려고 하는데, 사실 이 때 N=2와.. 2021. 10. 10.
백준 22866 자바 - 탑 보기 (BOJ 22866 JAVA) https://www.acmicpc.net/problem/22866 풀이방법을 생각하기보다는 구현이 복잡한(==귀찮은) 문제였다. 일단 3가지로 나눠서 생각해봐야 하는데, 1. 각 건물에서 좌측으로 보이는 건물의 개수 2. 각 건물에서 우측으로 보이는 건물의 개수 3. 각 건물에서 가장 가까운 건물 번호 중 작은 번호 위와 같다. 일단 '각 건물에서 좌측으로 보이는 건물의 개수' 어떻게 구할지 생각해보자. 문제에서 제시된 예시를 예시로 들겠다. 3 7 1 6 3 5 1 7 에서 좌측부터 차례로 봐보자. 1번째 건물 : 3 이다. 현재 좌측으로 보이는건 없다. 뭐 일단 어딘가에 넣어둬보자. 2번째 건물 : 7 이다. 현재 좌측으로 보이는건 없다. (7보다 높아야 보임). 그 이후로는 모두 7에 막힐것이므로.. 2021. 10. 5.

티스토리툴바