본문 바로가기

알고리즘/알고리즘 설명61

20230829 [Java] 문제풀이 20230829 [Java] 문제풀이 [프로그래머스] 양궁대회 아직 백트래킹, 완전 탐색이 많이 약한 것 같다 (그래도 전보다 어느 정도 생각을 할 수 있게 되었다) 먼저 shoot을 통해서 n번 동안 라이언이 쏠 수 있는 모든 경우를 배열로 구한다 그리고 compare을 통해서 라이언과 아파치가 맞춘 과녁을 비교하면서, 두 명의 점수를 비교해준다 import java.util.*; class Solution { public static int[] answer; public static int maxDif = 0; public static int[] lionArrow = new int[11]; public void shoot(int s, int limit, int[] info) { if (s == lim.. 2023. 8. 29.
20230828 [Java] 문제풀이 20230828 [Java] 문제풀이 [프로그래머스] 전력망을 둘로 나누기 1부터 n까지의 전력망이 있고, 모두 연결이 되어 있다 하나의 연결 선을 끊고 둘로 나누면서, 두 개의 연결되어 있는 노드 그룹의 차이 중, 제일 적은 차이를 출력한다 DFS를 통해서, Union Find를 사용했고, 하나의 그룹에 몇 개의 노드가 있는지 찾았다 연결선 하나만 자르게 되면, 어차피 2개의 그룹으로 나뉜다 (n - nodeCount) - nodeCount 를 통해 두 그룹의 노두 개수의 차이를 구했다 import java.util.*; class Solution { public int dfs(ArrayList wr, int[] visited) { Stack stack = new Stack(); int count = .. 2023. 8. 28.
20230822 [Java] 문제풀이 20230822 [Java] 문제풀이 [프로그래머스] 혼자 놀기의 달인 상자에 카드를 넣고 무작위로 섞어 일렬로 나열한다 그리고 상자를 1번부터 순차적으로 증가하는 번호를 붙인다 상자 번호에서, 카드 번호를 보고, 카드 번호에 대한 상자 번호를 여는 것이다 인덱스를 상자 번호라고 생각하면 카드 번호에 1을 항상 빼야한다 import java.util.*; class Solution { public int solution(int[] cards) { ArrayList group = new ArrayList(); int[] visited = new int[cards.length]; for (int i = 0; i < cards.length; i ++) { int tempCount = 0; if (visited.. 2023. 8. 22.
20230821 [Java] 문제풀이 20230821 [Java] 문제풀이 [프로그래머스] 두 큐 합 같게 만들기 이 문제는 두 큐가 주어지고, 서로의 원소를 주고 받으면서, 서로의 원소들의 값이 같을 수 있도록 만드는 것이다 제일 주의해야할 점은, 두 개의 큐가 있다는 것이다 서로 원소를 주고 받을 때에, 제일 먼저 큐에 들어온 원소를, 다른 큐에게 전달할 수 있다는 점이다 각 두 큐의 값을 구하고, 그 값에 따라, 값이 더 큰 큐에서, 더 작은 큐에게 원소를 주는 방식으로 로직을 짜면 된다 while문이 무한 루프에 빠질 수 있는 상황이 있어서, answer가 나올 수 있는 최대의 수를 정해준다 (answer > queue1.length * 4) 두 개의 큐의 합이 같으면, 바로 answer를 출력해준다 answer는 원소의 움직임의 개.. 2023. 8. 21.
20230819 [Java] 문제풀이 20230819 [Java] 문제풀이 [프로그래머스] 할인 행사 HashMap에 원하는 제품과, 그 수량을 넣는다 그리고 10일 단위로, Discount를 순회하면서, HashMap에 있는 제품과 동일한 제품이 있으면 하나씩 빼준다 즉 10일 단위로 갱신이 될 때마다 새로운 HashMap을 가지고 와야 한다 그래서 copy 라는 메서드를 따로 만들었다 그렇게 10개를 모두 살 수 있으면 answer에다가 1을 누적시키면 된다 제발 문제를 잘 읽자!!!!!!! import java.util.*; class Solution { public static HashMap copy(HashMap list) { HashMap newList = new HashMap(); for (String key : list.key.. 2023. 8. 19.
20230817 [Java] 문제풀이 20230817 [Java] 문제풀이 [프로그래머스] 귤 고르기 해쉬맵으로 문제를 풀었다 해쉬맵에 귤 사이즈를 key, 사이즈에 대한 개수를 value로 넣었다 value기준으로 최소한의 종류를 구했다 (value를 배열에 넣고 내림차순으로 정렬했다) import java.util.*; class Solution { public int solution(int k, int[] tangerine) { int answer = 0; HashMap map = new HashMap(); ArrayList array = new ArrayList(); for (int num : tangerine) { if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else.. 2023. 8. 17.
20230816 [Java] 문제풀이 20230816 [Java] 문제풀이 [프로그래머스] 디펜스 게임 첫 풀이는 71.9 로, 시간 초과 때문에 실패를 했다 2 중 for문으로, slicing을 하고, 정렬을 하면서 앞의 숫자 위주로 더하면서 정답을 구했다 import java.util.*; class Solution { public int solution(int n, int k, int[] enemy) { int answer = 0; if (k == enemy.length) return k; if (k > enemy.length) return enemy.length; for (int i = enemy.length; i >= k; i--) { int[] newEnemy = new int[i]; int tempAdd = 0; int temp.. 2023. 8. 16.
20230815 [Java] 문제풀이 20230815 [Java] 문제풀이 [프로그래머스] 택배 배달과 수거하기 기본적으로 뒤에서부터 택배를 수거 또는 배달해야, 최소 이동 거리를 구할 수 있다 뒤에서부터 천천히 수거 또는 배달의 개수를 순회한다 deliver 또는 pickup의 개수가 음수일 경우 트럭에 택배를 실을 공간이 있다는 것이다 반대로 양수일 경우에는 해당 지점을 while문을 통해 계속 왕복을 해야 한다 (해당 지점에서 택배를 다 처리할 때까지, 즉 음수가 될 때까지) class Solution { public long solution(int cap, int n, int[] deliveries, int[] pickups) { long answer = 0; long deliver = 0; long pickup = 0; // 뒤에서.. 2023. 8. 15.
20230804 [Java] 문제풀이 20230804 [Java] 문제풀이 [프로그래머스] 무인도 여행 DFS만 잘 구현하면 쉽게 풀 수 있는 내용이었다 일단 방문처리를 하면서 섬을 탐색하면서 count에다가 maps에 있는 숫자들을 더해주면 된다 import java.util.*; class Solution { public static int[] dr = {-1, 0, 0, 1}; public static int[] dc = {0, -1, 1, 0}; public static String[][] realMap; public static int[][] visited; public static int count; public static int dfs(int row, int column) { for (int i = 0; i < 4; i++) .. 2023. 8. 4.