분류 전체보기242 [백준] 2792: 보석 상자 - JAVA https://www.acmicpc.net/problem/2792 풀이M가지 보석을 N명의 학생들에게 나눠주어야한다. 보석을 받지 못하는 학생이 있어도 된다. 따라서 질투심을 몇 개로 할지를 변수로 두고 이분 탐색을 했다. 질투심을 mid로 했을 때 보석을 받는 학생의 수가 N보다 작으면 정답이 될 수 있다. N보다 크면 left를 mid + 1로, 그렇지 않으면 right를 mid - 1로 좁혀가면서 탐색한다. 메모리: 34892KB시간: 356ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Buffer.. 2024. 5. 18. [백준] 7578: 공장 - JAVA https://www.acmicpc.net/problem/7578 풀이A열과 B열에 같은 숫자들을 연결할 때, 케이블들이 서로 교차하는 부분의 개수를 세는 문제이다. A열: 1 2 3 4 5 B열: 2 4 1 3 5 위와 같이 주어졌을 때, B열에서 A열로 줄을 쏴주었다. B열의 2에서 A열의 2로 줄을 쐈을 때, A열의 2보다 오른쪽에 이미 연결된 점이 있다면 그 점이 교차하는 점이다. B열은 앞에서부터 순서대로 보는데, A열의 연결된 점 오른쪽으로 연결된 점이 있다는 것은 B열의 앞쪽 점과 연결되어 있다는 것이므로 교차한다는 것이다. A열의 인덱스를 저장해주었고, B열의 점이 A열의 어떤 인덱스와 연결되는지 저장했다. 세그먼트 트리를 이용해 A열의 인덱스부터 N까지 구간합을 구해 교차점이 몇개인지 구.. 2024. 5. 18. [백준] 10868: 최솟값 - JAVA https://www.acmicpc.net/problem/10868 풀이N개의 정수 배열의 a~b구간에서의 최솟값을 찾아야 한다. 세그먼트트리를 만들어 구간별로 최소값을 갖는 배열의 인덱스를 저장했다. a~b구간에서 최솟값의 인덱스를 찾아 배열의 값을 출력하면 된다. 인덱스를 저장하지 않고 최솟값 자체를 세그먼트트리에 저장하는 것도 좋다. 메모리: 48788KB시간: 600ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class SegmentTree { int[] tree; int treeSize; public SegmentTree(int arrSize) { .. 2024. 5. 18. [프로그래머스] 표 병합 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이union-find를 이용한 구현 문제였다. MERGE명령에 대한 설명을 읽고 union-find를 사용해야겠다고 생각했다. 병합된 셀의 어느 위치를 선택하더라도 병합된 셀로 접근한다는 부분에서 union-find에서 find를 해야겠다는 생각이 들었다. parent 배열을 1차원으로 만들기 위해 2501사이즈의 배열로 만들었다. 표의 크기가 50X50이기 때문에 (r,c)의 좌표를 (r-1)X.. 2024. 5. 18. [백준] 13701: 중복 제거 - JAVA https://www.acmicpc.net/problem/13701 풀이정수를 입력받으면서 부른적이 없는 정수만 출력하는 문제이다. set자료구조를 생각했지만 메모리 제한때문에 비트마스킹으로 풀어야한다. N의 범위는 2^25로 주어져있다. int범위는 32bit까지 담을 수 있기 때문에 32개의 숫자를 중복검사할 수 있다. 따라서, 2^25개의 수를 중복검사하려면 2^20크기의 배열을 만들어 배열의 원소 한 개가 32개의 숫자를 중복검사하도록 구현해야 한다. `int[] number = new int[1 메모리: 350208KB시간: 1388ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void.. 2024. 5. 18. [프로그래머스] 양과 늑대 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이늑대의 수가 양의 수 이상이 되면 양들이 다 잡아먹혀서 안된다. 트리의 0번부터 시작해서 양을 늑대보다 많게 하면서 돌아다닌다. 이때 양의 최댓값을 찾아야한다. 이동이 가능한 노드들을 담는 리스트를 만들었다. 특정 노드를 방문 할 때 그 노드의 자식 노드를 리스트에 담고, 해당 노드는 제거해주었다. 이동가능한 리스트를 들고 dfs탐색을 통해 최댓값을 갱신했다. 리스트에서 노드를 제거할 때 Conc.. 2024. 5. 18. [트러블슈팅] ConcurrentModificationException 내용private static void dfs(int node, List next, List> list) { next.removeIf(item -> item == node); for (int nextNode : list.get(node)) { next.add(nextNode); } for (int nextNode : next) { dfs(nextNode, next, list); }} Exception in thread "main" java.util.ConcurrentModificationException at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:10.. 2024. 5. 18. [백준] 2517: 달리기 - JAVA https://www.acmicpc.net/problem/2517 풀이N명의 선수의 실력을 입력받는다. 입력을 받는 순서대로 해당 위치에 있다고 할 때, 실력이 자기보다 안좋은 선수가 앞에 있으면 역전할 수 있다. 예를들어 실력이 2, 8, 10으로 주어졌다면 8실력을 가진 선수는 앞에 자기보다 낮은 실력의 선수 1명이 있으므로 이 선수가 할 수 있는 최선의 등수는 1등이다. 10인 선수는 앞에 2명을 앞지를 수 있으므로 최선의 등수는 1등이 된다. 세그먼트 트리를 이용하여 실력을 tree의 인덱스로 하여 1늘린다. 1부터 자신의 인덱스까지 구간합을 구하면 자신과 자신보다 실력이 낮은 선수들의 합이 된다. 구간합과 입력받은 순서를 이용하여 최선의 등수를 계산할 수 있다. 각 선수의 실력은 모두 다르므로 .. 2024. 5. 18. [프로그래머스] 카드 짝 맞추기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/72415 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이4 X 4 크기의 보드에 카드를 뒤집어 짝을 맞춰서 제거해야 한다. 카드 짝이 맞게 2개씩 위치를 저장해놓았다. 순열을 통해 제거할 카드 번호의 순서를 정해놓았다. 정해놓은 순서대로 제거해서 최소 이동을 계산하여 정답을 갱신했다. 메모리: 74.5MB시간: 1.17ms언어: Java 11import java.util.*;class Solution { static class Node { .. 2024. 5. 18. [프로그래머스] 파괴되지 않은 건물 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이N X M 크기의 영역이 주어지고, 각 영역을 사각형 크기의 영역을 정해 일정 수를 더하고 빼주게 된다. 누적합을 이용하는 문제였다. (a, b) 부터 (c, d) 까지의 사각형에 5씩 더해주기 위해서는arr[a][b] += 5arr[a+1][b+1] += 5arr[a][b+1] -= 5arr[a+1][b] -= 5위처럼 더해주면 된다. 이렇게 수를 저장한 뒤 행마다 왼쪽에서 오른쪽으로 누적합해주.. 2024. 5. 18. 이전 1 ··· 5 6 7 8 9 10 11 ··· 25 다음