해시를 사용한 집합과 맵4 [백준] 2015: 수들의 합 4 - JAVA https://www.acmicpc.net/problem/2015 풀이주어진 수열에서 부분 수열의 합이 k가 되는 경우를 찾는 문제이다. 누적합과 맵을 이용해 해결했다. ```sum[i]```에서 k를 뺀 값이 이전에 등장한 적이 있는지를 확인한다. 현재 누적합이 ```sum[i]```라고 할 때, ```sum[i]-k```가 이전에 등장한 적 있다면 그 구간의 합이 k라는 것을 의미한다. 메모리: 33452KB시간: 348ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br =.. 2024. 6. 10. [백준] 2179: 비슷한 단어 - JAVA https://www.acmicpc.net/problem/2179 풀이영단어들이 주어지고 두 단어를 앞에서부터 비교하여 공통적으로 나타나는 부분의 길이가 긴 두 단어를 출력해야한다. 한글자씩 비교하기 위해 트라이 알고리즘을 생각했으나, 시간이 충분하고 메모리 제한이 작아서 트라이를 사용하지 않았다. 길이가 같을 경우 주어진 순서대로 앞쪽에 있는 단어가 답이되므로 순서 유지가 되는 ArrayList를 선택했다. ArrayList에 단어를 담고 앞에서 부터 순서대로 비교하여 접두사의 길이와 인덱스를 저장했다. 메모리: 19328KB시간: 2008ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void .. 2024. 5. 17. [백준] 1525: 퍼즐 - JAVA https://www.acmicpc.net/problem/1525 풀이3x3 표의 퍼즐을 맞추는데 최소 이동 횟수를 구하는 문제였다. 빈칸은 0으로 주어지고 0의 상하좌우에 있는 숫자를 0위치로 이동시킨다. 0을 기준으로 상하좌우를 탐색하여 숫자를 바꿔주고, 그렇게 만들어진 배치를 방문처리하였다. 이때 방문처리를 String으로 하였는데, 메모리제한때문이었다. 숫자들을 이어붙여 String으로 만들었고, String의 indexOf 메서드를 이용하여 위치를 찾아 좌표를 구했다. Map에 String과 이동횟수를 저장하며 방문처리를 해줬고, "123456780"이 된다면 퍼즐의 완성이므로 Map에서 이동횟수를 꺼내어 출력했다. 메모리: 122456KB시간: 1048ms언어: Java 11import ja.. 2024. 5. 15. [백준] 2143: 두 배열의 합 - JAVA https://www.acmicpc.net/problem/2143 풀이배열 2개가 주어지고 배열들의 부 배열들을 합하여 T를 만들는 경우의 수를 찾는 문제이다. 두 가지 방법으로 풀 수 있는 문제였다. 첫 번째로 생각한 방법은 Map을 사용해 containsKey를 이용하는 방법이었다. 배열 A의 부 배열들의 합을 map에 저장해 놓는다. 배열 B의 부 배열의 합을 구하면서 T에서 뺀 값이 A의 map에 있다면 map의 value 만큼 카운트하여 더해준다. 이 방법으로 제출하고 다른 풀이들을 보니 이분 탐색으로 푸는 방법도 있었다. List에 부 배열들을 저장하고 이분 탐색을 위해 정렬한다. ListA에서 값을 꺼내면서 T - 꺼낸 값을 찾을 값으로 하여 ListB에서 이분탐색을 통해 찾는다. 개수가 여.. 2024. 5. 12. 이전 1 다음