algorithm-study-discussion
Replies: 3 comments
🚤 구명 보트🔹 첫 번째 접근 (실패)
🔹 두 번째 접근 (성공)
public class LifeBoat {
public int solution(int[] people, int limit) {
// 오름 차순 정렬
Arrays.sort(people);
int start = 0;
int end = people.length - 1;
int count = 0;
while (start <= end) {
if (start == end) {
count++;
break;
}
if (people[start] + people[end] <= limit) {
count++;
start++;
end--;
} else {
count++;
end--;
}
}
return count;
}
}[ 프로세스 📘 ]🔹 접근 방법
🔹 작업 규칙
🔹 느낀점
public int solution(int[] priorities, int targetIndex) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
Queue<Job> queue = new ArrayDeque<>();
// 작업 넣기
for (int i = 0; i < priorities.length; i++) {
Job job = new Job(priorities[i], i);
pq.add(priorities[i]);
queue.add(job);
}
// 작업 수행
while (!queue.isEmpty()) {
Job job = queue.poll();
int priority = job.priority;
// 최우선순위 작업이라면
if (pq.peek() == priority) {
pq.poll();
// 작업의 인덱스가 찾고자 하는 인덱스 라면
if (job.index == targetIndex) {
return priorities.length - pq.size();
}
} else {
// 작업 수행 불가
queue.add(job);
}
}
// 찾지 못하는 경우 (없음)
return -1;
}
private static class Job {
private int priority;
private int index;
public Job(int priority, int index) {
this.priority = priority;
this.index = index;
}
}[ 피로도 📘 ]🔹 첫번째 접근 방법
🔹 두번째 접근 방법
🔹 느낀 점
public class Fatigue {
private static boolean[] visited;
private static int[][] dungeons;
private static int maxDungeonCount = 0;
public int solution(int fatigue, int[][] dungeons) {
this.dungeons = dungeons;
// 탐색
this.visited = new boolean[dungeons.length];
dfs(0, fatigue);
return maxDungeonCount;
}
private static void dfs(int depth, int fatigue) {
maxDungeonCount = Math.max(maxDungeonCount, depth);
for (int i = 0; i < dungeons.length; i++) {
if (!visited[i]) {
int minFatigue = dungeons[i][0];
int useFatigue = dungeons[i][1];
int nextFatigue = fatigue - useFatigue;
if (fatigue >= minFatigue) {
visited[i] = true;
dfs(depth + 1, nextFatigue);
visited[i] = false;
}
}
}
}
}🔢 가장 큰 수첫 번째 접근
두 번째 접근
class Solution {
public String solution(int[] numbers) {
List<String> list = new ArrayList<>();
for(int i = 0; i < numbers.length; i++){
list.add(String.valueOf(numbers[i]));
}
list.sort((a,b) -> (b + a).compareTo(a + b));
StringBuilder sb = new StringBuilder();
for(int i = 0; i < numbers.length; i++){
sb.append(list.get(i));
}
String result = sb.toString();
if(result.charAt(0) == '0') return "0";
return result;
}
} |
0 replies
📌 구명보트
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
int start = 0;
int end = people.length - 1;
Arrays.sort(people);
while (start <= end) {
if (people[start] + people[end] <= limit) {
start++;
}
end--;
answer++;
}
return answer;
}
}📌 피로도
class Solution {
public int solution(int k, int[][] dungeons) {
boolean[] visited = new boolean[dungeons.length];
return dfs(k, dungeons, visited, 0);
}
private static int dfs(int k, int[][] dungeons, boolean[] visited, int count) {
int maxCount = count;
for (int i = 0; i < dungeons.length; i++) {
if (!visited[i] && k >= dungeons[i][0]) {
visited[i] = true;
maxCount = Math.max(maxCount, dfs(k - dungeons[i][1], dungeons, visited, count + 1));
visited[i] = false;
}
}
return maxCount;
}
}📌 프로세스
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
int answer = 0;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < priorities.length; i++) {
queue.add(new int[] {i, priorities[i]});
}
while (!queue.isEmpty()) {
int[] index = queue.poll();
boolean higher = false;
for (int[] q : queue) {
if (q[1] > index[1]) {
higher = true;
break;
}
}
if (higher) {
queue.add(index);
} else {
answer++;
if (index[0] == location) {
return answer;
}
}
}
return answer;
}
}📌 가장 큰 수
import java.util.*;
class Solution {
public String solution(int[] numbers) {
List<String> list = new LinkedList<>();
for (int i = 0; i < numbers.length; i++) {
list.add(String.valueOf(numbers[i]));
}
list.sort((a, b) -> (b + a).compareTo(a + b));
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
sb.append(list.get(i));
}
if (sb.charAt(0) == '0') {
return "0";
}
return sb.toString();
}
} |
0 replies
구명보트해결방법
import java.util.Arrays;
class Solution {
public int solution(int[] people, int limit) {
// 몸무게 오름차순 정렬 (가벼운 사람부터, 무거운 사람 순으로)
Arrays.sort(people);
int light = 0; // 가장 가벼운 사람 위치(왼쪽 포인터)
int heavy = people.length - 1; // 가장 무거운 사람 위치(오른쪽 포인터)
int boats = 0;
// 왼쪽(light)와 오른쪽(heavy)이 교차할 때까지 반복
while(light <= heavy) {
if (people[light] + people[heavy] <= limit) {
// 둘이 함께 탈 수 있으면 함께 태움
light++; // 가장 가벼운 사람 태움
heavy--; // 가장 무거운 사람 태움
} else {
// 둘이 같이 타면 초과될 시 -> 가장 무거운 사람만 혼자 태움
heavy--;
}
// 보트는 한 번에 최대 2명까지, 위 조건 처리 후 보트 1척 사용
boats++;
}
return boats;
}
}피로도해결 방법
import java.util.*;
class Solution {
// 던전 몇 개까지 갈 수 있었는지 최대값 저장 변수
int maxCount = 0;
public int solution(int k, int[][] dungeons) {
// 순서 섞기 위해 입장 체크 배열 만듬
boolean[] admission = new boolean[dungeons.length];
// 순서 섞어서 도는 함수
dfs(k, dungeons, admission, 0);
// 가장 많이 돈 횟수 반환
return maxCount;
}
// 던전 순서를 다 섞어 돌면서 체크하는 함수
public void dfs(int currentTired, int[][] dungeons, boolean[] admission, int count) {
// 지금까지 돈 횟수가 최대라면 저장
if (count > maxCount) {
maxCount = count;
}
// 던전 하나씩 체크
for (int i = 0; i < dungeons.length; i++) {
int minTired = dungeons[i][0]; // 최소 필요한 피로도
int useTired = dungeons[i][1]; // 던전 돌면 깎이는 피로도
// 아직 안 갔고, 갈 수 있으면
if(!admission[i] && currentTired >= minTired) {
admission[i] = true; // 방문했다고 표시
dfs(currentTired - useTired, dungeons, admission, count + 1); // 다음 단계
admission[i] = false; // 돌아와서 다시 방문 안 한걸로(되돌리기)
}
}
}
}프로세스Queue 안 쓴 풀이해결 방법
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
// 프로세스 목록을 담을 리스트 (중요도 + 원래 위치)
List<int[]> list = new ArrayList<>();
for (int i = 0; i < priorities.length; i++) {
list.add(new int[]{priorities[i], i}); // 예: [3, 2] → 중요도 3, 위치 2
}
int order = 0; // 몇 번째로 실행되는지 세는 변수
while (!list.isEmpty()) {
int[] current = list.remove(0); // 가장 앞 프로세스를 꺼냄
// 현재보다 높은 우선순위가 뒤에 있나 검사
boolean hasHigh = false;
for (int i = 0; i < list.size(); i++) {
if (list.get(i)[0] > current[0]) {
hasHigh = true;
break;
}
}
if (hasHigh) {
// 더 높은 우선순위 있으면 다시 뒤로 넣음
list.add(current);
} else {
// 아니면 실행
order++;
if (current[1] == location) {
return order;
}
}
}
return -1; // 여기는 절대 안옴
}
}Queue 쓴 풀이해결 방법
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
// 프로세스를 큐에 넣기 위해 Queue 선언
Queue<int[]> queue = new LinkedList<>();
// 프로세스를 큐에 추가 (중요도 + 원래 위치)
for (int i = 0; i < priorities.length; i++) {
// 예: [2, 0] → 중요도 2, 위치 0
queue.add(new int[]{priorities[i], i});
}
int order = 0; // 실행 순서를 세기 위한 변수 (몇 번째로 실행됐는지)
// 큐가 비기 전까지 계속 반복
while (!queue.isEmpty()) {
// 맨 앞에 있는 프로세스를 꺼냄
int[] current = queue.poll(); // current = [중요도, 위치]
// 현재 꺼낸 것보다 더 높은 중요도가 뒤에 있는지 확인
boolean hasHigher = false;
for (int[] q : queue) {
if (q[0] > current[0]) { // 더 큰 중요도 발견!
hasHigher = true;
break;
}
}
// 더 중요한 프로세스가 있다면 → 다시 뒤에 넣기
if (hasHigher) {
queue.add(current); // 다시 뒤에 넣음
} else {
// 그렇지 않으면 → 이 프로세스 실행
order++; // 실행 순서 증가
if (current[1] == location) {
// 만약 이게 내가 찾던 프로세스라면 → 지금이 실행 순서
return order;
}
}
}
return -1; // 도달하지 않음 (논리상 불가능)
}
}가장 큰 수해결방법
import java.util.*;
class Solution {
public String solution(int[] numbers) {
// 숫자 배열을 문자열 리스트로 바꿈 (이어 붙이기 위해)
List<String> list = new ArrayList<>();
for (int number : numbers) {
list.add(String.valueOf(number));
}
// 정렬: 두 수를 더해서 큰 조합이 앞으로 오게 정렬
list.sort((a, b) -> (b + a).compareTo(a + b));
// 예: "3" vs "30" -> "330" vs "303" -> "3"이 앞에
// 정렬된 숫자들을 이어붙임
StringBuilder result = new StringBuilder();
for (String numStr : list) {
result.append(numStr);
}
// 예외 처리: 가장 앞이 0이면 전부 0인 것 → "0" 리턴
if (result.charAt(0) == '0') {
return "0";
}
// 결과 문자열 리턴
return result.toString();
}
} |
0 replies
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
📢 이번 주 알고리즘 스터디 문제
이번 주에는 총 6문제를 풉니다.
(정답률은 프로그래머스 기준)
📌 문제 목록 [ 2단계 ]
🗓️ 발표
🚨 벌금 규칙
🔥 이번 주도 화이팅입니다!
All reactions