순간을 기록으로

문제 풀이 좌표를 정렬할 수 있는지에 관한 문제다. x를 기준으로 오름차순으로 정렬하되 만약 값이 같다면 y를 기준으로 정렬해야 한다. 좌표는 x와 y로 이루어져 있다. 즉 독립적인 변수 한 개가 아니고 두 개로 구성된다. 따라서 객체를 만들어 관련된 두 변수를 갖게 만들고 객체를 정렬하기 위해 Comparable 인터페이스 compareTo() 메서드를 구현해야 한다. 코드 package 인프런.정렬과검색.좌표정렬.방법1; import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Point implements Comparable{ // 좌표 int x; int y; public Point(int x,..

문제 풀이 '도착한 순서대로 진료를 받는다'를 통해 Queue를 이용한 문제를 알 수 있습니다. 코드 package 인프런.스택과큐.응급실.방법1; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Person { int id; int priority; public Person(int id, int priority) { this.id = id; this.priority = priority; } } public class Main { int solution(int n, int m, int[] arr) { int answer=0; Queue q = new LinkedList(); for (int i=0; i..

문제 N을 입력하면 1~N을 원소로하는 공집합을 제외한 부분집합을 출력하기 풀이 DFS를 이용해서 풀 수 있다. 예를들어 {1, 2, 3}이라는 집합이 있다고 하자. 이 집합의 공집합을 제외한 부분 집합의 갯수는 2^3-1이므로 7이다. 즉 원소마다 있느냐, 없느냐에따라 경우의 수가 2가지이고 원소의 갯수만큼 그만큼 곱해주면 모든 경우의 수가 나온다. 마지막에 공집합은 제외하니 -1을 하면된다. 그럼 DFS원리를 이용해서 이진트리로 풀어보자 코드 package 인프런.재귀와트리와그래프.부분집합구하기; /* * 어떤 집합의 모든 부분집합을 출력하는 문제 * */ public class Main { static int n; // 원소의 갯수 static boolean[] ch; // 부분 집합의 원소로 사용..

문제 풀이 철수가 받은 번호와 짝궁이 받은 번호를 찾는 문제이다. 입력으로 주어진 배열을 임시 배열에 복사를 한다. 그리고 원소별로 비교하면 철수와 짝궁의 번호를 알 수 있다. 코드 import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { public ArrayList solution(int n, int[] arr) { ArrayList answer = new ArrayList(); int[] temp = arr.clone(); Arrays.sort(temp); // 정렬 for (int i=0; i

문제 풀이 배열의 연속된 원소와 관련이 있고 길이가 바뀌므로 투포인터 알고리즘이다. 코드 package 인프런.투포인터와슬라이딩윈도우.최대길이연속부분수열.방법1; import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.Test; public class Main { public int solution(int N, int k, int[] arr) { int answer=0; int count = 0; int start=0; for (int end = 0; end k) { // count가 k를 넘어가면 start 포인터가 0을 만날 때까지 오른쪽으로 이동시킨다. if (arr[start] == 0) count--; start++; } an..

문제 https://programmers.co.kr/learn/courses/30/lessons/1845 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. programmers.co.kr 풀이 서로다른 가장 많은 종류의 폰켓몬을 반환하면 된다. 따라서 Set 자료구조를 이용해 중복은 무시하고 size() 메소드를 사용해서 서로다른 종류의 폰켓몬 갯수를 얻을 수 있다. 다만 처음 N/2마리라는 제한이 있으므로 만약 size 메소드에서 구한 값이 N/2보다 크면 N/2를 반환하고 그렇지 않으면 size 메소드에서 구한 값을 반환하면 된다. 코..

문제 https://programmers.co.kr/learn/courses/30/lessons/77884?language=java 코딩테스트 연습 - 약수의 개수와 덧셈 두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주 programmers.co.kr 풀이 약수에 대한 개념이 필요한 문제다. N의 약수란 N을 나누어 떨어지게 하는 양의 정수를 말한다. 예를들어 4의 약수는 1, 2, 3, 4가 있다. 3의 약수는 1, 3이다. 어떤 수가 나누어 떨어지는지는 알려면 나머지 연산(%)을 사용하면 된다. 만약 나누어 떨어지는 수라면 ..

문제 주의할 점 그리디 알고리즘 문제이다. 그리디 알고리즘은 매 선택에서 현재 당장 최적인 답을 선택한다. 이 문제는 매 선택에서 회의실 끝나는 시간이 빠른 회의를 선택한다는 점에서 그리디 알고리즘이라고 할 수 있다. 시작 시간과 끝나는 시간을 묶어서 하나의 객체를 만들기 위해 Meeting 클래스를 선언하고 객체를 비교하기 위해 Comparable 인터페이스를 구현하였다. Comparable 인터페이스는 반드시 compare 메소드를 구현해야한다. 그리고 이 메소드를 구현함으로써 객체를 비교할 수 있다. 코드 package 인프런.그리디.회의실배정.방법1; import java.util.ArrayList; import java.util.Collections; import java.util.Scanner..