Noooodle's Footprints

누적 합을 이용하는 문제이다. 처음에는 모든 숫자들의 합을 구했는데.. 그게아니라 (1,1)부터 (i,j)까지의 합을 미리 구하는 방식이더라.  1. 입력받아 arr[][] 배열을 만든다.2. 누적합 배열 acc[][] 배열을 만든다.3. 누적합을 바탕으로 (x1,y1)부터 (x2,y2)의 합을 구한다. 크게 이렇게 정리할 수 있다.. 1. 입력받아서 arr[][] 배열 만들기쉬우니까 생략.. 전체코드 참고하세요 2. 누적합 배열 acc[][] 배열을 만든다.음.. 우선 나는 배열을 [0]부터 쓰지않고 [1]부터 썼다. 문제에서 0으로 시작하지 않았고 배열 경계선(?)에 주는 조건을 더 간단히 할 수 있기 때문이다.     [0] ...    [4][0] 0 0 0 0 0      0 1 2 3 4   ..

정렬과 그리디 알고리즘을 사용한 문제이다. 그리디 알고리즘은 매 단계마다 최선의 선택을 하는 방법을 말한다. 난 처음에 그리디 알고리즘 문제인지 모르고 모든 가지수를 다 선택하는 방식을 재귀로 짰더니 시간초과가 났다. 그리디 알고리즘인 걸 알고 고쳤더니 통과했다! 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..

이 문제에서 중요한 부분은 사람이름은 고유값이고 로그는 변한다는 것이다. 그럼 Map을 사용해야한다는 것을 알 수 있다! Map중에 TreeMap을 쓰면 더 쉽게 풀 수 있다. 사람 이름은 key가 되고 로그는 value가 된다. 그리고 value가 enter인 경우에만 출력하면 된다. 사전 역순으로 출력하라 했으므로 reverse를 이용하면 된다.. 아 그리고 질문게시판에서 봤는데 문제에서 말하는 사전 순은 아스키코드 순이라고 한다. 사람이름을 대소문자로 구분한다 했으니.., 문제 설명이 좀 불친절하다. 예를들면 a와 A가 있다면 사전순으로 A(아스키코드 65) a(97)가 된다. 우리는 역순이니까 a(97) A(65)순으로 출력하면 된다! 어쩌피 reverseOrder를 사용하면 자동으로 해준다.. ..

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..

좀 불친절한 문제이다. 예외를 설명해주지 않았다. 그리고 !가 나오는 조건도 너무 애매하게 적혀있고.. 문제자체는 크게 어렵지 않다. ! 가 출력되는 조건은 아래와 같다.1. 룰렛이 제대로 생기지 않았을때 -> 0번칸에 A도 들어있고 B도 들어있다 -> 말이 안됨 -> ! 출력2. 룰렛에 중복된 알파벳이 있을때 -> 0번칸에 A, 1번칸에도 A -> 중복이라서 안됨 -> ! 출력 위 조건만 유의해서 코드를 짜면된다.. !의 조건을 이해하는데 너무 오랜 시간을 썼다;;행운의 룰렛(HONITAVR)이 아니면 !를 출력해야한다고 적혀있는데, 굳이 그런 조건을 주지 않아도 통과하더라..import java.io.BufferedReader;import java.io.IOException;import java.io..

문제는 길어서 읽기부터 겁나지만.. 사실 되게 쉬운 문제다. 내가 그린 빨간 선 순서대로 방을 주면 된다.문제 예시에 6*12 호텔에 10번째 손님은 10 = 6 + 4, 즉 좌에서 두 번째줄 밑에서 4번째 방을 주면 된다. 402호이다.30*50 호텔에 72번째 손님은 72 = 30 + 30 + 12, 좌에서 세 번째줄 밑에서 12번째 방을 주면 된다. 1203호 이다. 한 가지 신경써야 할 부분은, 호수가 두 자리를 넘어가는 경우이다. X01호, X02호 ... X09호 까지는 '0 + 좌에서 몇번째인지' 를 주면 되는데, X10호, X11호 .. 등 두자리를 넘어가는 경우는 앞에  0을 빼고 '좌에서 몇번째인지'만 써주면 된다. W는 입력은 받지만 사실상 쓰지 않는다. 입력할때 호텔 방 크기보다 큰..