Noooodle's Footprints

생각해야 할 게 많았다..시간복잡도에서 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..

정렬과 그리디 알고리즘을 사용한 문제이다. 그리디 알고리즘은 매 단계마다 최선의 선택을 하는 방법을 말한다. 난 처음에 그리디 알고리즘 문제인지 모르고 모든 가지수를 다 선택하는 방식을 재귀로 짰더니 시간초과가 났다. 그리디 알고리즘인 걸 알고 고쳤더니 통과했다! 1. 끝나는 시간을 기준으로 정렬을 한다.1-2. 만약 끝나는 시간이 같다면, 시작 시간이 빠른 것이 먼저 온다.2. 첫 번째 회의를 선택하고, 그 다음으로 선택 가능한 회의를 선택한다.3. 2번을 계속 반복해서 모든 회의를 다 살펴본다. 단순하다.. 이렇게 적으니까.. 그리디 알고리즘이라서 가능한거다. 1. 1-2. 정렬하기사용자 정의 클래스를 하나 만든다. 나는 Meeting이라고 만들었다. Meeting 클래스는 start(시작시간), e..

이 문제에서 제일 중요한건, 등장하는 횟수가 같다면 먼저 나온 것이 앞에 있어야 한다는 것이다. 그것말고는 딱히 어렵지않다. 먼저 나온 것이 앞에 나오게 하기 위해 LinkedHashMap을 사용했다. HashMap과 유사하지만 들어온 순서를 기억한다. 1. 전에 푼 1302번과 유사하게 map에 값을 넣어준다.2. value가 제일 큰 key를 찾아서 key를 value번 출력한다3. map에서 출력된 key를 삭제한다.4. 2번과 3번을 반복해서 map이 비면 끝낸다. LinkedHashMap을 사용했기 때문에 value가 같더라도 먼저 들어온 set을 찾아준다. 아래는 전체 코드이다.import java.io.BufferedReader;import java.io.IOException;import j..

처음엔 문제가 무슨 소린가했다.. 그냥 입력받은 수보다 작은 입력받은 수들의 개수를 구하는거다. 1. 배열 입력받기2. 중복없이 정렬된 새 배열 만들기3. 기존 배열의 값에 해당하는 새 배열의 인덱스값 출력하기 이렇게 구상했고, 테스트케이스로 예시를 들자면.. 2   4 -10  4  -9[0] [1] [2] [3] [4]1.배열을 입력받고, 2.정렬되고, 중복이 없는 새 배열을 만든다. 2   4 -10  4  -9            -10 -9   2  4[0] [1] [2] [3] [4]            [0] [1] [2] [3]                  3. 기존 배열의 값에 해당하는 새 배열의 인덱스 값을 출력한다.기존 배열의 [0]2는 새 배열의 [2]2에 해당하고, 인덱스인 2를..

TreeMap을 잘 활용하면 되는 문제..1. 책을 입력받는다.2-1. 처음 입력받은 책이면 map에 'key=bookTitle, value=1' 으로 추가해준다.2-2. 기존에 등록된 책이면 value만 +1 증가시켜준다.3. value가 제일 큰 set을 찾아 출력한다. 1. 2-1. 2-2. 책을 입력받고 등록 유무를 확인해  value 지정하기for(i=0;i새로운 책일때는.. 그냥 추가하면 되고, 등록된 책일때가 중요하다.bookTitle로 원래 있던 set을 찾아서 해당 value를 가져오고 +1 해준다. 3. value가 제일 큰 set을 찾고 출력Map.Entry maxEntry = Collections.max(books.entrySet(), Map.Entry.comparingByValue..

C언어는 구조체를 만들면 되고 자바는 class를 하나 만들어서 비교하면 된다. 새로 배운 부분은 사용자 정의 class 배열을 비교할 수 있다는 점이다. 단, 사용자가 comparable 클래스를 상속해서 compareTo함수를 오버라이딩하고 재정의해주어야 한다. 1. Member 클래스Member 클래스는 3개의 필드를 가진다. 나이, 이름 그리고 입력받은 순서(n)이다. 변수명을 뭘로할까 하다가 그냥 단순하게 n으로 주었다.Member클래스 안에 새로운 정렬 방식을 compareTo에 정의했다.기존의 compareTo 메서드와 리턴값이 같게 조건을 주었다.public class Member implements Comparable{// .. 생략 @Override public int com..

문제 자체는 쉽지만 시간복잡도와 arrays.sort, 람다식을 모르면 풀기 어려운 문제이다.단순히 이중 for문으로 길이와 알파벳순으로 정렬할 수 있지만 시간초과가 난다. 컴퓨터는 1초에 1억번 정도의 연산만 수행할 수 있는데 이중 for문을 사용하면 최대 20,000제곱만큼 계산해야 하기 때문이다.O(n^2)그래서 고민하다가.. arrays.sort를 할때 조건을 주면 되지않나 싶어서 찾아봤고 문제가 풀렸다. 1. 조건에 맞춰 정렬하기 조건은 길이가 짧은 순으로 정렬하고, 길이가 같으면 알파벳순으로 정렬하는 것이다.// 길이로 정렬, 길이 같으면 알파벳으로 정렬, 람다식 사용Arrays.sort(strArr, (s1, s2) -> { int lengthComparison = Integer.compa..

4. Merge sort 5. Quick sort 6. Heap sort Divide-And-Conquer, 분할정복법분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할정복: 각각의 작은 문제를 순환적(재귀)으로 해결합병: 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함 Merge sort, Quick sort, Heap sort 모두 분할정복법을 사용한다. 세 가지 방법 모두 시간복잡도는 O(nlogn)으로 동일하다. *예시는 오름차순 정렬*노란색은 정렬된 부분*파란색은 정렬할 부분4. Merge sort, 합병정렬1) 배열을 절반으로 나눔 2) 나뉜 배열 각각을 정렬함 3) 나뉜 배열을 합치면서 정렬순환적(재귀) 코드이다. 재귀는 자기 자신을 호출하는 것을 말한다. 처음..