Algorithm69

• 

  백준 - 파일 합치기3 문제 설명 파일을 모두 하나의 파일로 합치려고 한다. 단 파일을 합치는데 비용이 발생한다. a,b두개를 선택하여 합치면 각 값의 합으로 비용을 산정한다. 파일을 합칠 때 발생하는 최소비용을 구하는 문제이다. 주의사항 두 파일의 대한 값이 k개 백만개이고 각 요소의 최댓값은 만이다. 각 요소의 합이 백억까지될 수 있으므로 int자료형은 21억이라 overflow가 발생하니 타입에 주의해야 한다. 해당 문제에서 합치는 비용을 최소로 만들기 위해 작은 값끼리 먼저 더해가야 한다. 왜냐하면 이미 비싼 비용을 가진 파일이 점차 누적되기 때문에 큰 값은 계속 누적해서 더해가기 때문에 최소가 될 수 없다. 풀이 import java.util.Arrays; import java.util.PriorityQueue; im.. Algorithm/프로그래머스 2023. 6. 9.

• 

  프로그래머스 - 과제 수행하기 문제 설명 과제를 진행하려 한다. 과제를 하던중 새로운 과제가 나오면 새로운 과제를 먼저 해야한다. 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춘 과제를 진행한다. 또한 멈춘 과제를 진행 중 새로운 과제가 출현하였을 때 새로운 과제를 먼저 해야한다. 그리고 멈춘 과제가 여러개일 경우 최근 멈춘 과제를 먼저 진행한다. 주의사항 과제는 시간순으로 정렬된 상태가 아니므로 정렬한다. 과제를 진행하고 다음 과제 출현 시간 사이에 자투리 시간이 있다면 멈춘과제를 수행해야한다. 즉, 멈춘 과제들을 모두 나중에 처리하는 것이 아님을 인지해야 한다. 여기서의 핵심은 자투리 시간의 과제를 수행해야 한다. 풀이 class Node{ String name; String startTime; int playTime; pub.. Algorithm/프로그래머스 2023. 6. 8.

• 

  프로그래머스 - 요격 시스템 문제 설명 A나라가 B를 침략하기 위해 [s,e]까지 피해를 줄 수있는 미사일을 발포한다. B나라는 이 사실을 알고 A나라에서 발포한 미사일을 모두 격추 시키려 할 때, 최소한의 개수로 미사일을 격파시킬 수 있는 개수를 구하는 문제이다. 해당 문제는 한 점에서 최대 격추시킬 수 있는 미사일의 개수를 구하는 것이 핵심이다. 풀이 public int solution(int[][] targets) { Arrays.sort(targets,(a,b)-> { if(a[0] == b[0]){ return a[1]-b[1]; } return a[0] - b[0]; }); int answer=1; int end=targets[0][1]; for(int i=1; i Algorithm/프로그래머스 2023. 6. 7.

• 

  백준 - 우체국 문제 설명 각 마을들이 위치한 수직선 상에서 마을에 거주하는 각 사람들까지의 거리의 합이 최소가 되는 곳에 우체국을 건설하려고 할 때, 우체국을 세울 위치를 구하는 문제이다. 각 사람들까지의 거리의 합이 최소가 되는 곳에 우체국을 건설해야 하니 과반수가 넘는 인원에 대해서 최대한 가깝게 우체국을 건설하는 것이 좋다고 판단하였다. 우선 거리기반(오름차순), 인구수 기반(내림차순)으로 정렬한다. 하나씩 순회하면서 거쳐간 인원 인구수를 파악한 후 과반수 이상의 사람이 살고 있는 경우라면 해당 위치에 우체국을 건설한다. 단 원소의 값이 최소 + - 10억이므로 거쳐간 인구수에서 int 자료형은 이슈가 될 수 있으니 주의해야한다. 풀이 public static void main (String[] args) thr.. Algorithm/백준 2023. 5. 27.

• 

  백준 - 꿀 따기 문제 설명 주어진 배열은 각 꿀의 양을 나타낸다. 벌 2마리 벌통 1개가 주어진다. 벌 2마리를 어느 위치에 위치시키고, 벌통을 벌2마리의 위치가 아닌 위치에 두면, 벌들이 벌통을 향해서 이동하게 된다. 단, 가는 길의 꿀을 따면서 간다. 이런 시스템으로 이동할 경우 벌들이 꿀을 딸 수 있는 가능한 최대 양을 구하는 문제이다. 처음 접근할 때 어떤 것을 고정시켜야 될까? 라는 질문에 답하지 못했다. 너무나도 애매했다. 왜냐하면 벌들의 위치와 꿀통의 위치에 따라 달라지는데, n^3 이 나온다고 생각했다. - 벌1,2 위치 선택 (n^2) - > 꿀통 위치 [i, n-1] (n) 그래서 시간초과가 분명하게 난다고 생각했다. 최대가 되는 경우를 생각해 볼때, “꿀벌 1 위치 < 꿀벌 2위치 시간초과 // 누적.. Algorithm/백준 2023. 5. 26.