Coding Test Inflearn

설명      풀이 결정 알고리즘이란 이분 검색을 이용하는 것이다. lt와 rt 사이에 반드시 답이 있다고 보장할 수 있는 문제에만 적용이 가능하다. 답으로서 가능한지 범위를 좁혀 나가면서 최종적으로 답을 결정한다. 좋은 답을 향해 좁혀 나가는 알고리즘이다.  solution 함수 로직은 다음과 같다.정답이 될 변수 answer를 0으로 초기화 한다.lt는 배열의 최댓값이고, rt는 배열의 합이다.배열의 최댓값은 Arrays.stream(arr).max().getAsInt() 로 구한다.배열의 합은 Arrays.stream(arr).sum() 으로 구한다.이분 탐색을 수행한다. lt가 rt보다 작거나 같을 때 반복한다. while (lt 여기서 mid 변수는 DVD 한 장의 용량을 의미한다. mid 변수..

설명       풀이 이 문제를 통해 이분 검색 (Binary Search) 알고리즘에 대해 학습했다. 이분 검색은 오름차순이던 내림차순이던 정렬된 상태에서 수행해야 한다.앞에서부터 쭉 탐색하는 것은 순차 검색이라고 하며, 시간 복잡도는 O(n)이다.이분 검색의 시간 복잡도는 O(log(n))이다. 핵심은 다음과 같다.배열은 오름차순 정렬 되어있다고 가정한다. (Arrays.sort를 이용한다.)arr은 데이터가 들어있는 int형 배열이고, m은 찾고자 하는 수이다.두 포인터 변수 lt, rt, 그리고 mid 변수를 이용한다. lt는 왼쪽 인덱스 번호를 나타내며, rt는 오른쪽 인덱스 번호를 나타낸다. mid 변수는 (lt + rt) / 2 이다.lt가 rt보다 같거나 작은 동안 반복한다.(arr[mid..

설명      풀이 자료구조는 ArrayList를 사용한다.Point 클래스는 우리가 정의해야 할 클래스이다. 이 클래스는 x좌표, y좌표를 갖고 있으며 Comparable 인터페이스의 구현 클래스이다. Comparable 인터페이스에서 구현해야 할 메소드는 compareTo이다.오름차순인 경우 this.멤버변수 - o.멤버변수, 내림차순인 경우 o.멤버변수 - this.멤버변수 를 사용한다. 즉, 음수값이 리턴되도록 하면 된다.정렬은 Collections.sort를 호출하면 된다. 그럼 Comparable 인터페이스를 통해 compareTo의 정렬 기준에 의해 정렬이 수행된다.   코드와 함께 설명을 정리하면 다음과 같다. 아래는 핵심인 Point 클래스이다. 1) Point 클래스는 Comparabl..

설명      풀이 자료구조는 int형 배열을 사용한다. 로직은 다음과 같다.정답으로 리턴할 데이터는 ArrayList 형으로 생성한다.원본 배열을 깊은 복사한다. clone 메소드를 이용한다. 이 배열을 복사된 배열이라고 하자.복사된 배열을 오름차순 정렬한다. Arrays 클래스의 sort 메소드를 이용한다.반복문을 돌면서 원본 배열과 복사된 배열의 값을 비교한다.값이 다르다면 정답에 add 한다. 이 때 인덱스 값에 +1을 해야 배정받은 번호가 된다. (번호는 1부터 시작이고 인덱스는 0부터 시작이므로)정답 배열을 리턴한다.    코드 package inflearn._6_6;import java.io.BufferedReader;import java.io.BufferedWriter;import java..

설명       풀이 이 문제는 HashMap을 사용하면 O(n)으로 풀 수 있지만, 정렬로도 이 문제를 풀 수 있음을 보여주기 위해 정렬을 사용했다.정렬을 사용하면 O(nlog(n))이 된다. 로직은 다음과 같다.정답 문자열을 "U"로 초기화한다.오름차순 정렬을 한다. java.util.Arrays 클래스의 sort 메소드를 이용한다.0번 인덱스부터 (배열 길이의 - 1) 번 인덱스까지 반복문을 돈다.현재 배열값과 현재 배열값의 다음값이 같다면 중복된 것이므로 "D"를 바로 리턴한다.정답 문자열을 리턴한다.    코드 package inflearn._6_5;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOExcep..

설명       풀이 자료구조는 int 배열을 사용하며 알고리즘은 정렬을 활용한다.  로직은 다음과 같다.캐시 크기만큼의 int 배열을 생성한다.작업이 들어있는 배열을 돈다.초기 int형 변수 pos를 -1로 둔다. 이 변수는 현재 수가 캐시에 존재하는지 확인할 수 있는 변수이다.캐시 배열을 돌면서 현재 수가 캐시 배열에 존재하는지 확인한다.존재한다면 해당 인덱스 변호를 pos 변수에 저장한다.pos가 -1 이면 캐시에 현재 값이 존재하지 않는다는 뜻이다. 즉, miss 인 경우이다.배열의 맨 뒤부터 1번 인덱스까지 1 감소시키며 반복문을 돈다.오른쪽으로 수를 하나씩 민다. 캐시 배열의 i-1 번째 인덱스의 값을 캐시 배열의 i 번째 인덱스의 값에 넣는다.pos가 -1이 아니면 캐시에 현재 값이 존재한다..

설명      풀이 id와 priority를 가진 Person 클래스를 만든다.priority를 입력받을 때, Queue에 Person 클래스를 담아 입력받는다. 핵심 로직은 다음과 같다.초기 answer 값은 0이다. 큐가 비어있지 않는 동안 계속 진행한다.한 명의 환자를 큐에서 꺼낸다.큐를 순회하면서, 방금 꺼낸 한 명의 환자보다 우선순위가 높은 환자가 있는지 조사한다.현재 환자의 우선순위보다 높은 우선순위를 가진 환자가 있다면현재 환자를 큐의 제일 끝에 다시 넣는다.현재 환자를 비도록 한다.반복문을 멈춘다.반복문이 끝났는데 현재 환자가 null이 아니라면answer를 1 증가시킨다.현재 환자가 찾고자 하는 환자인지 확인한다.맞다면 그대로 answer를 리턴한다. answer를 리턴한다.     코드..

설명      풀이 필수과목 순서로 입력받은 문자열을 순회하며 큐에 넣는다.계획한 문자열을 순회하면서 다음 로직을 수행한다.필수과목에 포함되어 있다면 큐에서 꺼낸 값이 해당 값과 동일한지 확인한다.동일하지 않다면 교육과정을 잘못 짠 것으로, 바로 "NO"를 리턴한다. 순회가 끝난 후 큐가 비어있지 않다면 들어야 하는 필수과목이 남아있는 것이므로 "NO"를 리턴한다.     코드package inflearn._5_7;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import jav..