📌풀이 방법 이 문제는 카운팅 정렬(계수 정렬)을 이용한 문제였다. 처음 접근했을 때, 선택 정렬을 사용하게 되면 O(n^2)로 시간 초과가 나올 것 같아서 카운팅 정렬을 이용하여 문제를 풀었다. 여기서 visit를 boolean으로 한 이유는 문제에서 중복된 숫자가 없다고 했기 때문에 경우의 수는 숫자가 있다, 없다뿐이다. 그래서 count를 세지 않고 true false로만 구별하여 문제를 풀었다. 📌필요한 개념 카운팅 정렬 📌코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 package Sort; import java.io.BufferedReader; import java.io.IOException..

카운팅 정렬 Counting Sort(계수 정렬)은 숫자들의 대소 비교를 하지 않고 나오는 횟수를 가지고 정렬을 하는 알고리즘 방법이다. 숫자가 몇 개 나오는지 센 다음 정렬을 한다. 그래서 시간 복잡도는 O(n)이 나오게 된다. 이번에 카운팅 정렬이라는 것을 처음 보았다. 퀵 정렬, 힙 정렬들의 시간 복잡도는 일반적으로 O(nlogn)으로 정렬 중에 이보다 더 작아질 수 없다고 배웠는데 O(n) 정렬이 있었던 것이다. index를 가지고 정렬을 함 배열의 값은 count의 index로 사용됨. count의 값은 배열의 값이 몇 번 나왔는지 횟수를 의미. count 배열의 값을 누적합으로 변환시킴(이유는 아래에서) count 배열의 값 - 1은 res 배열에서 index를 나타내고, count 배열의 i..

📌List 인터페이스를 구현하는 클래스 - ArrayList, Vector, LinkedList, Stack이 있다. 📌List 특징 - List는 입력 순서대로 데이터가 저장이 되고, Set과 다르게 중복 데이터 저장이 허용된다. 선형 구조로 데이터를 일렬로 놓은 모양이라고 생각하면 된다. 📌List 공통 메소드 boolean add(E e) - 데이터 삽입 void add(int index, E element) - index에 데이터 삽입 void clear() - 데이터 모두 삭제 boolean contains(Object o) - 데이터가 존재하면 true, 없으면 false 리턴 E get(int index) - index의 데이터 리턴 boolean isEmpty() - 데이터가 없으면 tru..

next()와 nextLine()의 차이 next() - 공백을 기준으로 한 단어 또는 한 문자씩 입력받는다. - 버퍼에 입력된 문자나 문자열에서 공백 전까지의 단어를 읽음. 그래서 개행 문자를 가져오지 않는다. nextLine() - 문자 또는 문장 한 라인 전체를 입력받는다. - 버퍼에 입력된 문자열을 개행 문자까지 다 가져온다. ex) Hello World 입력 next() : Hello만 출력 nextLine() : Hello World 출력 nextInt() 사용 후 nextLine() 사용 시 문제 발생 - nextInt()는 개행 문자를 제거하지 않는다. 그래서 버퍼에 개행 문자가 남아있게 된다. 여기서, nextLine()을 사용하게 되면 개행 문자를 만나서 개행 문자를 받게 된다. 따라서..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 package BruteForce_Search; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System...

12345678910111213141516171819202122232425262728293031323334353637import 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 InputStreamReader(System.in)); StringTokenizer st; while(true)..

1234567891011121314151617181920212223242526272829303132333435363738package BruteForce_Search; import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner s = new Scanner(System.in); int a = 0, b = 0, c = 0, sum = 0; a = s.nextInt(); b = s.nextInt(); c = s.nextInt(); sum = s.nextInt(); for(int i = 0; i

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 package BruteForce_Search; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int countarr[]; static int result[]; public st..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 package BruteForce_Search; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syst..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 package BruteForce_Search; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static char[] sang = {'A','B','C','A','B','C','..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 package BruteForce_Search; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new Buffered..