Algorithm/프로그래머스18

• 

  백준 - 파일 합치기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.

• 

  프로그래머스 - 방의 개수 문제 설명 8가지의 방향 수가 입력으로 주어지고, (0,0)에서 출발하여 방향대로 움직여서 도형을 이루는 개수를 출력하는 문제이다. 도형이 만들어지는 경우는 해당 정점에 이미 다른 노드로부터 방문한 흔적이 있고 새로운 간선이 만들어지는 경우가 도형이 만들어지는 경우이다. (:= 사이클 형성) 주의사항 도형이 만들어지는 경우 엣지케이스가 존재한다. 교차점이 생성될 경우 이러면 도형은 위 아래 삼각형이 만들어지게 되는데 도형이 2개인지 1개인지 판별할 수 없게 된다. 맨 왼쪽 그림에서 해당 a로 다시 들어올때 방문했던 이력이 있고, 새로운 간선이 생겨 도형이 만들어졌다. 하지만 도형이 2개가 만들어 졌는지 1개가 만들어졌는지 알수 없다. 그래서 2배로 확대해서 보면 쉽게 2개가 만들어졌는지 1개가 만들어 졌.. Algorithm/프로그래머스 2023. 4. 25.

• 

  프로그래머스 - N으로 표현 문제 설명 N에 대한 사칙연산으로 number를 만들 수 있는 최소 N의 사용개수를 구하는 문제이다. n의 사용횟수에 따라 값을 저장한다. 하지만 아래 방식처럼 알고리즘을 작성하면 “12 = (55 + 5) / 5” 해당식에서 나타난 괄호에 대한 우선순위 적용이 안되어있어 최소 개수를 구할 수 가 없다. 왜냐하면 괄호 연산에 따라 값이 달라지기 때문이다. := 사칙연산은 우선순위가 존재하므로 “4+4*4“ 의 식이 주어질때 20으로 계산된다. 하지만 괄호가 들어간 (4+4) * 4 식으로 바꾸면 32가 나오듯이 괄호에 따라 중간 결과값이 달라지는 경우가 많아 해당 괄호도 있도록 알고리즘을 구성해야 한다. 괄호가 있도록 구성하기 위해 n이라는 숫자를 4번 사용하여 만드는 경우의 수를 구할떄 n을 3번 사용.. Algorithm/프로그래머스 2023. 4. 21.