본문 바로가기

Algorithm

 (140)
Programmers - 가사 검색 with JAVA 첫번째 시도 1. 단어들에 대해서 길이에 따른 해시맵 생성 2. 뒤집은 단어들을 길이에 따라 해시맵 생성 3. 쿼리마다 ?로 시작하는지 여부에 따라 첫번째 해시맵 또는 두번째 해시맵 불러온다. 4. 불러온 List에서 ?를 제외한 쿼리로 시작하는 단어의 개수를 구한다. 문제점 4번에서 모든 단어들을 하나씩 불러오기에는 시간복잡도에 문제가 생긴다. 두번째 시도 - 단어들에 대해서 길이에 따른 해시맵 생성 - 뒤집은 단어들을 길이에 따라 해시맵 생성 - 해시맵 정렬 - 쿼리마다 ?로 시작하는지 여부에 따라 첫번째 해시맵 또는 두번째 해시맵 불러온다. - ?를 a로 대체한 String, z로 대체한 String 두개 생성 - a로 대체한 String이 들어갈 위치와 z로 대체한 String이 들어갈 위치 구하..
이코테 - 공유기 설치 with JAVA 해결 이 문제를 해결하기 위해서는 공유기 설치 간격을 이분탐색으로 구하면 된다. 즉, 공유기 설치 간격을 정해서 입력받은 공유기의 수보다 공유기를 설치 못한다면 공유기 설치 간격을 줄이고 반대로, 입력받은 공유기 수와 같거나 더 많이 설치 가능하다면 공유기 설치 간격을 늘려가며 이분탐색을 진행한다. 예를 들어, 집은 1, 2, 4, 8, 9 에 위치하고 공유기는 3개를 설치하고 싶다고 가정하자. 집간 최소 간격은 1이고 최대 간격은 8이다. 따라서 start=1, end=8로 설정한다. 첫번째 mid= 4가 되고 이는 공유기 설치 간격은 4가 되는 것이다. 위 집들에 적용하면 1, 8에 설치 가능하다. 이는 공유기 3개보다 적으므로 설치 간격을 줄인다. 두번째로는 start=1, mid=2, end=3 ..
이코테 - 정렬된 배열에서 특정 수의 개수 구하기 풀이 1. 기본적으로는 이진탐색이 배경이 된다. (찾고자 하는 값보다 현재 값이 작다면 start = mid+1, 반대는 end = mid-1) 2. 첫번째 인덱스 찾기 - 현재 인덱스가 0이거나 현재인덱스 -1 에 해당하는 값이 찾고자하는 값보다 작고 현재 인덱스에 해당하는 값이 찾고자하는 값일 때, 종료 - 현재 인덱스의 값이 찾고자하는 값보다 작다면 start = mid+1 - 현재 인덱스의 값이 찾고자하는 값보다 크거나 같다면 end = mid-1 예를들어, 1 2 2 2 2 2 3 이 있고 mid는 3이다. 찾고자하는 것은 2의 시작점이다. 인덱스 3에 해당하는 값은 2이다. 해당 인덱스는 0도 아니고 해당 인덱스의 전값이 2보다 작지도 않으므로 첫번째 조건은 성립하지 않는다. 해당 값은 2보다..
이코테 - 안테나 with JAVA 이 문제에서 가장 중요한 점은 값을 기준으로 정렬 후 중간값에 해당하는 인덱스에 값이 정답이 된다는 점이다. 증명은 여러가지 경우의 수를 체크해볼 경우 파악이 가능하다. 코드 import java.util.*; public class Q2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); List values = new ArrayList(); for(int i=0; i
이코테 - 특정 거리의 도시 찾기 with JAVA 1. 입력받을 때는 아래와 같이 nextInt() 써서 입력받자 2. List queue = new ArrayList(); 보다 Queue queue = new LinkedList();가 효율적이다. -> 전자는 삭제시 모든 데이터를 앞으로 땡기기위해 옮겨야 하지만 후자는 그렇지 않기 때문이다. 3. 단방향이기에 방문처리가 필요없다. import java.util.*; public class Q1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int k = sc.nextInt(); int x = sc.nextInt(); List m..
Programmers - 무지의 먹방 라이브 with JAVA 로직 우선, 큐에 [음식 양, 음식 번호] 를 넣고 음식양이 오름차순이 되도록 정렬한다. 예를 들어, [1, 2], [2, 3], [3, 1]이 있다고 가정하자. - 처음 꺼낸 리스트는 [1, 2]가 된다. - 음식양 1을 전체 리스트의 길이(3)만큼 먹는다. 하지만 1*3은 k보다 작으므로 더 진행 - 두번째 꺼낸 리스트는 [2, 3]이 된다. - 전에 1만큼 먹었기 때문에 2-1 = 1이 된다. - 음식양 1을 전체 리스트의 길이(2)만큼 먹는다. 그럼 지금까지 3 + 2를 먹었다. 이는 k와 같으므로 리스트를 다시 넣어주고 종료한다. (지금까지 먹은양이 k보다 크다는 의미는 이번 음식이 없어지면서 또는 없어지기 전에 k만큼 먹었다고 할 수 있다.) 종료 시점에 리스트의 번호만 보면 [1, 3]이 남..
이코테 - 만들 수 없는 금액 with JAVA 문제 N개의 동전으로 만들 수없는 양의 정수 중 최솟값을 구하라 로직 예를 들어, [1, 1, 2, 3, 9] 원이 있다고 가정하자. 1. 1원을 가지고는 1원까지 만들 수 있다. 2. 1원을 가지고는 2원까지 만들 수 있다. 3. 2원을 가지고는 4원까지 만들 수 있다. 4. 3원을 가지고는 7원까지 만들 수 있다. 5. 9원을 가지고는 16원까지 만들 수 있다. 증명 1원 - 1 2원 - 1, 1 3원 - 1, 2 4원 - 1, 1, 2 5원 - 3, 2 6원 - 3, 2, 1 즉, 결론적으로 a원을 가지고 있다면 기존에 만들 수 있는 금액 m원에 더해 a+m원까지 만들 수 있다. 코드 import java.util.*; public class Q4 { public static void main(St..
Programmers - 등산 코스 정하기 with JAVA 로직 1. 양방향 맵 생성 2. 산봉우리마다 확인 3. 우선순위 큐를 통해 가장 비용이 짧은순으로 처리 - 우선 순위 큐는 비용순으로 처리 - 방문 처리 - 봉우리마다 가장 가까운 출발지 방문시 바로 종료 (비용순으로 처리하고 출발지에 번호는 상관없기에 종료 가능) - 중간비용이 이미 정답보다 크다면 종료 (예를 들어, 산봉우리 A처리 후 최소값이 5라고 가정, 산봉우리 B 처리 중 이미 비용이 5 이상이라면 더이상 처리할 필요없어짐.) 4. 비용이 가장 작으면서 산봉우리 번호가 가장 작은 구역 반환 코드 import java.util.*; class Solution { public int[] solution(int n, int[][] paths, int[] gates, int[] summits) { i..

티스토리툴바