기록방

👉 문제링크🔸 문제 분석 🔸총 m개의 컨테이너가 n개의 칸에 나누어 쌓여져 있다.n개의 각 칸의 컨테이너 높이가 1이하가 되도록 재배치할 때, 최소 이동 횟수를 출력한다.🔸 문제 풀이 🔸컨테이너의 높이를 평탄화 하는 문제이다.가장 먼저 정렬을 n번 수행해서 최대값을  -1 최소값을 +1 하는 방법이 있다n이 최대 10만이므로, 시간 복잡도는 O(n^2logn) 으로 1초를 초과하게 된다.최대힙, 최소힙 두 가지 우선순위 큐로 최대값과 최소값만 빠르게 구하는 방법이 있지만, 이 문제에서는 시간 초과가 나게 된다.그리디 알고리즘으로 효율적으로 계산해야한다.n개의 각 칸에 컨테이너는 결국 평균(m/n)에 수렴하게 된다.여기서 높이차가 1이하인 이유가 나오는데, 평균에 수렴할 때 몇 개의 칸은 평균+1..

👉 문제링크🔸 문제 분석 🔸t 번의 테스트 동안 n 개의 전화번호가 주어진다. 각 전화번호가 서로 접두어가 되는 경우가 없는지 판단한다.접두어 관계가 있으면 NO, 없으면 YES를 출력한다.🔸 문제 풀이 🔸n개의 문자열들을 서로 비교해야하는데, n이 1만이므로 O(n^2)으로 비교하면 테스트케이스까지 합쳐서 1초를 초과하게 된다.방법은 2가지가 있는데 정렬 혹은 트라이 자료구조를 이용하는 것이다.정렬 : 현재 문자열보다 긴 문자열 하고만 비교해서 접두어인 경우가 있는지 파악한다.트라이 : 현재 문자열을 접두어로 하거나, 다른 문자열이 현재 문자열에게 접두어인지 확인한다.🔸 정렬 풀이 코드 🔸import java.io.*;import java.util.Arrays;import java.util..

👉 문제링크🔸 문제 분석 🔸N개의 단어가 주어진다. 단어는 알파벳으로 구성되어 있는데, 각 알파벳은 0~9 숫자로 변환할 수 있다.알파벳은 최대 10종류가 주어지고, 알파벳의 숫자는 겹치지 않아야 한다.N개의 단어를 숫자로 변환했을 때 총합의 최대값을 출력한다.🔸 문제 풀이 🔸각 알파벳이 어떤 숫자와 매칭 되어야 최대값이 되는지 찾는 문제이다.Brute Force로 전부 넣어봐도 찾을 수 있지만, 좀더 효율적으로 찾고자 각 알파벳 별 가중치를 계산한다.가중치 순서대로 9부터 0까지 부여한 후 값을 계산해 출력한다.🔸 코드 🔸import java.io.*;import java.util.Arrays;public class Main { public static void main(String[..

👉 문제링크 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 🔸 문제 분석 🔸 N개의 수로 이루어진 수열이 있다. 두 수를 묶어서 곱셈 연산을 할 수 있고, 나머지는 합연산으로 계산한다. 계산 결과의 최대값을 출력한다. 🔸 문제 풀이 🔸 곱셈 연산으로 최대값을 만들어야 하므로 그리디 알고리즘으로 풀이한다. 수열을 정렬 후, 1보다 큰 수 중에서 크기가 큰 수를 우선으로 짝을 지어 곱셈 연산을 진행한다. 수가 1 미만인 수들은 음수끼리 만나 양수가 되거나, 0과 합쳐져 음수가 지워지므로 짝을 짓는다. 🔸 코드..

👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 x축에 평행한 미사일들의 시작과 끝 인덱스가 주어진다. 요격 하기 위해서 미사일들의 범위에 해당하는 곳을 선택해야하며 끝 인덱스에 걸칠 수는 없다. 요격에 필요한 미사일의 최소 수를 구한다. 🔸 문제 풀이 🔸 최소한의 요격 미사일 개수로 최대한 많은 수의 폭격 미사일을 요격해야 하므로 그리디 문제로 볼 수 있다. 포격 미사일의 범위가 겹치는 인덱스를 빠르게 알기 위해 끝 인덱스로 오름차순 정렬한다. 문제에서의 제한 사항으로 실수 좌표도 가능하며 끝 인덱스에 겹치면 안된다. 이전 ..