👨🏻‍💻 PS/JAVA

[JAVA] 백준 10845번 【큐】

이번 문제는, 문제 이름 그대로 큐를 구현하는 문제이다. 저번에는 스택의 기능을 직접 구현하였는데, 큐와 스택의 차이점은 큐는 데이터가 먼저 들어온 순서대로 추출이 된다는 것이다. 스택의 pop 은 가장 최근에 들어간 데이터값이 나오는 것이고 큐의 pop 은 가장 먼저 들어온 데이터 값이 나오는 것이다. 이 문제 역시 명령 수가 10000개 이므로 10001 크기의 int 배열을 먼저 생성하였다. 그리고 stack 구현 문제와 차이점은, index를 first index 와 last index 2개를 조절하면서 구현해야한다. first index 와 last index는 0에서 시작하고, push할때마다 last index 값이 이동하면서 데이터가 채워지고 pop 할때마다 first index가 이동하면..

[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을 출력하게 하였고, 그 외는,..

[JAVA] 백준 11004번 【K번째 수】

이 문제는, BufferedReader 로 입력 받고, sort() 메서드를 쓰면 해결되긴 하지만, 정렬 알고리즘 유형 특성상, 정렬을 구현하게끔 설계해놨을 것이라 생각이 들기도 했고, 속도도 느린 것 같아 찾아보니 Quick Sort 알고리즘을 이용해서 푸는 사람들이 많았다. double pivot quick sort 라는 quick sort 의 다른 버전도 있었지만, Quick sort 자체를 처음 접해봐서, 일단 Quick Sort 를 공부해보고 코드를 작성하여 제출하였다. 오름차순 기준으로 설명해보겠다. 간단하게 설명하면, 기준 값을 하나 정하고, start index 0에서부터 기준값보다 크거나 값을 발견하고, end index 끝에서부터 기준값보다 작거나 같은 값을 발견할 시, 두수의 위치를 ..

[JAVA] 백준 11652번 【카드】

최근에, Map 사용해서 카운팅하는 메서드를 많이 작성해봤던게, 이 문제를 푸는데 도움을 주었다. 확실히, 여러 알고리즘을 풀어보는게 프로그래밍 언어의 다양한 문법들을 복습하고 배우는데 도움이 되는 것 같다. 아무튼! 수의 범위가 크므로, Map map의 키 값으로 입력되는 수를 기록할 것이고, integer 에는 횟수를 셀 것이다. Map 카운팅 자체는 크게 어려운 부분은 없지만, 가장 많이 가지고 있는 정수가 여러가지라면 작은 것을 출력해야 하므로 이 부분 조건식을 작성할 때, 주의해야한다. maxTime을 0으로 초기화 시키고, maxTime 보다 큰 횟수를 가진 key 값이 존재하면, maxKey와 maxTime을 업데이트 해준다. 만약, 어떤 키의 횟수가, 이미 등록된 maxTime과 동일하다면..

[JAVA] 백준 10989번 【수 정렬하기 3】

문제 자체는 평범한 오름차순 문제이지만, 메모리와 시간 제한이 까다로워서 곰곰히 생각해보고 문제를 풀어봤다. 요즘, 정렬 문제를 풀어보면서 StringBuilder 의 위대함을 느끼고 있어서, StringBuilder 를 이용해서 문제를 풀어보았다. 방법은 간단하다. StringBuilder 배열을 만들어서, 입력값이 1~10000이라고 했으므로, 입력되는 값을 인덱스로 지정하고 그 인덱스 값에 "\n" 을 추가해서 문자열을 append 해준 후 출력하면 된다. 참고로 String str 을 루프 안에서 선언할 경우, 메모리 초과가 일어날 수 있으니 주의해야한다. import java.io.BufferedReader; import java.io.IOException; import java.io.Input..

[JAVA] 백준 10825번 【국영수】

이제, 정렬 문제를 람다식을 사용해서 해결하는 방법을 완전히 터득한 것 같다. 그리고, 정렬 문제를 풀때마다 StringBuilder를 사용해서 출력하는 것의 엄청난 효과를 느끼는 것 같다. 웬만하면 StringBuilder를 사용해서 출력해야겠다. ㅎㅎ for each문을 사용해서 println 하는 방법과 StringBuilder에 쌓아두고 한번에 출력하는 방법 속도가 거의 2배 차이 난다...ㅎㅎ 아무튼 이 문제의 키포인트는 국어 점수는 감소하는 순서, 영어 점수는 증가하는 순서, 수학 점수는 감소하는 순서, 이름은 증가하는 순서 임을 파악하고 이에 맞는 return 값을 건네주면 된다. 참고로 이름은 String 이므로, compareTo() 메서드를 사용했다. [JAVA] Comparator 와..

[JAVA] 백준 10814번 【나이순 정렬】

이 문제도, 다른 정렬 문제와 비슷하다. 처음에, Member 클래스를 생성한 뒤, Comparable을 implements 한 다음 나이가 같다면, 맴버 아이디를 비교하고, 나이가 다르다면, 나이를 기준으로 오름차순 되게끔 compareTo()를 정의한 후 List memberList = new ArrayList(); 를 선언해서 Member 타입의 객체들을 기록한 뒤, Collections.sort()를 사용해서 정렬하였다. 그리고 출력 시, [나이 이름] 이 출력되야 하므로, toString()을 오버라이딩하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java..

[JAVA] 백준 11651번 【좌표 정렬하기 2】

이번 문제는, 이전에 풀었었던 11650 문제와 굉장히 흡사하다. [JAVA] 백준 11650번 【좌표 정렬하기】 이 문제는, 단순히 1차원 오름차순 정렬이 아닌, x좌표가 같은 경우 y좌표도 비교해야 하기 때문에, sort 함수의 정렬 조건을 변경시켜주어야 한다. [JAVA] Comparator 와 Comparable에 대해 이해하기 배열 yinq.tistory.com 다만, 차이점이 있다면, y좌표 기준으로 먼저 오름차순 정렬을 한 뒤에, y좌표가 같다면, x좌표를 비교해서 오름차순으로 비교한다는 점이다. 저번 문제에서는, Comparator 을 implements 하는 CustomComparator 객체를 만들어서 해결했었는데, 이번엔 람다 식 연습도 할 겸, 람다식을 이용해서 풀어봤다. 람다식으로..

[JAVA] 백준 11650번 【좌표 정렬하기】

이 문제는, 단순히 1차원 오름차순 정렬이 아닌, x좌표가 같은 경우 y좌표도 비교해야 하기 때문에, sort 함수의 정렬 조건을 변경시켜주어야 한다. [JAVA] Comparator 와 Comparable에 대해 이해하기 배열을 오름차순하는 가장 쉬운 방법은 Arrays 를 import 해준 뒤, Arrays의 sort 메서드를 사용하면 알아서 오름차순 정렬을 해준다! sort 메서드는 Comparable 인터페이스를 Arrays 클래스에서 구현하여 동 yinq.tistory.com 마침 최근에, 한 백엔드 스쿨 동기분 덕분에 Comparator 에 대한 이해를 한 상태라서 수월하게 해결할 수 있었다. 먼저, Arrays.sort(int [][] array) 와 같은 방식으로 sort 메서드를 사용할 ..

[JAVA] 백준 2751번 【수 정렬하기 2】

정답을 맞추긴 했지만, 시간이 비정상적으로 높은 것 같아 다양한 방법을 시도했다. 1. BufferedReader 와 Arrays.sort()를 사용한 뒤, 향상된 for문을 사용해서 BufferedWriter로 출력하게끔 답을 제출했더니 1708ms 가 나왔다. 2. BufferedReader 와 Arrays.sort()를 사용한 뒤, 일반적인 for문을 사용해서 BufferedWriter로 출력하게끔 답을 제출했더니 1472ms 가 나왔다. 향상된 for문보다 그냥 for문 루프를 돌리는게 속도가 더 빠르다는 사실을 얼떨결에 알게 되었다. 3. BufferedReader 로 입력을 받은 뒤, Arrays.sort 를 사용하고 StringBuilder를 사용해서 데이터들을 저장한 뒤, 한번에 출력하게끔..

[JAVA] 백준 11052번 【카드 구매하기】

내가 진행하고 있는 알고리즘 dp 마지막 문제이다! 이제 dp 문제는 쉽게 해결법이 떠오르는 것 같다. 역시나, dp 배열에 어떤 값을 넣어야 할지 고민하고, dp값들 사이에 관계를 맺어주는게 중요하다. dp[i] 에는 주어진 카드팩을 활용해서 i장을 살때 지불하는 최대 금액을 기록할 것이다. 보통, 예제를 보면 규칙이 어느정도 보인다. 문제에서 처럼, 4장을 뽑아야 되는 상황에서 카드 팩 배열을 cp 라고 했을 때 1장 카드 팩 = 3원 = cp[1] 2장 카드 팩 = 5원 = cp[2] 3장 카드 팩 = 15원 = cp[3] 4장 카드 팩 = 16원 = cp[4] 을 생각해보자. dp[1] 은 1장 카드팩을 사는 경우 밖에 없으므로 dp[1] = cp[1] = 3원이다. dp[2] 는 2장을 구매해야..

[JAVA] 백준 2011번 【암호코드】

이 문제는 예외상황을 빠르게 캐치하는게 중요한 문제였다. 먼저 dp배열을 어떤 조건으로 어떤 데이터를 채울지 생각을 해봐야한다. 최대 5000자리 이하의 암호가 주어진다고 했으니, dp[i]에서 i는 자릿수가 될 것이고 해당 자릿수에서 만들 수 있는 경우의 수를 기록할 것이다. 자릿수는 높은 자릿수부터 시작할 것인데, 예제문제처럼 25114가 주어졌을 때, dp[1] = [2] (1가지) dp[2] = [2,5] [25] (2가지) dp[3] = [2,5,1] [25, 1] (2가지) dp[4] = [2, 5, 1, 1] [2, 5, 11] [25, 1, 1] [25, 11] (4가지) dp[5] = [2, 5, 1, 1, 4] [2, 5, 1, 14] [2, 5, 11, 4] [25, 1, 1, 4] ..

[JAVA] 백준 2225번 【합분해】

이번 문제는 혼자 풀어서 매우 뿌듯했던 문제! 포기하지 않아서 결국 풀 수 있었다~ DP문제는 Dp배열을 어떻게 생성할지 고민하고, 이전 dp값들을 어떻게 활용할지 고민해보면 답이 보이는 것 같다. 그래도 정 안떠오르면, 경우의 수를 직접 적어보며 규칙을 찾으면 해결이 되는 것 같다. 나는 dp[][] 2차원 배열을 생각했다. 아무리 생각해도 1차원 배열로는 해결할 수 없을 것이라 판단했다. 왜냐하면 수 자체에 대한 변화도 있고 수의 갯수에 대한 변화도 생기기 때문이다. 거두절미 하고 어떻게 해결했는지 설명해보겠다! dp[i][j]에는 i를 j개로 표현하는 경우의 수를 기록할 것이다. dp[1][ ] 의 경우에는 dp[1][j] = j가 성립한다. 1을 1개로 표현할 수 있는 방법은 1 ( 1 ) 1을 ..