Noooodle's Footprints

쉽네~ 하고 풀었다가 시간초과 받고 슬라이딩윈도우 방식으로 풀었다. 1. 처음에 한 방식이렇게 모든 범위 하나하나마다 DNA 조건에 일치하는지 확인했다. i ~ j 까지.. 시간초과 났고 다시 짰다.public static int checkPassword(char[] password, int[] DNA, int P){ int i, j, cnt = 0; int[] tmp = {DNA[0], DNA[1], DNA[2], DNA[3]}; // i~j까지 값이 DNA안이랑 같은지 확인 -> 확인할때마다 i~j 변해야함 // j가 인덱스범위를 넘어가면 안됨 for(j=P-1;j 1(8-8+1) -> 2(9-8+1) .. while(i 2. 슬라이딩 윈도우를 적용한 방식1.처..

같은 수일 수도 있다. 이 말때문에 왜틀림???? 을 반복했다.. 인덱스가 같으면 안된다1 2 3 있으면 2를 두 번 고른다는게 아니라 1 2 2 이렇게 2개 있을 수 있다는 말..두포인터 썼고 쉬우니까 그냥 넘어감.. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class BOJ2230 { public static int getMinusMin(int[] numbers, int M){ int i = 0, j = 1, min = 2000000000, result..

이진탐색 문제 왤케 어렵지.. 연속해서 풀어도 감 잡기가 힘들다. 집에다가 공유기를 C개 설치하는데, 설치된 집 사이 거리들 중, 거리가 좁은 쪽을 구한다. 좁은 쪽의 거리들 중에 최댓값을 찾는다. 아래는 예시이다.*은 공유기이다. 설치를할때..  1 2   4        8 9  -> 이런식으로 하면 최소거리는 1이다(1~2)  * *   * 1 2   4        8 9  -> 최소거리는 3(1~4)  *      *         * 1 2   4        8 9  -> 최소거리는 3(1~4)  *      *           * 1 2   4        8 9  -> 최소거리는 1(8~9)  *                * *이 중 제일 큰 최소거리인 3(1~4)가 답이다! 뭘 탐색..

이진탐색을 활용한 세 번째 문제이다. 연달아 푸니 이진탐색 문제에서 중요한게 뭔지 느껴진다.. 제일 중요한건 이진탐색할 범위이다. 범위를 잘못 정하면 아무리 이진탐색을 해도 정답을 맞출 수 없다. 질문게시판을 보니, 문제가 이해 안된다는 글이 매우 많았다.. 예전에는 더 복잡하게 문제가 적혀있었나? 아무튼.. 지금 돈이 있으면 쓰고, 없으면 출금한다. 근데 그냥 출금하면 안되고 지금 있는 돈 다시 통장에 다 넣어서 0원 만들고 출금해야한다. 문제에서 준 예제 7 5 / 100 400 300 100 500 101 400 으로 입출금내역을 정리하면 아래와 같다. *는 출금, -는 사용한 돈, = 는 돈 쓰고 남은 현재돈*+500 // 첫 출금-100 // 첫째날 100원 씀=400 // 400원 남음-400..

앞서 한 나무자르기와 비슷한 문제이다. 이진탐색을 이용했고 나무자르기처럼 답이 딱 안 떨어질 때가 있다. 여유있게 잘라줘야한다.(예: 1 3 / 4 인 경우.. 원하는 답은 3 -> 2로 자르면 2개나오고 1로 자르면 4가 나옴, 답은 1) 1. 입력 받고 정렬2. 이진탐색을 이용해 특정값으로 잘라서 몇 개 나오는지 확인하기3. 출력 1. 3. 은 생략 2. 이진탐색을 이용해 특정값으로 잘라서 몇 개 나오는지 확인하기 처음 이진탐색 범위는 1~제일 긴 랜선 길이(Lan[K-1])이다. 1개 이상은 나와야 몇개가 나오는지 셀 수 있기 때문이다.. 문제에서 준 예제는 4 11 / 802 743 457 539 이고, 제일 긴 랜선은 802이므로 1 ~ 802로 이진탐색을 한다. 이진탐색의 조건은 mid로 잘랐..

심하게 삽질 한 문제!!! 난 바보다... 이진탐색을 한다. 문제에 있는 예시처럼 10 15 17 20 배열이 있다면, 0 ~ 20으로 이진탐색을 한다. 처음에는 mid가 10이 됐다가.. 값 크기 차이를 보고 앞부분을 탐색하거나 뒷부분을 탐색한다. 이진탐색 쓰기로 정했을때 그 생각을 못하고 배열자체를 이진탐색해서 정확하게 찾은 경우, 못찾은경우에 mid들을 비교해서 1개씩 비교하고.. 어쩌고.. ㅎ.. 심지어 제일 처음에 풀때는 브루트포스로 풀었고 다른 예시는 다 적용이 되나 나무 크기가 중복되는 경우(10 10 10  1. 입력받고 정렬 -> 이진탐색 해야되니까..2. 이진탐색으로 적절한 값 찾기3. 출력하기 1. 3. 은 생략.. 2.만 추가설명 2. 이진탐색으로 적절한 값 찾기위에서 말한대로 0부..

간단하다. 전체 코드만 올리고 설명은 생략 1. map으로 입력받고 set에도 동시에 저장 2. 확인할 값 입력받고 해당 값 set에 있는지 확인3. 있으면 map의 value, 없으면 0출력import java.io.*;import java.util.*;public class BOJ10816 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); ..

두 포인터를 사용하는 문제이다.  1. 입력을 받고 오름차순으로 정렬한다.2. [0]과 [N-1]자리에 각각 포인터를 두고 0에 가까워지도록 만든다.3. 0에 가장 가까울때의 값을 출력한다. 1. 입력받고 오름차순 정렬쉬우니까 생략 2. [0]과 [N-1]자리에 각각 포인터를 두고 0에 가까워지도록 만든다.예시를 먼저 들면.. 배열이 아래와 같을때 첫번째 계산을 한다. N = 5, *과 **은 포인터이다. -13 -10 -8 11 12  [0] [1] [2] [3] [4] *                   **두 용액을 합한다. [0]-13 + [4]12 = -1 가 될것이다. '[0]-13 + [4]12 = -1' 가 0에 근접하려면 어떤 계산을 해야할까?[0]-13에는 [4]12 보다 더 큰 수(예..

생각해야 할 게 많았다..시간복잡도에서 N의 범위가 1000까지라서 그냥 이진탐색하면 되겠지~ 했는데 반복문 안에서 이진탐색을 하니 시간초과가 일어나더라. 그래서 음.. 어떻게 하는거지 하고 검색했더니 HashSet을 이용한 문제였다. Set은 중복된 요소를 허용하지 않는 컬렉션을 정의하는 인터페이스다. 쉽게말해 중복을 허용하지 않는다. 종류로는 HashSet, LinkedHashSet, TreeSet이 있고 HashSet만 순서를 유지하지 않는다. 이 문제에서는 순서를 따지지 않기때문에 HashSet을 이용했다. 문제의 큰 흐름은 이렇다. 1. U집합 입력받고 정렬하기2. U집합의 두 개의 합 Set으로 저장하기3. Set과 U집합을 이용해 세 수의 합 최댓값 구하기 1. U집합 입력받고 정렬하기배열로..

입력은.. 주어진대로 받으면 되고, 집합 S에 문자열들이 있는지 확인할때 이진탐색을 쓰면 된다. 주의사항은 이진탐색은 정렬된 상태에서 가능한 탐색방법이므로, 정렬 후 이진탐색을 하면 된다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamR..