본문 바로가기

자바144

20230709 [Java] 문제풀이 20230709 [Java] 문제풀이 [프로그래머스] 요격 시스템 미사일이 떨어지는 개구간이 targets라는 2차원 배열로 주어진다 이 미사일을 요격하기 위해, 필요한 요격 미사일의 개수의 최솟값을 구하는 것이다 일단 각 미사일의 개구간 중, 끝 부분을 기준으로 오름차순으로 정렬을 한다 그렇게 정렬을 하고 난 후에, 현재 공격 받는 미사일의 개구간의 시작점과, 그 전의 공격 받았던 미사일의 개구간의 마지막 지점이 완전히 겹치면, 한번에 요격을 할 수 있다 [3, 6] , [4, 7] : 두 미사일을 한번에 요격할 수 있음 [3, 6], [6, 8] : 두 미사일을 요격하려면 두 개의 요격 미사일이 필요함 [3, 6], [7, 9] : 두 미사일을 요격하려면 두 개의 요격 미사일이 필요함 // ==== .. 2023. 7. 9.
20230708 [Java] 문제풀이 20230708 [Java] 문제풀이 [프로그래머스] 체육복 체육복을 도난 당한 학생들의 배열과, 여벌이 있는 학생들의 배열이 주어진다 여벌이 있는 학생은, 도난당한 학생에게 체육복을 빌려줄 수 있다 단 도난 당한 학생은, 자신보다 1 아래 또는 1 위에 있는 학생의 체육복을 빌릴 수 있다 여벌이 있지만, 체육복을 도난 당했다면 (그 학생은 다른 학생에게 체육복을 빌려줄 수 없게 된다) 일단 새로운 배열을 만들었다 학생들의 번호를 인덱스로 넣었다 (-1을 해줌) 그리고 값은 -1 : 도난 당함 0 : 자기 자신의 체육복만 있음 1 : 여벌이 있는 학생 그리고 이 배열을 순회하면서, 도난 당한 학생의 index - 1 또는 index + 1의 값이 1이라면 1을 더해준다 더해줬다는 것은, 체육복을 빌렸다는.. 2023. 7. 8.
20230707 [Java] 문제풀이 20230707 [Java] 문제풀이 [프로그래머스] 완주하지 못한 선수 완주하지 못 한 선수를 찾는 것이다 참여는 했지만, 끝내지 못 한, 한 사람을 찾으면 된다 참여한 사람들의 이름을 marathon 이라는 HashMap에 넣고, value는 +1을 해준다 같은 이름이 있을 수 있다 completion에서, 이름이 나올때마다, value에 -1을 해준다 동명인이 없으면 모든 value는 하나 빼고 0일 것이다 동명인이 있을 수 있어 -1만 해주는 것이다 0이 아니면 그 사람이 완주를 못 한 선수다 import java.util.*; class Solution { public String solution(String[] participant, String[] completion) { HashMap ma.. 2023. 7. 7.
[Java] 알고리즘 백트래킹 [Java] 알고리즘 백트래킹 백트래킹 DFS와 백트래킹이 다른점 DFS는 가능한 모든 경우의 수를 탐색을 한다 (그래서 시간이 많이 걸린다) 백트래킹은 탐색을 하다가, 불필요한 탐색이라고 생각하면, 다른 루트를 탐색을 한다 백트래킹에서는 얼마나 가지치기를 잘 하느냐가 제일 중요하다 용어 유망 (Promising) : 목표의 값이 될 가능성이 있다는 것 가지치기 (Prunning) : 목표의 값이 될 수 있는 가능성이 없어, 해당 노드를 제외 백트래킹 (Backtracking) : 유망하지 않는 쪽으로 가지 않고 다시 돌아오는 것 void dfs(int cnt, int idx) { // 현재까지의 결과, 탐색을 진행할 인덱스 // r개를 선택한 경우 if(cnt == r) { // 결과 처리 후 현재 가.. 2023. 7. 7.
20230706 [Java] 문제풀이 20230706 [Java] 문제풀이 [프로그래머스] 신규 아이디 추천 그냥 1단계부터 7단계까지, 구현을 하라고 문제에서 나온 대로, 코드를 작성했다 특히 아스키 코드를 많이 썼고, 그리고 문자열 슬라이싱을 많이 사용했던 것이 특이점이다 다른 분의 코드 (정규 표현식 사용하기) .toLowerCase() : 이것을 사용해서 대문자를 소문자로 바꾸기 replaceAll() : 문자열에서 변경할 점들을 바꾸기 .replaceAll("[.]{2,}", "."); => '.' 이 2개 이상이면 '.' 하나로 바꾸기 .replaceAll("^[.][.]$", ""); => 앞뒤에 '.'이 있으면, 없애기 import java.util.*; class Solution { public String solution(.. 2023. 7. 6.
[Java] 알고리즘 다이나믹 프로그래밍 [Java] 알고리즘 다이나믹 프로그래밍 다이나믹 프로그래밍 큰 문제를 작은 문제로 쪼개서 앞에 저장을 하고, 해결해 나가는 것이다 피보나치 수열 예시) 1, 1, 2, 3, 5, 8, 13, 21 - 이렇게 순서대로 공식대로 계산을 하면서 문제를 해결하는 방식이 있다 (시간이 오래 걸릴 수 있다) f(1) f(2) f(3) f(4) f(5) f(6) f(7) f(8) f(9) f(10) 1 1 2 3 5 8 13 21 34 55 위와 같이 f(10) 까지 저장이 되어 있으면, f(11)을 구할 때 f(1)부터 다시 구하는 것이 아니라 f(9)와 f(10)만 찾아서 더해주면 된다 피보나치 수열을 구할 때에, 재귀를 사용할 때에는, 위와 같이 A zone과 B zone 모두 작동하게 된다 즉 B zone에.. 2023. 7. 6.
20230705 [Java] 문제풀이 20230705 [Java] 문제풀이 신고 결과 받기 k번 이상 신고를 받은 사람은 게시판 이용이 정지된다 한 사람이, 특정한 사람 한 명을 계속 신고해도, 한번 신고한 것과 같다 set을 이용하여, 한 사람이 특정 한 사람을 여러 번 신고 한 것을 없앤다 각 유저가, 신고한 유저 ID 중, 정지된 ID의 개수를 구하는 것 import java.util.*; // 각 유저가, 신고한 유저 ID 중, 정지된 ID의 개수를 구하는 것 class Solution { public int[] solution(String[] id_list, String[] report, int k) { HashSet set = new HashSet(); for (String string : report) set.add(string.. 2023. 7. 5.
[Java] 알고리즘 투포인터, 그리디, 분할정복 [Java] 알고리즘 투포인터, 그리디, 분할정복 투포인터 투포인터는 주로 배열에서 두 개의 포인트를 만들어서 포인트에 대한 정보를 가지고 데이터를 찾아내는 것이다 투포인터는 양 옆에서 안쪽으로 들어오는 형태로 순회가 가능하다 또한 같은 지점에서 탐색을 할 수 있도록 할 수 있다 기본적으로 문제에 따라 적절하게 사용을 하면 될 것 같다 // ======= 양쪽에서 안 쪽으로 들어오는 방식 ========= // 2개의 숫자를 가지고, target을 만드는 것 private static boolean isPairSum(int[] array, int target) { int left = 0; int right = array.length - 1; while (left < right) { if (array[le.. 2023. 7. 5.
[Java] 알고리즘 이진 탐색 [Java] 알고리즘 이진 탐색 이진 탐색은 정렬된 데이터에서 특정 데이터를 빠르게 찾는 방법이다 데이터를 정렬을 한다 정렬 후, 중간 인덱스를 찾고, 해당 값이, 구하려는 값과 같은 값인지 본다 찾으려는 값이 더 작다면, 중간 인덱스 기준 왼쪽으로 / 크다면 중간 인덱스 기준으로 오른쪽으로 탐색을 한다 위와 같이 왼쪽 또는 오른쪽 기준에서 중간 지점을 찾고, 중간에 있는 숫자보다 작은지 큰지, 또는 같은지 탐색을 한다 그리고 숫자 하나가 남을때까지 탐색을 한다 (마지막 숫자 하나가 답이 아니면, 찾으려는 숫자가 없는 것이다) // ========== loop문으로 구현 ================= public static int binarySearch(int[] array, int target) {.. 2023. 7. 4.

티스토리툴바