개발놀이터

이번 포스팅은 기존 Map 인터페이스의 구현체 중 thread-safe 하다고 알려져있는 바로 그 구현체 ConcurrentMap입니다. 앞선 포스팅인 Map에 대한 기본적인 내용과 지금 쓰려는 이 내용은 지식의 깊이부터 다르기 때문에 성격이 맞지않다고 판단하여 따로 분리하여 포스팅하였습니다. 들어가기에 앞서 Map은 자바 컬렉션 중에서 가장 대중적으로 사용하는 것 중 하나입니다. 그리고 그 중 가장 많이 사용하는 HashMap은 thread-safe 하지 않은 구현체입니다. java 1.5 이전 (ConcurrentMap이 나오기 전) 에는 Hashtable이라는 클래스를 많이 사용했습니다. Hashtable은 HashMap과 다르게 멀티스레드 환경에서 thread-safe를 보장합니다. 하지만 Has..

오늘은 알고리즘 문제에서도 많이 사용하고 실전에서도 많이 사용한다고 알려져있는 Map에 대해서 알아보도록 하겠습니다. Map 맵은 사전과 비슷합니다. people이란 단어에 "사람", baseball이란 단어에 "야구" 라는 뜻이 부합되듯이 Map은 Key와 Value라는 것을 한 쌍으로 갖는 자료구조입니다. Map은 리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고 Key를 통해서 Value를 얻습니다. Map의 가장 큰 특징은 Key로 Value를 얻어낸다는 것입니다. people이라는 단어의 뜻을 찾기 위해서 사전의 내용을 순차적으로 검색하는 것이 아니라 해당 단어가 있는 곳만을 펼쳐보는 것이죠. 우리가 잘 아는 Map은 List와 마찬가지로 인터페이스입니다. Map인터페이스를 구현한 Has..

3장의 주요 개념은 역시 Two Pointers Algorithm (이하 투 포인터 알고리즘) 이다. 대부분의 문제는 투 포인터 알고리즘을 적용하면 간단하게 풀 수 있는 문제이다. 그 중에서 투 포인터 알고리즘의 변형 문제인 Sliding Window (이하 슬라이딩 윈도우) 를 익히면 완벽할 것 같다. 하지만 3-6. 최대 길이 연속 부분수열 문제를 다시 한번 확인할 필요가 있다. https://coding-review.tistory.com/275 3-6. 최대 길이 연속 부분수열 package 배열응용3장.최대길이연속부분수열3다시6.my; import java.util.Scanner; public class Main { /** * -내 풀이- * 0을 1로 바꾸는 작업을 하는 것에 초점이 맞아서 풀지..

package 배열응용3장.최대길이연속부분수열3다시6.my; import java.util.Scanner; public class Main { /** * -내 풀이- * 0을 1로 바꾸는 작업을 하는 것에 초점이 맞아서 풀지 못했다. * * -피드백- * 0과 1로 바꾸는 작업 없이 start 와 end 와의 거리를 구하면 되는 것이다. * 또한 cnt 라는 개념을 추가하여 arr[end] == 0 이면 cnt++ * 그리고 while (cnt > k) 로 cnt > k 인 상황에서 start 를 조정 (여기서 k 는 0을 1로 바꿀 수 있는 최대 횟수) * arr[start] == 1 이면 단순 start++ arr[start] == 0 이면 cnt-- 하면서 start++ */ public stati..

package 배열응용3장.연속된자연수의합3다시5.my; import java.util.Scanner; public class Main { /** * 이전 문제와 완벽히 동일 피드백 X */ public static void main(String[] args) { Scanner kb = new Scanner(System.in); int input = kb.nextInt(); int[] arr = new int[input]; for (int i = 0; i < input; i++) { arr[i] = i + 1; } System.out.println(solution(arr, input)); } private static int solution(int[] arr, int input) { int answer ..

package 배열응용3장.연속부분수열3다시4.my; import java.util.Scanner; public class Main { /** * -내 풀이- * two pointers algorithm 을 이용해 풀었는데 내 코드가 더 깔끔한 것 같다. 선생님의 코드는 너무 복잡함 * 피드백할 것은 없다. */ public static void main(String[] args) { Scanner kb = new Scanner(System.in); int n = kb.nextInt(); int m = kb.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = kb.nextInt(); } System.out.println(so..

package 배열응용3장.최대매출3다시3.my; import java.util.Scanner; public class Main { /** * -피드백- * sliding window 알고리즘을 이용하여 풀면 된다. * sliding window 는 two pointers algorithm 을 이용한 문제지만 딱히 two pointers algorithm 을 이용하지 않아도 된다. * 선생님의 풀이처럼 for 문 하나를 가지고 풀어도 된다. * * -선생님 풀이- * ex) 10개의 값을 3개만큼 합해서 최댓값을 구해야 한다면 * 1 2 3 4 5 6 7 8 9 10 * | | * | | * | | * 이렇게 칸을 이동시키면 된다. 즉, 앞에건 빼주고 뒤에건 더해주면 된다. * for (int i = k..

package 배열응용3장.공통원소구하기3다시2.my; import java.util.ArrayList; import java.util.Scanner; public class Main { /** * -내 풀이- * 도저히 생각이 나지 않아서 포기했다. * * -선생님 풀이- * 이번에도 two pointers algorithm 을 사용한 문제였다. * 이번에 눈여겨 볼 점은 어떤 배열을 오름차순으로 정렬하기 위해서는 Arrays 클래스의 sort 메서드를 사용하면 된다는 것과 * 교집합을 찾는 문제이기 때문에 p1 과 p2 가 같은 경우 p1, p2 둘을 동시에 증가시켜야 했다는 점이다. * * 그리고 p1 과 p2 중 작은 쪽을 하나 증가시켜야 한다는 점도 인상깊었다. * * int p1 = 0, p2..

package 배열응용3장.두배열합치기3다시1.my; import java.util.Scanner; public class Main { /** * -내 풀이- * 이중 for 문을 돌면서 각각의 숫자를 비교한 후 최솟값을 넣는 방향으로 진행했다. * 거기에 배열 두개를 그냥 새로운 배열로 만들어서 풀었다. * * --피드백-- * 두개의 정렬된 배열을 하나의 배열로 만드는 것이 아니라 각각의 배열에서 포인터를 도입해 비교하면 된다. * 그리고 문제를 잘못 이해하여 입력받은 두 배열은 정렬된 상태라는 것을 눈치채지 못했다. * * -선생님의 풀이- * two pointers algorithm 을 이용해 풀면 간단하게 풀린다. * * pt1 = 0, pt2 = 0; * while (pt1 < n && pt2..

Two-Pointers-Algorithm two pointers algorithm (이하 투 포인터 알고리즘) 알고리즘은 말 그대로 포인터를 사용해 배열에 쉽게 접근할 수 있게 해줍니다. 자바에서도 배열에 쉽게 접근하기 위해 포인터를 사용하는 경우가 종종 있습니다. 보통 lt (left), rt (right) 혹은 s (start), e (end) 혹은 p1, p2 이런식으로 포인터를 정해서 값을 하나씩 증가시키면서 배열을 참조합니다. 투 포인터 알고리즘을 사용하는 문제는 비교적 자주 만나볼 수 있으며 한번 익혀두면 나중에 써먹기 정말 편하다고 합니다. 물론 저는 세번밖에 안써봤습니다. 먼저 문제를 확인해보시죠 문제를 해석하자면 N개로 된 수열에서 N개의 부분집합 중에서 M이 되는 개수가 몇개냐라고 물어..