728x90
반응형
SMALL
1. 문자열
1. 문자 찾기
date: 06.03
s 스캐너
.next() 문자열 반환
.charAt(index) 문자 반환
str
.toUpperCase()
.toLowerCase().toCharArray() 문자열을 배열화 해서 for-each 구문을 쓸 수 있다.
Character
.toUpperCase(char)- 문자열 for-each 사용법
for (char c : str.toCharArray()) {
System.out.print(c);
}- 문자 카운트 예시
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
char x = sc.next().charAt(0);
int count = 0;
for (char c : str.toLowerCase().toCharArray()) {
if (Character.toLowerCase(x) == c) {
count++;
}
}
System.out.println(count);
}
}2. 대소문자 변환
Character
isLowerCase(char)- 예시
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
String conversion = "";
for (char c : str.toCharArray()) {
if (Character.isLowerCase(c)) {
conversion += Character.toUpperCase(c);
} else {
conversion += Character.toLowerCase(c);
}
}
System.out.println(conversion);
}
}아스키번호
대문자 : 65~90
소문자 : 97~122
대문자 = 소문자 - 32
String
.split(' ')공백구분
String[] arr = str.split(" ");.length길이반환.indexOf(' ')찾으면 그 값 반환. 없으면 -1 반환 : 있는지 없는지만 확인하고 몇 개 있는지는 확인할 수 없다..substring(startIndex, endIndex)start 부터 end 까지 슬라이스 : 글자 수는 end - start.substring(index)index 부터 끝까지 슬라이스new String[n]크기가 n 인 리스트를 만든다. n = arr.length.charAt(index)index 에 음수가 올 수 없다.
array.length 는 괄호가 없지만 String.length() 는 괄호가 있다.
3. 문장 속 단어
date: 06.08
- 문장에서 가장 긴 단어를 출력합니다.
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int max = 0;
String answer = "";
String str = s.nextLine();
String[] arr = str.split(" ");
for (String string : arr) {
if (max < string.length()) {
max = string.length();
answer = string;
}
}
System.out.println(answer);
}
}4. 단어 뒤집기
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 몇개의 단어를 뒤집을까요?
int n = sc.nextInt();
String[] revArr = new String[n];
// 단어 n 개 만큼 반복
for (int i = 0; i < n; i++) {
String str = sc.next();
int len = str.length();
String reverse = "";
// 단어를 뒤집습니다.
for (int j = 0; j < len; j++) {
reverse += str.charAt(len - j - 1);
}
// 뒤집은 단어를 array 에 넣어 보관합니다.
revArr[i] = reverse;
}
// 뒤집은 단어를 출력합니다.
for (String string : revArr) {
System.out.println(string);
}
}
}인프런
String tmp = new StringBuilder(x) Stiring 의 객체이다.
StringBuilder(String)
.reverse().toString()
ArrayList
add(Object)뒤집은 char 를 한개씩 추가한다.
- 단어를 Array 화 한 후 앞뒤를 변수선언, 앞뒤를 서로 바꾸기.
5. 문자열 배열변환
date: 06.10
- 비 효율적인 코드
int len = str.length();
char[] arr = new char[len];
for (int i = 0; i < len; i++) {
arr[i] = str.charAt(i);
}- 효율적인 코드
char[] arr = str.toCharArray();문자배열 문자열변환
String str = String.valueOf(arr);6. 알파벳 단어 뒤집기
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String scan = sc.next();
char[] arr = scan.toCharArray();
int left = 0;
int right = scan.length() - 1;
while (left < right) {
if (Character.isAlphabetic(arr[left]) & Character.isAlphabetic(arr[right])) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
left++;
right--;
}
String str = String.valueOf(arr);
System.out.print(str);
}
}7. 중복문자제거
date: 06.20
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
String answer = "";
for (int index = 0; index < str.length(); index++) {
char c = str.charAt(index);
// 처음나오는 문자만 answer 에 추가한다.
if (str.indexOf(c) == index) {
answer += c;
}
}
System.out.println(answer);
}
}입력 : ksekkset
출력 : kset
Q. 어떻게 중복되는 문자가 제거됐을까?
A. indexOf(char) 에 답이 있다. indexOf 는 문자가 나오는 첫 번째 인덱스 값을 반환하기 때문에 변수 index 와 같아졌을때만 answer 에 문자를 더하기 때문에 그렇다.
8. 회문문자열 : palindrome
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int back = str.length() - 1;
String answer = "YES";
// 대문자 변환
str = str.toUpperCase();
// 하나라도 다르면 NO 를 반환합니다.
for (int front = 0; front < str.length() / 2; front++) {
if (str.charAt(front) != str.charAt(back)) {
answer = "NO";
break;
}
back--;
}
System.out.println(answer);
}
}StringBuilder 사용
String reverse = new StringBuilder(str).reverse().toString()
builder
.equalsIgnoreCase(String)
9. 유효한 팰린드롬
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
String str = "";
String answer = "YES";
// 알파벳만 반환
for (char c : input.toCharArray()) {
if (Character.isAlphabetic(c)) {
str += c;
}
}
// 대문자 변환
str = str.toUpperCase();
for (int front = 0; front < str.length() / 2; front++) {
int back = str.length() - 1 - front;
if (str.charAt(front) != str.charAt(back)) {
answer = "NO";
break;
}
}
System.out.println(answer);
}
}10. 숫자만 추출
- 직접 작성한 코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.next();
String str = "";
for (char c : input.toCharArray()) {
if (Character.isDigit(c)) {
str += c;
}
}
// 첫 번째 수가 0이면 제거
while (str.charAt(0) == '0') {
str = str.substring(1);
}
System.out.println(str);
}
}- 인프런 강의
숫자 0
9 는 아스키코드로 48
57
조건이 48~57 일 때
answer = answer * 10 + (x - 48)
- 이상적인 코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.next();
String str = "";
int number;
for (char c : input.toCharArray()) {
if (Character.isDigit(c)) {
str += c;
}
}
// 앞에 0 을 없애줍니다.
number = Integer.parseInt(str);
System.out.println(number);
}
}- 아스키코드 활용
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.next();
int number = 0;
for (char c : input.toCharArray()) {
if (c >= 48 & c <= 57) {
number = (number*10) + (c-48);
}
}
System.out.println(number);
}
}11. 가장 짧은 문자거리
Math
.min()
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
char t = sc.next().charAt(0);
ArrayList<Integer> arr = new ArrayList<Integer>();
int order = 0;
int distance = 0;
int first;
int second;
// t 의 인덱스 값을 arr 에 저장
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == t) {
arr.add(i); // 1, 5, 10
}
}
// 첫 번째 인덱스까지
for (int i = 0; i < arr.get(0) + 1; i++) {
distance = arr.get(order) - i;
System.out.print(distance + " ");
}
// 두 인덱스 사이
while (arr.size() - 1 > order) {
first = arr.get(order);
second = arr.get(order + 1);
for (int i = 0; i < (second - first) / 2; i++) {
distance++;
System.out.print(distance + " ");
}
for (int i = 0; i < (second - first) / 2; i++) {
distance = second - i;
System.out.print(distance + " ");
}
System.out.println("\nfirst: " + first + ", second: " + second);
order++;
}
}
}문자열이 무한대
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
char t = sc.next().charAt(0);
int len = s.length();
int[] disArr = new int[len];
int distance = -1;
for (int i = 0; i < len; i++) {
if (s.charAt(i) == t) {
distance = 0;
disArr[i] = distance;
} else if (distance != -1) {
distance++;
disArr[i] = distance;
// 정의되지 않은 곳에 -1 저장
} else {
disArr[i] = distance;
}
}
for (int i = len - 1; i >= 0; i--) {
if (s.charAt(i) == t) {
distance = 0;
} else {
distance++;
}
if (disArr[i] == -1) {
disArr[i] = distance;
}
if (disArr[i] > distance) {
disArr[i] = distance;
}
}
for (int i : disArr) {
System.out.print(i + " ");
}
}
}문자열의 길이가 100 미만
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
char t = sc.next().charAt(0);
int len = s.length();
int[] disArr = new int[len];
int distance = 1000;
for (int i = 0; i < len; i++) {
if (s.charAt(i) == t) {
distance = 0;
disArr[i] = distance;
} else {
distance++;
disArr[i] = distance;
}
}
for (int i = len - 1; i >= 0; i--) {
if (s.charAt(i) == t) {
distance = 0;
} else if (disArr[i] > distance) {
distance++;
disArr[i] = distance;
}
}
for (int i : disArr) {
System.out.print(i + " ");
}
}
}12. 문자열 압축
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int count = 1;
for (int i = 0; i < str.length(); i++) {
if (i < str.length() - 1) {
boolean compress = (str.charAt(i) == str.charAt(i + 1));
if (!compress) {
System.out.print(str.charAt(i));
if (count != 1) {
System.out.print(count);
}
// 출력 후 count 초기화
count = 1;
} else {
count++;
}
// 마지막 문자 비교 : 빈 문자를 추가하면 필요없는 코드이다.
} else {
System.out.print(str.charAt(i));
if (count != 1) {
System.out.print(count);
}
}
}
}
}이상적인 코드
- 마지막문자를 비교할 필요없이 간단히 빈 문자 " " 를 추가합니다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
str += " ";
int count = 1;
for (int i = 0; i < str.length(); i++) {
if (i < str.length() - 1) {
boolean compress = (str.charAt(i) == str.charAt(i + 1));
if (!compress) {
System.out.print(str.charAt(i));
if (count != 1) {
System.out.print(count);
}
// 출력 후 count 초기화
count = 1;
} else {
count++;
}
}
}
}
}13. 암호
str
.replace(oldChar, newChar)
Integer
.parseInt(String, int)int 가 2이면 2진수를 10진수로
2. 배열
1. 보이는 학생
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
int max;
int count = 0;
// 학생들의 키 배열에 넣기
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
// 초기값 설정
max = arr[0];
count++;
// 뒤 학생이 가장 큰 학생보다 크면 카운트
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
count++;
}
}
System.out.println(count);
}
}2. 가위바위보
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
int[] b = new int[n];
// A 가위바위보 정보
for (int i = 0; i < a.length; i++) {
a[i] = sc.nextInt();
}
// B 가위바위보 정보
for (int i = 0; i < b.length; i++) {
b[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
// A 가 이기는 경우
boolean winA = ((a[i] == 1) & (b[i] == 3)) | ((a[i] == 2) & (b[i] == 1)) | ((a[i] == 3) & (b[i] == 2));
// 무승부
if (a[i] == b[i]) {
System.out.println("D");
// A 가 이기는 경우
} else if (winA) {
System.out.println("A");
// B 가 이기는 경우
} else {
System.out.println("B");
}
}
}
}3. 피보나치 수열
date: 06.26
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int first = 1;
int second = 1;
System.out.print(first + " " + second);
for (int i = 0; i < n - 2; i++) {
int temp = first + second;
first = second;
second = temp;
System.out.print(" " + second);
}
}
}4. 소수 (에라토스테네스 체)
에라토스테네스 체 : 소수를 구하는 방법론에서 가장 빠릅니다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int count = 0;
int[] arr = new int[n + 1];
for (int i = 2; i <= n; i++) {
if (arr[i] == 0) {
count++;
for (int j = i; j <= n; j += i) {
arr[j] = 1;
}
}
}
System.out.println(count);
}
}5. 뒤집은 소수
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Loop:
for (int i = 0; i < n; i++) {
String input = sc.next();
String rev = "";
int len = input.length();
int prime = 0;
// 숫자 뒤집기
for (int j = 0; j < len; j++) {
rev += input.charAt(len - j - 1);
// 첫 자리 0 없애기
prime = Integer.parseInt(rev);
}
// 뒤집은 숫자가 1이라면 소수가 아닙니다.
if (prime == 1) {
continue;
}
// 소수가 있으면 다음숫자로 넘어가기
for (int j = 2; j < prime; j++) {
if ((prime % j) == 0) {
continue Loop;
}
}
System.out.print(prime + " ");
}
}
}6. 점수계산
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum = 0;
int stack = 0;
for (int i = 0; i < n; i++) {
int input = sc.nextInt();
if (input == 1) {
sum += 1 + stack;
stack++;
} else {
stack = 0;
}
}
System.out.println(sum);
}
}7. 등수구하기
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] points = new int[n];
for (int i = 0; i < n; i++) {
points[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
int rank = 1;
for (int j = 0; j < n; j++) {
if (points[i] < points[j]) {
rank++;
}
}
System.out.print(rank + " ");
}
}
}8. 격자판 최대합
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int max = 0;
int[][] arr = new int[n][n];
int sum;
// 입력
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = sc.nextInt();
}
}
// 각 행의 합
for (int i = 0; i < n; i++) {
sum = 0;
for (int j = 0; j < n; j++) {
sum += arr[i][j];
}
if (max < sum) {
max = sum;
}
}
// 각 열의 합
for (int i = 0; i < n; i++) {
sum = 0;
for (int j = 0; j < n; j++) {
sum += arr[j][i];
}
if (max < sum) {
max = sum;
}
}
// 각 대각선의 합
sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i][i];
}
if (max < sum) {
max = sum;
}
sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i][n - 1 - i];
}
if (max < sum) {
max = sum;
}
System.out.println(max);
}
}9. 봉우리
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int count = 0;
int[][] arr = new int[num + 2][num + 2];
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
arr[i + 1][j + 1] = sc.nextInt();
}
}
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
boolean n = arr[i + 1][j + 1] > arr[i][j + 1];
boolean e = arr[i + 1][j + 1] > arr[i + 1][j + 2];
boolean w = arr[i + 1][j + 1] > arr[i + 1][j];
boolean s = arr[i + 1][j + 1] > arr[i + 2][j + 1];
if (n & e & w & s) {
count++;
}
}
}
System.out.println(count);
}
}10. 임시반장 정하기
| 1학년 | 2학년 | 3학년 | 4학년 | 5학년 | |
|---|---|---|---|---|---|
| 1번학생 | 2 | 3 | 1 | 7 | 3 |
| 2번학생 | 4 | 1 | 9 | 6 | 8 |
| 3번학생 | 5 | 5 | 2 | 4 | 4 |
| 4번학생 | 6 | 5 | 2 | 6 | 7 |
| 5번학생 | 8 | 4 | 2 | 2 | 2 |
입력
5
2 3 1 7 3
4 1 9 6 8
5 5 2 4 4
6 5 2 6 7
8 4 2 2 2출력
1번 학생은 친구가 0명 입니다.
2번 학생은 친구가 1명 입니다.
3번 학생은 친구가 2명 입니다.
4번 학생은 친구가 3명 입니다.
5번 학생은 친구가 2명 입니다.
학급회장은 4번 학생입니다.import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] classes = new int[n][5];
int[] students = new int[n];
int max = 0;
int president = 0;
// 입력
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
classes[i][j] = sc.nextInt();
}
}
for (int firstStudent = 0; firstStudent < n - 1; firstStudent++) {
for (int secondStudent = firstStudent + 1; secondStudent < n; secondStudent++) {
for (int grade = 0; grade < 5; grade++) {
if (classes[firstStudent][grade] == classes[secondStudent][grade]) {
students[firstStudent]++;
students[secondStudent]++;
break;
}
}
}
}
// 배열에서 가장 친구가 많은 학생 출력
for (int i = 0; i < n; i++) {
if (max < students[i]) {
max = students[i];
president = i + 1;
}
System.out.println(i + 1 + "번 학생은 친구가 " + students[i] + "명 입니다.");
}
System.out.println("학급회장은 " + president + "번 학생입니다.");
}
}Q1. break 을 사용하는 이유는?
A1.
3번학생과 4번학생의 2학년 3학년을 보면 각각 5, 5 와 2, 2 로 같습니다.
for 문에서 학년이 2학년일 때 students++ 로 3번학생과 4번학생의 친구가 하나 늘어났지만
3학년일 때는 동일한 친구이므로 친구를 늘리면 안됩니다. (2, 3학년때 각각 두번 같은 반이었어도 친구는 여전히 한 명이므로)
break 을 실행하면 grade (학년) 를 반복하는 for 문을 빠져나옵니다.
그러므로 같은 학생에 대한 학년의 반복을 막을 수 있습니다.
Q2. president 에 i + 1 을 대입하는 이유는?
A2.
students 배열에 넣을때는 0 부터 넣었으므로 students[0] 은 1번학생, students[1] 은 2번학생, students[2] 은 3번학생...
students[4] 은 5번학생이 됩니다. 그러므로 마지막에 president 에는 i + 1 로 대입하여 출력합니다.
11. 멘토링
이 강의 선생님은 이 문제를 4중 for문으로 푼다..
뭔가 마음에 들지 않아서 여러 시도 중에 있다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] number = new int[m][n];
int firstRank = 0;
int secondRank = 0;
int count = 0;
// 입력
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
number[i][j] = sc.nextInt();
}
}
for (int first = 1; first <= n; first++) {
for (int second = 1; second <= n; second++) {
int mento = 0;
// 같은사람은 ㅣ등수를 비교하지 않는다.
if (first == second) {
continue;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (number[i][j] == first) {
firstRank = j;
} else if (number[i][j] == second) {
secondRank = j;
}
}
if (firstRank >= secondRank) {
break;
}
mento++;
if (mento == m) {
count++;
}
}
}
}
System.out.println(count);
}
}3. Two pointers&Sliding window
이 문서에서는 two pointers 알고리즘과 sliding window 알고리즘을 사용하여 O($$n^2$$) 의 복잡도를 O(n) 으로 만듭니다.
for 문 안에 while 문과 if 문이 들어간 것이 이상적입니다. (4~6번 알고리즘)
for(){
while(){
}
if(){
}
}1. 두 배열 합치기
크기가 n 인 배열과 크기가 m 인 배열을 오름차순으로 정렬된 하나의 배열로 합치시오.
입력
3
1 3 5
5
2 3 6 7 9출력
1 2 3 3 5 6 7 9두 가지 방법을 모두 해봤지만 코드의 길이도 비슷해 어떤 것을 해도 무방할 것처럼 보인다.
for 문과 String 에 담아 출력
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr1 = new int[n];
int index1 = 0;
int index2 = 0;
// 첫 번째 배열 입력
for (int i = 0; i < n; i++) {
arr1[i] = sc.nextInt();
}
int m = sc.nextInt();
int[] arr2 = new int[m];
// 두 번째 배열 입력
for (int i = 0; i < m; i++) {
arr2[i] = sc.nextInt();
}
for (int i = 0; i < n + m; i++) {
// 첫 번째 배열이 더 이상 없을 때
if (index1 == n) {
while (index2 < m) {
System.out.print(arr2[index2] + " ");
index2++;
}
break;
}
// 두 번째 배열이 더 이상 없을 때
if (index2 == m) {
while (index1 < n) {
System.out.print(arr1[index1] + " ");
index1++;
}
break;
}
// 배열의 앞에서 작은 값을 반환합니다.
if (arr1[index1] < arr2[index2]) {
System.out.print(arr1[index1] + " ");
index1++;
} else {
System.out.print(arr2[index2] + " ");
index2++;
}
}
}
}while 문과 배열에 담아 출력
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr1 = new int[n];
int index1 = 0;
int index2 = 0;
ArrayList<Integer> numbers = new ArrayList<Integer>();
// 첫 번째 배열 입력
for (int i = 0; i < n; i++) {
arr1[i] = sc.nextInt();
}
int m = sc.nextInt();
int[] arr2 = new int[m];
// 두 번째 배열 입력
for (int i = 0; i < m; i++) {
arr2[i] = sc.nextInt();
}
while ((n > index1) & (m > index2)) {
// 배열의 앞에서 작은 값을 반환합니다.
if (arr1[index1] < arr2[index2]) {
numbers.add(arr1[index1++]);
} else {
numbers.add(arr2[index2++]);
}
}
// 첫 번째 배열이 더 이상 없을 때
if (index1 == n) {
while (index2 < m) {
numbers.add(arr2[index2++]);
}
// 두 번째 배열이 더 이상 없을 때
} else {
while (index1 < n) {
numbers.add(arr1[index1++]);
}
}
for (int i : numbers) {
System.out.print(i + " ");
}
}
}2. 공통원소 구하기
정렬
배열에 담아 Arrays.sort(arr) 해도되고
저처럼 ArrayList 에 담아 arr.sort(null) 해도 됩니다.
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> arr1 = new ArrayList<Integer>();
ArrayList<Integer> arr2 = new ArrayList<Integer>();
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
arr1.add(sc.nextInt());
}
int m = sc.nextInt();
for (int i = 0; i < m; i++) {
arr2.add(sc.nextInt());
}
// 정렬
arr1.sort(null);
arr2.sort(null);
while ((arr1.size() > 0) & arr2.size() > 0) {
// 첫 번째 배열이 작을경우 배열의 첫 번째 수 제거
if (arr1.get(0) < arr2.get(0)) {
arr1.remove(0);
// 두 번재 배열이 작을경우 배열의 첫 번째 수 제거
} else if (arr1.get(0) > arr2.get(0)) {
arr2.remove(0);
// 두 배열의 첫 번째 수가 같을경우 출력하고 제거
} else {
System.out.print(arr1.get(0) + " ");
arr1.remove(0);
arr2.remove(0);
}
}
}
}3. 최대 매출
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[n];
int sum = 0;
int max = 0;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int i = 0; i < k - 1; i++) {
sum += arr[i];
}
for (int left = 0; left <= n - k; left++) {
int right = k - 1 + left;
sum += arr[right];
if (max < sum) {
max = sum;
}
sum -= arr[left];
}
System.out.println(max);
}
}4. 연속 부분수열
N개의 수열 에서 연속부분수열의 합이 M 이 되는 경우의 수
입력
8 6
1 2 1 3 1 1 1 2출력
+1+2+1+3-1
1가지
+1-2+1
2가지
+1-1
3가지
+2-3입력
8 6
1 1 1 1 1 5 3 2출력
+1+1+1+1+1+5-1-1-1-1
1가지
+3-1-5+2설명없는 코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] arr = new int[n];
int sum = 0;
int tail = 0;
int count = 0;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int head = 0; head < n; head++) {
sum += arr[head];
while (sum > m) {
sum -= arr[tail++];
}
if (sum == m) {
count++;
}
}
System.out.println(count);
}
}설명출력 코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] arr = new int[n];
int sum = 0;
int tail = 0;
int count = 0;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int head = 0; head < n; head++) {
sum += arr[head];
System.out.print("+" + arr[head]);
while (sum > m) {
System.out.print("-" + arr[tail]);
sum -= arr[tail++];
}
if (sum == m) {
count++;
System.out.println("\n" + count + "가지");
}
}
}
}5. 연속된 자연수의 합
2개 이상의 연속된 자연수의 합으로 정수 N 을 표현하는 방법의 가짓수를 출력
- 7+8=15
- 4+5+6=15
- 1+2+3+4+5=15
답은 3가지이다.
입력
15출력
+1+2+3+4+5
1가지
+6-1-2-3
2가지
+7-4-5+8-6
3가지설명없는 코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int count = 0;
int sum = 0;
int tail = 1;
for (int head = 1; head <= (n / 2) + 1; head++) {
sum += head;
while (sum > n) {
sum -= tail++;
}
if (sum == n) {
count++;
}
}
System.out.println(count);
}
}설명출력 코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int count = 0;
int sum = 0;
int tail = 1;
for (int head = 1; head <= (n / 2) + 1; head++) {
System.out.print("+" + head);
sum += head;
while (sum > n) {
System.out.print("-" + tail);
sum -= tail++;
}
if (sum == n) {
count++;
System.out.println();
System.out.println(count + "가지");
}
}
}
}6. 최대 길이 연속부분수열
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[n];
int max = 0;
int length = 0;
int count = 0;
int tail = 0;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int head = 0; head < n; head++) {
if (arr[head] == 0) {
count++;
}
while (count > k) {
if (arr[tail] == 0) {
count--;
}
tail++;
}
length = head - tail + 1;
if (max < length) {
max = length;
}
}
System.out.println(max);
}
}4. HashMap&TreeSet
학급 회장
- 문자열의 HashMap 초기값 설정 및 카운팅
for (char key : str.toCharArray()) {
int value = map.getOrDefault(key, 0);
map.put(key, value + 1);
}- 숫자의 HashMap 초기값 설정 및 카운팅
for (int i = 0; i < n; i++) {
int key = sc.nextInt();
int value = map.getOrDefault(key, 0);
map.put(key, value + 1);
}import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String vote = sc.next();
char answer = ' ';
int max = 0;
// 학급회장 투표
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (char key : vote.toCharArray()) {
int value = map.getOrDefault(key, 0);
map.put(key, value + 1);
}
// 학급회장 개표
for (char key : map.keySet()) {
System.out.println(key + " " + map.get(key));
if (max < map.get(key)) {
max = map.get(key);
answer = key;
}
}
System.out.println(answer);
}
}HashMap 에 입력하는 것은 toCharArray(), 출력하는 것은 KeySet()
map
.put(key, value).get(key).getOrDefault(key, Integer defaultValue): 값이 없으면 defaultValue 값을 가져옵니다..keySet()key 값을 모두 불러옵니다. : for-each 구문 사용.containsKey(Key)boolean : Key 가 있나요?.size()Key 갯수.remove(Key)
아나그램 : Anagram
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.nextLine();
String str2 = sc.nextLine();
HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();
// 문자열을 HashMap 으로
for (char key : str1.toCharArray()) {
int value = map1.getOrDefault(key, 0);
map1.put(key, value + 1);
}
for (char key : str2.toCharArray()) {
int value = map2.getOrDefault(key, 0);
map2.put(key, value + 1);
}
if (map1.equals(map2)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}매출액의 종류
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[n];
String answer = "";
// 숫자들을 배열에
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
for (int i = 0; i < n - k + 1; i++) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int j = 0; j < k; j++) {
// 숫자들의 배열을 HashMap 으로
int value = map.getOrDefault(arr[i + j], 0);
map.put(arr[i + j], value + 1);
}
answer += map.size() + " ";
}
System.out.println(answer);
}
}모든 아나그램 찾기
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String t = sc.nextLine();
int count = 0;
char[] arr = s.toCharArray();
HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();
for (char key : t.toCharArray()) {
int value = map2.getOrDefault(key, 0);
map2.put(key, value + 1);
}
for (int i = 0; i < s.length() - t.length() + 1; i++) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int j = 0; j < t.length(); j++) {
int value = map.getOrDefault(arr[i + j], 0);
map.put(arr[i + j], value + 1);
if (map.equals(map2)) {
count++;
}
}
}
System.out.println(count);
}
}Sliding window algorithm
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String t = sc.nextLine();
int count = 0;
HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();
HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
// 두 번째 문자열 HashMap 에 담기
for (char key : t.toCharArray()) {
int value = map2.getOrDefault(key, 0);
map2.put(key, value + 1);
}
// 첫 번째 문자열의 일부분 HashMap 에 담기
for (int i = 0; i < t.length(); i++) {
int value = map1.getOrDefault(s.charAt(i), 0);
map1.put(s.charAt(i), value + 1);
}
// 중복되는 코드
if (map1.equals(map2)) {
count++;
}
// Sliding window algorithm 을 이용해 HashMap 에 한 개씩 추가하고 제거하기
for (int i = 0; i < s.length() - t.length(); i++) {
int left = i;
int right = i + t.length();
int valueRight = map1.getOrDefault(s.charAt(right), 0);
map1.put(s.charAt(right), valueRight + 1);
int valueLeft = map1.get(s.charAt(left));
map1.put(s.charAt(left), valueLeft - 1);
if (map1.get(s.charAt(left)) == 0) {
map1.remove(s.charAt(left));
}
// 문자열1과 문자열2가 아나그램이라면 count 를 1 증가시킨다.
if (map1.equals(map2)) {
count++;
}
}
System.out.println(count);
}
}Sliding window algorithm 개선
- 위 코드는
count++가 중복되므로 문자열을 한 개 덜 담으므로써 중복코드를 없앱니다.
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String t = sc.nextLine();
int count = 0;
HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();
// 두 번째 문자열 HashMap 에 담기
for (char key : t.toCharArray()) {
int value = map2.getOrDefault(key, 0);
map2.put(key, value + 1);
}
// 첫 번째 문자열의 일부분 HashMap 에 담기 : 문자열을 한 개 덜 담습니다.
for (int i = 0; i < t.length() - 1; i++) {
int value = map1.getOrDefault(s.charAt(i), 0);
map1.put(s.charAt(i), value + 1);
}
// Sliding window algorithm 을 이용해 HashMap 에 한 개씩 추가
for (int i = 0; i < s.length() - t.length() + 1; i++) {
int left = i;
int right = i + t.length() - 1;
int valueRight = map1.getOrDefault(s.charAt(right), 0);
map1.put(s.charAt(right), valueRight + 1);
// 문자열1과 문자열2가 아나그램이라면 count 를 1 증가시킨다.
if (map1.equals(map2)) {
count++;
}
// 한 개씩 제거
int valueLeft = map1.get(s.charAt(left));
map1.put(s.charAt(left), valueLeft - 1);
if (map1.get(s.charAt(left)) == 0) {
map1.remove(s.charAt(left));
}
}
System.out.println(count);
}
}k번째 큰 수
date: 06.20
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
int[] arr = new int[N];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
ArrayList<Integer> arrList = new ArrayList<Integer>();
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
// 세 수의 합을 HashMap 에 저장
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
for (int k = j + 1; k < arr.length; k++) {
int key = arr[i] + arr[j] + arr[k];
int value = map.getOrDefault(key, 0);
map.put(key, value + 1);
}
}
}
// 정렬하기 위해 arrayList 에 저장
for (int key : map.keySet()) {
arrList.add(key);
}
// 정렬 후 세 번째로 큰 수 출력
arrList.sort(null);
System.out.println(arrList.get(arrList.size() - 3));
}
}TreeSet
중복도 제거하며 정렬도 된다.
TreeSet<Integer> tree = new TreeSet<Integer>(Collections.reverseOrder()) 기본은 오름차순, reverseOrder 시 내림차순
tree
add(value)remove(value)first()last()
TreeSet 으로 풀기
import java.util.Collections;
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
int[] arr = new int[N];
TreeSet<Integer> tree = new TreeSet<Integer>(Collections.reverseOrder());
// 숫자 입력받아 배열에 저장
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
// 세 수의 합을 TreeSet 에 저장
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
for (int k = j + 1; k < arr.length; k++) {
int key = arr[i] + arr[j] + arr[k];
tree.add(key);
}
}
}
// 세 번째로 큰 수 출력
int num = 0;
for (Integer key : tree) {
num++;
if (num == 3) {
System.out.println(key);
break;
}
}
}
}5. Stack&queue
Stack
1. 올바른 괄호
Stack 은 구덩이, Queue 는 원통의 통로
LIFO 구조
stack
push()넣기pop()꺼내기isEmpty()비어있으면 true 반환
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
Stack<Character> stack = new Stack<>();
String answer = "YES";
for (char c : str.toCharArray()) {
if (c == '(') {
stack.push(c);
} else if (stack.isEmpty()) {
answer = "NO";
break;
} else {
stack.pop();
}
}
if (!stack.isEmpty()) {
answer = "NO";
}
System.out.println(answer);
}
}2. 괄호문자제거
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
Stack<Character> stack = new Stack<>();
for (char c : str.toCharArray()) {
if (c == '(') {
stack.push(c);
} else if (c == ')') {
stack.pop();
}
if (stack.isEmpty() & Character.isAlphabetic(c)) {
System.out.print(c);
}
}
}
}3. 크레인 인형뽑기 (카카오)
크레인에서 [1, 5, 3] 의 순서로 인형을 뽑은 예시
)
입력
첫 줄에 자연수 N 이 주어집니다.
두 번째 줄부터 N*N board 배열이 주어집니다.
0은 빈 칸을 나타냅니다.
board 의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
board배열이 끝난 다음줄에 moves 배열의 길이 M이 주어집니다.
마지막 줄에는 moves 배열이 주어집니다.
moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.
5
0 0 0 0 0
0 0 1 0 3
0 2 5 0 1
4 2 4 4 2
3 5 1 3 1
8
1 5 3 5 1 2 1 4출력
첫 줄에 터트려져 사라진 인형의 개수를 출력합니다.
4최적화 코드
class Solution {
public int solution(int[][] board, int[] moves) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
int count = 0;
pick: for (int move : moves) {
int col = 0;
int row = move - 1;
while (board[col][row] == 0) {
col++;
if (col == board.length) continue pick;
}
int pick = board[col][row];
if (stack.lastElement() == pick) {
stack.pop();
count += 2;
} else stack.push(pick);
board[col][row] = 0;
}
return count;
}
}코드
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Stack<Integer> stack = new Stack<>();
int n = sc.nextInt();
int[][] board = new int[n][n];
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = sc.nextInt();
}
}
int m = sc.nextInt();
int[] moves = new int[m];
// 입력
for (int i = 0; i < m; i++) {
moves[i] = sc.nextInt();
}
stack.push(0);
loop:
for (int i = 0; i < m; i++) {
int height = 0;
while (board[height][moves[i] - 1] == 0) {
height++;
if (height == n) {
continue loop;
}
}
int pick = board[height][moves[i] - 1];
if (stack.lastElement() == pick) {
stack.pop();
count += 2;
} else {
stack.push(pick);
}
board[height][moves[i] - 1] = 0;
}
System.out.println(count);
}
}4. 후위식 연산 (postfix)
입력
352+*9-출력
12코드
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Stack<Integer> stack = new Stack<>();
String str = sc.next();
for (char c : str.toCharArray()) {
int first;
int second;
int answer = 0;
if (Character.isDigit(c)) {
stack.push(c - 48);
} else {
second = stack.pop();
first = stack.pop();
switch (c) {
case '+':
answer = first + second;
break;
case '-':
answer = first - second;
break;
case '*':
answer = first * second;
break;
case '/':
answer = first / second;
break;
default:
break;
}
stack.push(answer);
}
}
System.out.println(stack.pop());
}
}5. 쇠막대기
조건
- 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되,
끝점은 겹치지 않도록 놓는다. - 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
- 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.
설명
- 모든 ‘( ) ’는 반 드시 레이저를 표현한다.
- 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.
- 이와 같은 방식으로 주어진 쇠막대기들은 총 17 개의 조각으로 잘려진다.
입력
()(((()())(())()))(())출력
17코드
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Stack<Character> stack = new Stack<>();
String str = sc.next();
int answer = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
stack.push('(');
} else {
stack.pop();
if (str.charAt(i - 1) == '(') {
answer += stack.size();
} else {
answer++;
}
}
}
System.out.println(answer);
}
}Queue
queue
offer(value)poll()peek()확인만size()contains(x)
FIFO: first in first out
선언
Queue<Integer> queue = new LinkedList<Integer>();Q. Queue 에서 add 와 offer 의 차이점은?
A. add() 는 Collection 프레임워크에서 오고 offer() 는 Queue 프레임워크에서 옵니다.
add() 는 항상 true 를 반환하고 용량문제로 넣지못할 때에는 throws 예외를 발생시킵니다.
반면 offer() 는 넣지못할 때에는 false 를 반환합니다.
https://stackoverflow.com/questions/15591431/difference-between-offer-and-add-in-priority-queue-in-java{:target="_blank"}
6. 공주구하기
1번 왕자부터 시계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다.
한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다.
그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다.
예시
예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 왕자가 3을 외쳐 제외된다.
이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고 마지막까지 남게 된 7번 왕자에게 공주를 구하러갑니다.
입력
8 3출력
7코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Queue<Integer> queue = new LinkedList<Integer>();
int n = sc.nextInt();
int k = sc.nextInt();
for (int i = 1; i <= n; i++) {
queue.offer(i);
}
while (queue.size() != 1) {
for (int i = 1; i < k; i++) {
queue.offer(queue.poll());
}
queue.poll();
}
System.out.println(queue.poll());
}
}7. 교육과정 설계
예시
만약 총 과목이 A, B, C, D, E, F, G가 있고, 여기서 필수과목이 CBA로 주어지면 필수과목은 C, B, A과목이며 이 순서대로 꼭 수업계획을 짜야 합니다.
필수과목순서가 주어지면 현수가 짠 N개의 수업설계가 잘된 것이면 “YES", 잘못된 것이면 ”NO“를 출력하는 프로그램을 작성하세요.
입력
CBA
CBDAGE출력
YES코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Queue<Character> queue = new LinkedList<>();
String require = sc.next();
String subject = sc.next();
int count = 0;
for (char c : require.toCharArray()) {
queue.offer(c);
}
for (char c : subject.toCharArray()) {
if (queue.peek() == c) {
count++;
queue.poll();
if (queue.isEmpty()) {
break;
}
}
}
if (count == require.length()) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}8. 응급실
• 환자가 접수한 순서대로의 목록에서 제일 앞에 있는 환자목록을 꺼냅니다.
• 나머지 대기 목록에서 꺼낸 환자 보다 위험도가 높은 환자가 존재하면 대기목록 제일 뒤로 다시 넣습니다. 그렇지 않으면 진료를 받습니다.
즉 대기목록에 자기 보다 위험도가 높은 환자가 없을 때 자신이 진료를 받는 구조입니다.
현재 N명의 환자가 대기목록에 있습니다.
N명의 대기목록 순서의 환자 위험도가 주어지면, 대기목록상의 M번째 환자는 몇 번째로 진료를 받는지 출력하는 프로그램을 작성하세요.
대기목록상의 M번째는 대기목록의 제일 처음 환자를 0번째로 간주하여 표현한 것입니다.
M번째 환자는 몇 번째로 진료받는지 출력하세요.
예시
위험도가 70인 2번째 환자는 3번째로 진료를 받는다.
입력
5 2
60 50 70 80 90출력
[0환자:위험도60, 1환자:위험도50, 2환자:위험도70, 3환자:위험도80, 4환자:위험도90]
0환자:위험도60를 뒤로 보냅니다.
[1환자:위험도50, 2환자:위험도70, 3환자:위험도80, 4환자:위험도90, 0환자:위험도60]
1환자:위험도50를 뒤로 보냅니다.
[2환자:위험도70, 3환자:위험도80, 4환자:위험도90, 0환자:위험도60, 1환자:위험도50]
2환자:위험도70를 뒤로 보냅니다.
[3환자:위험도80, 4환자:위험도90, 0환자:위험도60, 1환자:위험도50, 2환자:위험도70]
3환자:위험도80를 뒤로 보냅니다.
[4환자:위험도90, 0환자:위험도60, 1환자:위험도50, 2환자:위험도70, 3환자:위험도80]
1번째 진료는 4환자:위험도90입니다.
0환자:위험도60를 뒤로 보냅니다.
[1환자:위험도50, 2환자:위험도70, 3환자:위험도80, 0환자:위험도60]
1환자:위험도50를 뒤로 보냅니다.
[2환자:위험도70, 3환자:위험도80, 0환자:위험도60, 1환자:위험도50]
2환자:위험도70를 뒤로 보냅니다.
[3환자:위험도80, 0환자:위험도60, 1환자:위험도50, 2환자:위험도70]
2번째 진료는 3환자:위험도80입니다.
0환자:위험도60를 뒤로 보냅니다.
[1환자:위험도50, 2환자:위험도70, 0환자:위험도60]
1환자:위험도50를 뒤로 보냅니다.
[2환자:위험도70, 0환자:위험도60, 1환자:위험도50]
3번째 진료는 2환자:위험도70입니다.설명없는 코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Person {
int id;
int risk;
public Person(int id, int risk) {
this.id = id;
this.risk = risk;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Queue<Person> queue = new LinkedList<>();
int n = sc.nextInt();
int m = sc.nextInt();
int order = 1;
boolean pass;
for (int i = 0; i < n; i++) {
int risk = sc.nextInt();
queue.offer(new Person(i, risk));
}
while (true) {
pass = false;
for (Person person : queue) {
if (queue.peek().risk < person.risk) {
queue.offer(queue.poll());
pass = true;
break;
}
}
if (!pass) {
if (queue.poll().id == m) {
System.out.println(order);
break;
}
order++;
}
}
}
}설명포함 코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Person {
int id;
int risk;
public Person(int id, int risk) {
this.id = id;
this.risk = risk;
}
@Override
public String toString() {
return id + "환자:위험도" + risk;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Queue<Person> queue = new LinkedList<>();
int n = sc.nextInt();
int m = sc.nextInt();
int order = 1;
boolean pass;
for (int i = 0; i < n; i++) {
int risk = sc.nextInt();
queue.offer(new Person(i, risk));
}
System.out.println(queue);
while (true) {
pass = false;
for (Person person : queue) {
if (queue.peek().risk < person.risk) {
System.out.println(queue.peek() + "를 뒤로 보냅니다.");
queue.offer(queue.poll());
System.out.println(queue);
pass = true;
break;
}
}
if (!pass) {
System.out.println(order + "번째 진료는 " + queue.peek() + "입니다.");
if (queue.poll().id == m) {
break;
}
order++;
}
}
}
}6. Sorting&Searching
정렬알고리즘 애니메이션
https://www.toptal.com/developers/sorting-algorithms{:target="_blank"}
1. 선택정렬
가장 작은 수를 찾아 앞에서부터 정렬한다.
비교정렬이자 제자리정렬
시간복잡도는 $$O(N^2)$$ 이다.
항상 비슷한 시간이 걸린다.
입력
6
13 5 11 7 23 15출력
13과 5을 바꿉니다.
[5, 13, 11, 7, 23, 15]
13과 7을 바꿉니다.
[5, 7, 11, 13, 23, 15]
11과 11을 바꿉니다.
[5, 7, 11, 13, 23, 15]
13과 13을 바꿉니다.
[5, 7, 11, 13, 23, 15]
23과 15을 바꿉니다.
[5, 7, 11, 13, 15, 23]swap 메서드사용 코드
public class Main {
public static void main(String[] args) {
int n = 10;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = (int) (Math.random() * 50);
}
for (int i = 0; i < n - 1; i++) {
int index = i;
for (int j = i + 1; j < n; j++) {
if (arr[index] > arr[j]) {
index = j;
}
}
swap(arr, i, index);
}
System.out.println(Arrays.toString(arr));
}
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}메소드없는 코드
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int i = 0; i < n - 1; i++) {
int index = i;
for (int j = i + 1; j < n; j++) {
if (arr[index] > arr[j]) {
index = j;
}
}
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
System.out.println(Arrays.toString(arr));
}
}설명포함 코드
public class Main {
public static void main(String[] args) {
int n = 10;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = (int) (Math.random() * 50);
}
for (int i = 0; i < n - 1; i++) {
int index = i;
for (int j = i + 1; j < n; j++) {
if (arr[index] > arr[j]) {
index = j;
}
}
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
System.out.println(temp + "과 " + arr[i] + "을 바꿉니다.");
System.out.println(Arrays.toString(arr));
}
}
}2. 버블정렬
이웃한 것 끼리 비교하여 정렬
이미 거의 정렬된 상태에서 빠르다.
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < n - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}3. 삽입정렬
이미 거의 정렬된 상태에서 빠르다.
i 는 1부터 증가, j 는 감소하며 i 값을 끼워넣는다.
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int i = 1; i < n; i++) {
int target = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > target) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = target;
}
System.out.println(Arrays.toString(arr));
}
}| 정렬 | 초기값 | 최종값 | 초기값 | 최종값 |
|---|---|---|---|---|
| 선택정렬 | 0 | n-1 | i+1 | n |
| 버블정렬 | 1 | n | 0 | n-i |
| 삽입정렬 | 1 | n | i-1 | 0 보다 크다 |
4. LRU: Least Recently Used
캐시, 카카오 변형
입력
5 9
1 2 3 2 6 2 3 5 7출력
Cache Miss
[1, 0, 0, 0, 0]: 1
Cache Miss
[1, 1, 0, 0, 0]: 1을 밀었습니다.
[2, 1, 0, 0, 0]: 2
Cache Miss
[2, 1, 1, 0, 0]: 1을 밀었습니다.
[2, 2, 1, 0, 0]: 2을 밀었습니다.
[3, 2, 1, 0, 0]: 3
Cache Hit
2가 1위치에 있습니다.
Cache Miss
[3, 3, 1, 0, 0]: 3을 밀었습니다.
[2, 3, 1, 0, 0]: 2
Cache Miss
[2, 3, 1, 1, 0]: 1을 밀었습니다.
[2, 3, 3, 1, 0]: 3을 밀었습니다.
[2, 2, 3, 1, 0]: 2을 밀었습니다.
[6, 2, 3, 1, 0]: 6
Cache Hit
2가 1위치에 있습니다.
Cache Miss
[6, 6, 3, 1, 0]: 6을 밀었습니다.
[2, 6, 3, 1, 0]: 2
Cache Hit
3가 2위치에 있습니다.
Cache Miss
[2, 6, 6, 1, 0]: 6을 밀었습니다.
[2, 2, 6, 1, 0]: 2을 밀었습니다.
[3, 2, 6, 1, 0]: 3
Cache Miss
[3, 2, 6, 1, 1]: 1을 밀었습니다.
[3, 2, 6, 6, 1]: 6을 밀었습니다.
[3, 2, 2, 6, 1]: 2을 밀었습니다.
[3, 3, 2, 6, 1]: 3을 밀었습니다.
[5, 3, 2, 6, 1]: 5
Cache Miss
[5, 3, 2, 6, 6]: 6을 밀었습니다.
[5, 3, 2, 2, 6]: 2을 밀었습니다.
[5, 3, 3, 2, 6]: 3을 밀었습니다.
[5, 5, 3, 2, 6]: 5을 밀었습니다.
[7, 5, 3, 2, 6]: 7설명없는 코드
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int c = sc.nextInt();
int w = sc.nextInt();
int[] cash = new int[c];
int[] work = new int[w];
for (int i = 0; i < w; i++) {
work[i] = sc.nextInt();
}
for (int i = 0; i < w; i++) {
int index = c - 1;
for (int j = 0; j < c; j++) {
if (work[i] == cash[j]) {
index = j;
break;
}
}
for (int j = index; j > 0; j--) {
if (cash[j] != cash[j - 1]) {
cash[j] = cash[j - 1];
}
}
cash[0] = work[i];
}
System.out.println(Arrays.toString(cash));
}
}설명있는 코드
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int c = sc.nextInt();
int w = sc.nextInt();
int[] cash = new int[c];
int[] work = new int[w];
for (int i = 0; i < w; i++) {
work[i] = sc.nextInt();
}
for (int i = 0; i < w; i++) {
int index = c - 1;
boolean miss = false;
for (int j = 0; j < c; j++) {
if (work[i] == cash[j]) {
System.out.println("Cache Hit");
System.out.println(work[i] + "가 " + j + "위치에 있습니다.");
index = j;
break;
} else {
miss = true;
}
}
if (miss) {
System.out.println("Cache Miss");
}
for (int j = index; j > 0; j--) {
if (cash[j] != cash[j - 1]) {
cash[j] = cash[j - 1];
System.out.println(Arrays.toString(cash) + ": " + cash[j - 1] + "을 밀었습니다.");
}
}
cash[0] = work[i];
System.out.println(Arrays.toString(cash) + ": " + cash[0]);
}
}
}5. 중복확인
이 문제는 HashMap 으로도 풀 수 있을 것 같다.
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] numbers = new int[n];
char answer = 'U';
for (int i = 0; i < n; i++) {
numbers[i] = sc.nextInt();
}
loop:
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (numbers[i] == numbers[j]) {
answer = 'D';
break loop;
}
}
}
System.out.println(answer);
}
}6. 장난꾸러기
입력
9
120 125 152 130 135 135 143 127 160출력
3 8 *코드 *
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
int[] sorted = new int[n];
int number = 1;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
sorted = arr.clone();
for (int i = 1; i < n; i++) {
int target = sorted[i];
int j = i - 1;
while (j >= 0 && sorted[j] > target) {
sorted[j + 1] = sorted[j];
j--;
}
sorted[j + 1] = target;
}
for (int i = 0; i < n; i++) {
if (arr[i] != sorted[i]) {
System.out.print(number + " ");
}
number++;
}
}
}7. 객체정렬: compareTo
x, y 좌표를 정렬하는 문제입니다.
compareTo 메서드구현 코드
class Point implements Comparable<Point> {
int x;
int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Point o) {
if (this.x == o.x) {
return this.y - o.y;
}
return this.x - o.x;
}
}public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Point> arr = new ArrayList<>();
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
arr.add(new Point(x, y));
}
Collections.sort(arr);
for (Point point : arr) {
System.out.println(point.x + " " + point.y);
}
}
}입력
5
2 7
1 3
1 2
2 5
3 6출력
[2 7, 2 7, 1 2, 2 5, 3 6]: 2 7를 밉니다.
[1 3, 2 7, 1 2, 2 5, 3 6]
[1 3, 2 7, 2 7, 2 5, 3 6]: 2 7를 밉니다.
[1 3, 1 3, 2 7, 2 5, 3 6]: 1 3를 밉니다.
[1 2, 1 3, 2 7, 2 5, 3 6]
[1 2, 1 3, 2 7, 2 7, 3 6]: 2 7를 밉니다.
[1 2, 1 3, 2 5, 2 7, 3 6]
[1 2, 1 3, 2 5, 2 7, 3 6]삽입정렬구현 코드
class Coordinate implements Cloneable {
int x;
int y;
Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return x + " " + y;
}
@Override
protected Coordinate clone() throws CloneNotSupportedException {
return (Coordinate) super.clone();
}
}public class Main {
public static void main(String[] args) throws CloneNotSupportedException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Coordinate[] coordinates = new Coordinate[n];
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
coordinates[i] = new Coordinate(x, y);
}
for (int i = 1; i < n; i++) {
Coordinate target = coordinates[i];
int j = i - 1;
while (j >= 0 && coordinates[j].x >= target.x) {
if (coordinates[j].x > target.x) {
coordinates[j + 1] = coordinates[j].clone();
System.out.println(Arrays.toString(coordinates) + ": " + coordinates[j].x + ", " + coordinates[j].y + "를 밉니다.");
j--;
} else if (coordinates[j].y > target.y) {
coordinates[j + 1] = coordinates[j].clone();
System.out.println(Arrays.toString(coordinates) + ": " + coordinates[j].x + ", " + coordinates[j].y + "를 밉니다.");
j--;
}
}
coordinates[j + 1] = target.clone();
System.out.println(Arrays.toString(coordinates));
}
}
}8. 이분검색: Binary search
이 교수님이 페이지를 찾는데 책을 찢는 것과 같은 방법이다.
책 예시{:target="_brank"}
이분검색은 정렬이 되어있어야 합니다.
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] arr = new int[n];
int left = 0;
int right = n - 1;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
while (left <= right) {
int mid = (left + right) / 2;
if (m == arr[mid]) {
System.out.println(mid + 1);
break;
} else if (m < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
}9. 결정알고리즘: 뮤직비디오
Arrays.stream(arr)
.max().getAsInt().sum()
입력
9 3
1 2 3 4 5 6 7 8 9출력
left: 9, right: 45, mid: 27
2<=3
answer: 27, right: 26
left: 9, right: 26, mid: 17
3<=3
answer: 17, right: 16
left: 9, right: 16, mid: 12
5>3
answer: 17, left: 13
left: 13, right: 16, mid: 14
5>3
answer: 17, left: 15
left: 15, right: 16, mid: 15
4>3
answer: 17, left: 16
left: 16, right: 16, mid: 16
4>3
answer: 17, left: 17설명없는 코드
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] arr = new int[n];
int answer = 0;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int left = Arrays.stream(arr).max().getAsInt();
int right = Arrays.stream(arr).sum();
while (left <= right) {
int mid = (left + right) / 2;
if (count(arr, mid) <= m) {
answer = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
System.out.println(answer);
}
static int count(int[] arr, int DVD) {
int sum = 0;
int count = 1;
for (int minute : arr) {
if (sum + minute > DVD) {
count++;
sum = 0;
}
sum += minute;
}
return count;
}
}설명있는 코드
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] arr = new int[n];
int answer = 0;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int left = Arrays.stream(arr).max().getAsInt();
int right = Arrays.stream(arr).sum();
while (left <= right) {
int mid = (left + right) / 2;
System.out.println("left: " + left + ", right: " + right + ", mid: " + mid);
if (count(arr, mid) <= m) {
answer = mid;
right = mid - 1;
System.out.println(count(arr, mid) + "<=" + m);
System.out.println("answer: " + answer + ", right: " + right);
} else {
left = mid + 1;
System.out.println(count(arr, mid) + ">" + m);
System.out.println("answer: " + answer + ", left: " + left);
}
}
}
static int count(int[] arr, int DVD) {
int sum = 0;
int count = 1;
for (int minute : arr) {
if (sum + minute > DVD) {
count++;
sum = 0;
}
sum += minute;
}
return count;
}
}10. 결정알고리즘: 마구간 정하기
N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.
현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고,
가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.
입력
5 3
1 2 8 4 9출력
[1, 2, 4, 8, 9]
left: 1, right: 8, mid: 4
5>=8, count: 2
left: 1, right: 3, mid: 2
3>=4, count: 2
6>=8, count: 3
left: 3, right: 3, mid: 3
4>=4, count: 2
7>=8, count: 3설명없는 코드
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int c = sc.nextInt();
int[] arr = new int[n];
int answer = 0;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
int left = 1;
int right = arr[n - 1] - arr[0];
while (left <= right) {
int mid = (left + right) / 2;
if (horse(arr, mid) >= c) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
System.out.println(answer);
}
private static int horse(int[] arr, int mid) {
int recent = arr[0];
int count = 1;
for (int point : arr) {
if (recent + mid <= point) {
recent = point;
count++;
}
}
return count;
}
}설명있는 코드
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int c = sc.nextInt();
int[] arr = new int[n];
int answer = 0;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
int left = 1;
int right = arr[n - 1] - arr[0];
while (left <= right) {
int mid = (left + right) / 2;
System.out.println("left: " + left + ", right: " + right + ", mid: " + mid);
if (horse(arr, mid) >= c) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
}
private static int horse(int[] arr, int mid) {
int recent = arr[0];
int count = 1;
for (int point : arr) {
if (recent + mid <= point) {
System.out.print(recent + mid + ">=" + point + ", count: ");
recent = point;
count++;
System.out.println(count);
}
}
return count;
}
}7. Recursive&Tree&Graph(DFS, BFS 기초)
1. 재귀함수: 스택프레임
재귀함수는 스택을 사용합니다.
public class Main {
public static void main(String[] args) {
recursive(3);
}
}재귀함수 전에 선언
static void recursive(int n) {
if (n != 0) {
System.out.print(n + " ");
recursive(n - 1);
}
}출력
3 2 1 재귀함수 후에 선언
static void recursive(int n) {
if (n != 0) {
recursive(n - 1);
System.out.print(n + " ");
}
}출력
1 2 3 2. 이진수 출력 (재귀)
이진수는 나머지를 역으로 출력하면 됩니다.
public class Main {
static void r(int n) {
if (n != 0) {
r(n / 2);
System.out.print(n % 2);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
r(sc.nextInt());
}
}3. 팩토리얼
public class Main {
static int r(int n) {
if (n == 1) {
return 1;
} else {
return r(n - 1) * n;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(r(sc.nextInt()));
}
}4. 피보나치 재귀 (메모이제이션)
대부분은 재귀함수보다 for 문과 배열로 짜는 것이 메모리 등이 더 가볍고 유리합니다.
기본코드
public class Main {
static int r(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return r(n - 1) + r(n - 2);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(r(n));
}
}입력
10출력
1 1 2 3 5 8 13 21 34 55 배열저장 코드
public class Main {
static int[] arr;
static int r(int n) {
if (n == 1 || n == 2) {
return arr[n - 1] = 1;
} else {
return arr[n - 1] = r(n - 1) + r(n - 2);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
arr = new int[n];
r(n);
for (int num : arr) {
System.out.print(num + " ");
}
}
}메모이제이션의 중요성
n = 45 일 때,
메모이제이션을 사용한 코드는 0.1초만에 출력되는 반면
사용하지 않은 코드는 4.45초가 걸렸다.
n = 46 일 때,
메모이제이션을 사용한 코드는 0.1초만에 출력되는 반면
사용하지 않은 코드는 6.89초가 걸렸다.
if (arr[n] > 0) {
return arr[n];단 두 줄의 코드를 추가함으로써 엄청난 시간을 아낄 수 있는 것이다.
코드
public class Main {
static int[] arr;
static int r(int n) {
if (arr[n] > 0) {
return arr[n];
} else if (n == 1 || n == 2) {
return arr[n] = 1;
} else {
return arr[n] = r(n - 1) + r(n - 2);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
arr = new int[n + 1];
r(n);
for (int num : arr) {
System.out.print(num + " ");
}
}
}5. 이진트리순회 (DFS: Depth-First Search)
전위순회
중위순회: 부모를 중간에 출력
후위순회: 부모를 마지막에 출력. 병합정렬과 같습니다.
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
}
}
public class Main {
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
dfs(root);
}
}출력
1 2 4 5 3 6 7 전위순회
static void dfs(Node node) {
if (node != null) {
System.out.print(node.data + " ");
dfs(node.left);
dfs(node.right);
}
}출력
4 2 5 1 6 3 7 중위순회
static void dfs(Node node) {
if (node != null) {
dfs(node.left);
System.out.print(node.data + " ");
dfs(node.right);
}
}출력
4 5 2 6 7 3 1 후위순회
static void dfs(Node node) {
if (node != null) {
dfs(node.left);
dfs(node.right);
System.out.print(node.data + " ");
}
}6. 부분집합 구하기 (DFS)
date: 07.13
출력
123
12
13
1
23
2
3코드
public class Main {
static int input = 3;
static int[] arr = new int[input + 1];
public static void main(String[] args) {
dfs(1);
}
static void dfs(int n) {
if (n != input + 1) {
arr[n] = 1;
dfs(n + 1);
arr[n] = 0;
dfs(n + 1);
} else {
for (int i = 1; i <= input; i++) {
if (arr[i] == 1) {
System.out.print(i);
}
}
System.out.println();
}
}
}7. 이진트리 레벨탐색 (BFS: Breadth-First Search)
너비우선탐색
Queue 에서 빼면서 자식들을 저장한다.
출력
0: 1
1: 2 3
2: 4 5 6 7 코드
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
}
}
public class Main {
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
bfs(root);
}
static void bfs(Node node) {
Queue<Node> q = new LinkedList<>();
q.add(node);
int level = 0;
while (!q.isEmpty()) {
int len = q.size();
System.out.print(level + ": ");
for (int i = 0; i < len; i++) {
Node current = q.poll();
System.out.print(current.data + " ");
if (current.left != null) {
q.add(current.left);
}
if (current.right != null) {
q.add(current.right);
}
}
level++;
System.out.println();
}
}
}8. 송아지찾기1 (BFS)
입력
5 14출력
5를 꺼냈습니다. []
6를 넣었습니다.
4를 넣었습니다.
10를 넣었습니다.
level: 1
6를 꺼냈습니다. [4, 10]
7를 넣었습니다.
11를 넣었습니다.
4를 꺼냈습니다. [10, 7, 11]
3를 넣었습니다.
9를 넣었습니다.
10를 꺼냈습니다. [7, 11, 3, 9]
15를 넣었습니다.
level: 2
7를 꺼냈습니다. [11, 3, 9, 15]
8를 넣었습니다.
12를 넣었습니다.
11를 꺼냈습니다. [3, 9, 15, 8, 12]
16를 넣었습니다.
3를 꺼냈습니다. [9, 15, 8, 12, 16]
2를 넣었습니다.
9를 꺼냈습니다. [15, 8, 12, 16, 2]
3설명있는 코드
public class Main {
static int answer = 0;
static int[] move = {1, -1, 5};
static int[] point = new int[10001];
static Queue<Integer> q = new LinkedList<>();
private static int next;
private static int level = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int su = sc.nextInt();
int cow = sc.nextInt();
int answer = bfs(su, cow);
System.out.println(answer);
}
static int bfs(int su, int cow) {
q.add(su);
point[su] = 1;
while (!q.isEmpty()) {
int len = q.size();
for (int i = 0; i < len; i++) {
int poll = q.poll();
System.out.println(poll + "를 꺼냈습니다. " + q);
for (int j = 0; j < move.length; j++) {
next = poll + move[j];
if (next == cow) {
return level + 1;
}
if (point[next] == 1) {
continue;
}
if (next >= 1 && next <= 10000) {
q.add(next);
point[next] = 1;
System.out.println(next + "를 넣었습니다.");
}
}
}
level++;
System.out.println("level: " + level);
}
return 0;
}
}9. Tree 말단노드까지의 가장 잛은 경로 (DFS)
10. 그래프와 인접행렬
- 무방향 그래프
- 방향 그래프
- 가중치방향 그래프
11. 경로탐색 (DFS)
방향그래프가 주어지면 1번 정점에서 point 정점으로 가는 모든 경로의 가지수를 출력하는 프로그램을 작성하세요.
아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지 입니다.
입력
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5출력
1에서 2로 이동
2에서 3로 이동
3에서 4로 이동
4에서 5로 이동
도착!
2에서 5로 이동
도착!
1에서 3로 이동
3에서 4로 이동
4에서 2로 이동
2에서 5로 이동
도착!
4에서 5로 이동
도착!
1에서 4로 이동
4에서 2로 이동
2에서 3로 이동
2에서 5로 이동
도착!
4에서 5로 이동
도착!
6설명없는 코드
static void solve(int start) {
check[start] = 1;
if (start == point) {
count++;
}
for (int end = 1; end <= point; end++) {
if (arr[start][end] == 1 && check[end] == 0) {
solve(end);
check[start] = 0;
}
}
}public class Main {
static int count = 0;
static int point;
static int arrow;
static int[][] arr;
static int[] check;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
point = sc.nextInt();
arrow = sc.nextInt();
arr = new int[point + 1][point + 1];
check = new int[point + 1];
for (int i = 0; i < arrow; i++) {
int n = sc.nextInt();
int m = sc.nextInt();
arr[n][m] = 1;
}
solve(1);
System.out.println(count);
}
}설명있는 코드
public class Main {
static int count = 0;
static int point;
static int arrow;
static int[][] arr;
static int[] check;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
point = sc.nextInt();
arrow = sc.nextInt();
arr = new int[point + 1][point + 1];
check = new int[point + 1];
for (int i = 0; i < arrow; i++) {
int n = sc.nextInt();
int m = sc.nextInt();
arr[n][m] = 1;
}
solve(1);
System.out.println(count);
}
static void solve(int start) {
check[start] = 1;
if (start == point) {
count++;
System.out.println("도착!");
}
for (int end = 1; end <= point; end++) {
if (arr[start][end] == 1 && check[end] == 0) {
System.out.println(start + "에서 " + end + "로 이동");
solve(end);
check[start] = 0;
}
}
}
}12. 경로탐색 (인접리스트)
DFS 는 $$n^2$$ 개의 배열을 만들어야 하므로 데이터를 많이 차지한다.
갈 수 있는 경로의 리스트만 만들어 데이터를 적게 차지하는 인접리스트를 배워보자.
public class Main {
static ArrayList<ArrayList<Integer>> graph;
static int count;
static int[] ch;
static int point;
public static void main(String[] args) {
int line, answer = 0;
graph = new ArrayList<ArrayList<Integer>>();
Scanner sc = new Scanner(System.in);
point = sc.nextInt();
line = sc.nextInt();
ch = new int[point + 1];
for (int i = 0; i <= point; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < line; i++) {
int start = sc.nextInt();
int end = sc.nextInt();
graph.get(start).add(end);
}
ch[1] = 1;
dfs(1);
System.out.println(count);
}
static void dfs(int start) {
if (start == point) {
count++;
}
for (int end : graph.get(start)) {
if (ch[end] == 0) {
ch[end] = 1;
dfs(end);
ch[end] = 0;
}
}
}
}리스트 확인코드
// 리스트 확인코드
for (int i = 1; i <= point; i++) {
System.out.print(i + ": ");
for (int n : graph.get(i)) {
System.out.print(n + " ");
}
System.out.println();
}13. 그래프 최단거리 (BFS)
레벨로 풀어도 되고 배열로 풀어도 된다.
입력
6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2
6 5출력
2: 3
3: 1
4: 1
5: 2
6: 28. 그리디 알고리즘
1. 씨름선수
키와 몸무게가 자신보다 모두 큰 사람이 있다면 탈락하고 아니라면 뽑힌다.
해설: 키 순으로 정렬한 다음 몸무게 max 변수를 만들어 인원을 확인한다.
객체의 속성으로 정렬
객체의 속성 (attribute) 로 정렬하기 위해서는
- Comparable 인터페이스를 구현한다.
- compareTo 메소드의 리턴으로 this.속성 - o.속성 을 입력한다. (오름차순)
- Collections.sort(리스트)
결과
height: 178
weight: 90
max: 90
-----
height: 176
weight: 82
max: 90
-----
height: 174
weight: 62
max: 90
-----
height: 170
weight: 91
max: 91
-----
height: 154
weight: 96
max: 96
-----
count: 3코드
ArrayList<Player> players = new ArrayList<>();
Player p = new Player(200, 100);
int count = 0;
int max = 0;
// 생성
for (int i = 0; i < 5; i++) {
players.add(new Player((int) (Math.random() * 50 + 150), (int) (Math.random() * 40 + 60)));
}
Collections.sort(players);
for (Player player : players) {
if (max < player.weight) {
max = player.weight;
count++;
}
System.out.printf("height: %d\nweight: %d\nmax: %d\n-----\n", player.height, player.weight, max);
}
System.out.printf("count: %d", count);
2. 회의실 배정
설명
한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다.
각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.
단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
입력
첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데
이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 회의시간은 0시부터 시작한다.
회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.
출력
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.
입력
5
1 4
2 3
3 5
4 6
5 7출력
2 3
1 4
3 5
4 6
5 7
3코드
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Conference> conferences = new ArrayList<>();
int count = 0;
int max = 0;
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int start = sc.nextInt();
int end = sc.nextInt();
conferences.add(new Conference(start, end));
}
Collections.sort(conferences);
for (Conference conference : conferences) {
System.out.printf("%d %d\n", conference.start, conference.end);
}
for (Conference conference : conferences) {
if (max <= conference.start) {
max = conference.end;
count++;
}
}
System.out.println(count);
}
}
class Conference implements Comparable<Conference> {
int start;
int end;
public Conference(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Conference o) {
if (this.end != o.end) return this.end - o.end;
return this.start - o.start;
}
}3. 결혼식
설명
현수는 다음 달에 결혼을 합니다.
현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.
피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다.
각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다.
현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요.
만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다.
입력
첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.
시간은 첫날 0시를 0으로 해서 마지막날 밤 12시를 72로 하는 타임라인으로 오는 시간과 가는 시간이 음이 아닌 정수로 표현됩니다.
출력
첫째 줄에 피로연장에 동시에 존재하는 최대 인원을 출력하세요.
입력
5
14 18
12 15
15 20
20 30
5 14출력
2코드
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Time> arr = new ArrayList<>();
int count = 0;
int max = 0;
int n = sc.nextInt();
for (int i = 0; i < n * 2; i++) {
int time = sc.nextInt();
arr.add(new Time(time, i % 2 == 0 ? 's' : 'e'));
}
Collections.sort(arr);
for (Time obj : arr) {
count += obj.status == 's' ? 1 : -1;
if (max < count) max = count;
}
System.out.println(max);
}
}
class Time implements Comparable<Time> {
int time;
char status;
public Time(int time, char status) {
this.time = time;
this.status = status;
}
@Override
public int compareTo(Time o) {
if (this.time != o.time) return this.time - o.time;
return this.status - o.status;
}
}4. 최대 수입 스케줄
작성날짜: 10/3
Priority Queue 응용문제
설명
현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.
각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.
단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.
입력
첫 번째 줄에 자연수 N(1<=N<=10,000)이 주어지고, 다음 N개의 줄에 M(1<=M<=10,000)과 D(1<=D<=10,000)가 차례로 주어진다.
출력
첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다.
입력
6
50 2
20 1
40 2
60 3
30 3
30 1출력
150코드
class Solution {
int solution(int n, int[][] arr) {
Arrays.sort(arr, (o1, o2) -> o2[1] - o1[1]);
int max = arr[0][1];
PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
int income = 0;
int idx = 0;
for (int i = max; i >= 1; i--) {
for (; idx < arr.length; idx++) {
if (arr[idx][1] == i) q.offer(arr[idx][0]);
else break;
}
if (!q.isEmpty()) income += q.poll();
}
return income;
}
}Queue 에서 poll() 은 꼭 isEmpty() 와 같이쓰도록 한다. 아니면 런타임에러가 난다.
입력코드
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] arr = new int[n][2];
for (int i = 0; i < n; i++)
for (int j = 0; j < 2; j++)
arr[i][j] = sc.nextInt();
Solution s = new Solution();
System.out.println(s.solution(n, arr));
}
}다익스트라 알고리즘
전제: 가중치 값이 음수가 되면 안된다.
PriorityQueue 는 log n 만큼의 시간복잡도가 든다.
728x90
반응형
LIST
