풀이 방법 문제에서 중복을 뺀다는 걸 본 순간 Set이 생각났다. 그래서 Set에 입력값을 넣어주고 ArrayList를 Set 데이터 기반으로 만들어 sort를 이용해 오름차순 정렬하였다. 사용 개념 Set Set을 ArrayList로 sort 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 package Sort; //BOJ 10867 중복 빼고 정렬하기 import java.io.*; import java.util.*; public class Main { public static void main(String args[]) throws IOException { BufferedReade..

풀이 방법 comparable과 comparator를 이해하고 문제를 풀어 쉽게 풀렸다. 이 문제를 풀면서 느낀 점은 comparator를 익명 클래스로 사용하여 문제를 해결한다면 더욱 간결하게 풀 수 있다. 그래서 둘 중 어느 방법이 더 간단한지 문제에 따라 다르기 때문에 잘 생각하고 선택해야 한다. 사용 개념 comparator 익명 클래스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 package Sort; //BOJ 11651 좌표 정렬하기 2 import java.io.*; import java.util.*..

풀이 방법 comparable과 comparator를 모두 사용하여 문제를 해결해보았다. comparator를 사용할 때는 sort메소드에 comparator 클래스 참조 변수를 만들어서 인자로 넣어줘야 하고, comparable를 사용할 때는 sort메소드에 인자로 넣어주지 않아도 된다. 왜 이러는지 공부를 해보아야겠다. 둘의 차이가 무엇인지 잘 모르겠다. comparator를 구현하는 방법은 익명 클래스 또는 클래스 하나를 만들어 comparator를 구현하는 방법이 있고, comparable은 클래스에 바로 구현해서 오버라이딩 하면 되는 것 같다. 사용 개념 comparable comparator 코드1 comparator 사용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..

풀이 방법 답을 처음 작성했을 때, 코드 1처럼 작성을 했다. 문자 입력에 따라 index값을 변화시켜 커서를 움직이는 식으로 했다. 그러나 그렇게 하게 되면, 문자를 삭제하고 list안에서 재배열될 때 O(n)이 나오게 되고, 이것을 반복하게 되면 O(n^2)로 총 명령어가 500,000개 이므로 500,000^2가 되어 시간 초과가 나온다. 그래서 stringbuilder도 사용했지만, 계속해서 시간 초과가 나와 힌트를 얻기 위해 구글링을 했다. 시간 초과를 피하기 위해서 사용한 방법은 왼쪽 스택, 오른쪽 스택을 구현하는 것이었다. 스택에서의 push, pop은 시간 복잡도가 O(1)이어서 n번 반복하면 O(n)이 되기 때문에 시간 초과가 나오지 않는다. 솔직하게 힌트를 보지 않았다면 이 문제는 풀 ..

풀이 방법 이 문제를 읽어보고 오버 라이딩을 하지 않은 sort 메소드를 사용하기엔 부족한 점이 있다고 생각했다. 왜냐하면 문자열의 길이에 따라 먼저 오름차순으로 정렬한 뒤, 길이가 같으면 사전 순으로 정렬하기 때문이다. 그래서 comparator를 사용하여 compare를 오버 라이딩하여 sort 메소드를 재정의하고 정렬하였다. 그리고, 중복된 단어가 있을 경우 한 번씩만 출력한다고 했으므로 set을 사용하였고, Set을 다시 ArrayList로 변환시켜서 정렬시켰다. 사용 개념 comparator, set, arraylist 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ..

백준 문제를 풀다가 문자열 정렬이 나와 comparable과 comparator 공부를 하게 되었다.그래서 comparable과 comparator의 정확한 개념은 구글링을 해도 많이 나오기 때문에 나는 알고리즘 문제를 풀면서 적용할 수 있게끔, 나중에 내가 다시 봐도 이해할 수 있게 글을 써보았다. comparator 인터페이스 백준 문제를 풀다가 문자열 정렬이 나와 comparable과 comparator 공부를 하게 되었다. comparator은 java.util 패키지에 포함되어 있는 인터페이스이다. comparator는 comparable과 다르게 일반적인 기준이 아닌 특정 기준을 사용할 때 필요하다. comparator의 메소드는 compare( o1, o2)이다. comparator 활용 나..

풀이 방법 이 문제를 풀면서 처음에 이진 탐색과 upperbound에 대해 생각하면서 풀었다. 왜냐하면 index를 바꿔야 하는 줄 알고 문제를 해석했다. 그래서 시간 복잡도가 50^50까지 생각되어 이분 탐색을 생각했다. 그러나 문제를 다시 읽어보니 최솟값만 구하면 되는 것이었다. 그래서 A와 B 배열을 정렬한 뒤에, A의 첫 번째 index, B의 마지막 index 순차대로 곱하면서 더해주어 문제를 해결했다. 사용 개념 Arrays.sort 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 package Data_Structure; import java.io...

풀이 방법 덱의 메소드를 알면 쉽게 풀 수 있는 문제이다. 사용 개념 덱 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 package Data_Structure; //BOJ 10866 덱 // https://c-king.tistory.com/ /* 덱의 메소드를 알면 쉽게 풀 수 있는 문제이다. */ import java.io.BufferedReader; import java.io.IOException; import ..

풀이 방법 컬렉션 큐를 사용하고 풀고 있었는데, back이 가장 뒤에 있는 정수를 출력하라고 해서 pollLast가 있는 덱으로 바꾸어 풀었다. 큐는 이러한 메소드도 없고, 인덱스도 존재하지 않아 back을 출력하는데 어려움이 있다고 생각이 들었다. 그래서 덱을 사용하였다. 사용 개념 덱, 큐 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 package Data_Structure; //BOJ 10845 큐 //https://c-king.tist..

풀이 방법 자바 컬렉션을 사용하지 않고, 배열을 사용하면서 size를 조절하며 메소드를 구현하며 문제를 해결했다. 이 문제는 스택에 관련 메소드를 구현 연습을 할 수 있었다. 스택의 개념이 무엇인지만 알지, 메소드를 한번 더 구현함으로써스택을 더 정확히 알게된 문제였다. 사용 개념 스택 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 ..

Queue 인터페이스를 구현하는 클래스 큐를 구현하는 클래스는 여러 가지가 있지만 대부분 사용하는 것은 LinkedList, ArrayDeque라고 생각한다. 일반적인 큐를 사용할 경우 LinkedList를 사용한다. 하지만 자바 api에서는 큐를 사용할 때 LinkedList를 사용하는 것보다 ArrayDeque를 사용하는 것이 더 빠르다고 한다. 성능 테스트한 것을 보았는데 ArrayDeque가 더 빠르고, 그다음으로 LinkedList가 빨랐다. Queue 특징 큐는 스텍과 다르게 FIFO 형태를 가진다. 먼저 들어온 데이터가 가장 먼저 나가는 구조이다. Queue 공통 메소드 boolean offer(E e) - 큐에 데이터를 추가한다. E peek() - 첫번째로 저장된 값을 리턴한다. 그러나 ..

풀이 방법 앞의 수 정렬하기 2와 매우 유사한 문제이다. 다른 점이 있다면 중복되는 숫자가 있다. 그래서 count배열을 이용할 때 boolean을 사용할 수 없고, int형을 사용하여 해당 숫자를 index, 숫자 개수를 해당 index 값으로 입력받는다. 그래서 해당 index의 값이 0이 될 때까지 index를 출력하게 된다. 사용 개념 카운팅 정렬 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 package Sort; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRea..