코딩테스트/Java
백준 - 시간복잡도, 브루트포스, 정렬
soohykim
2025. 4. 10. 13:59
728x90
반응형
📍 11. 시간 복잡도
📕 알고리즘 수업 - 알고리즘의 수행 시간 1
BAEKJOON 알고리즘 수업 - 알고리즘의 수행 시간 1
문제
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) {
i = ⌊n / 2⌋;
return A[i]; # 코드1
}코드
import java.util.*;
public class baek11_1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 단일 연산의 경우 : O(1)의 시간 복잡도
System.out.println('1');
System.out.println('0');
in.close();
}
}📕 알고리즘 수업 - 알고리즘의 수행 시간 2
BAEKJOON 알고리즘 수업 - 알고리즘의 수행 시간 2
문제
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n
sum <- sum + A[i]; # 코드1
return sum;
}코드
import java.util.*;
public class baek11_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
// for문 있을 경우 : O(n)의 시간 복잡도
System.out.println(n);
System.out.println(1);
in.close();
}
}
📕 알고리즘 수업 - 알고리즘의 수행 시간 3
BAEKJOON 알고리즘 수업 - 알고리즘의 수행 시간 3
문제
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n
for j <- 1 to n
sum <- sum + A[i] × A[j]; # 코드1
return sum;
}코드
import java.util.*;
public class baek11_3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long n = in.nextLong();
// for문 2개 있을 경우 : O(n^2)의 시간 복잡도
System.out.println(n * n);
System.out.println(2);
in.close();
}
}📕 알고리즘 수업 - 알고리즘의 수행 시간 4
BAEKJOON 알고리즘 수업 - 알고리즘의 수행 시간 4
문제
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n - 1
for j <- i + 1 to n
sum <- sum + A[i] × A[j]; # 코드1
return sum;
}코드
import java.util.*;
public class baek11_4 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long n = in.nextLong();
// 1부터 n-1 까지, i+1qnxj n까지 반복
System.out.println(n * (n - 1) / 2);
System.out.println(2);
in.close();
}
}📕 알고리즘 수업 - 알고리즘의 수행 시간 5
BAEKJOON 알고리즘 수업 - 알고리즘의 수행 시간 5
문제
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n
for j <- 1 to n
for k <- 1 to n
sum <- sum + A[i] × A[j] × A[k]; # 코드1
return sum;
}코드
import java.util.*;
public class baek11_5 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long n = in.nextLong();
// for문 3개 있을 경우 : O(n^3)의 시간 복잡도
System.out.println(n * n * n);
System.out.println(3);
in.close();
}
}📕 알고리즘 수업 - 알고리즘의 수행 시간 6
BAEKJOON 알고리즘 수업 - 알고리즘의 수행 시간 6
문제
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n - 2
for j <- i + 1 to n - 1
for k <- j + 1 to n
sum <- sum + A[i] × A[j] × A[k]; # 코드1
return sum;
}
코드
import java.util.*;
public class baek11_6 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Long n = in.nextLong();
System.out.println(n * (n - 1) * (n - 2) / 6);
System.out.println(3);
in.close();
}
}📕 알고리즘 수업 - 점근적 표기 1
문제
알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.
O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}
이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.
함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.코드
import java.util.*;
public class baek11_7 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a1 = in.nextInt();
int a0 = in.nextInt();
int c = in.nextInt();
int n0 = in.nextInt();
if (a1 * n0 + a0 <= c * n0 && c >= a1)
System.out.println(1);
else
System.out.println(0);
in.close();
}
}📍 12. 브루트 포스
📕 블랙잭
문제
제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 새로운 블랙잭 규칙을 만들어 게임하려고 한다.
블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.
이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.코드
import java.util.*;
public class baek12_1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
int[] arr = new int[N];
int sum = 0;
int max = 0;
for (int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
for (int i = 0; i < N - 2; i++) {
for (int j = i + 1; j < N - 1; j++) {
for (int k = j + 1; k < N; k++) {
sum = arr[i] + arr[j] + arr[k];
if (sum <= M && max < sum)
max = sum;
}
}
}
System.out.println(max);
in.close();
}
}📕 분해합
문제
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.코드
import java.util.*;
public class baek12_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int result = 0;
for (int i = 0; i < N; i++) {
int number = i;
int sum = 0;
while (number != 0) {
sum += number % 10;
number /= 10;
}
if (sum + i == N) {
result = i;
break;
}
}
System.out.println(result);
in.close();
}
}📕 수학은 비대면강의입니다
문제
문자가 2개인 연립방정식을 해결하는 방법에 대해 강의하고, 다음과 같은 문제를 숙제로 냈다.
다음 연립방정식에서 x와 y의 값을 계산하시오.
빈 칸에 수들을 입력하는 식이다. 각 칸에는 -999 이상 999 이하의 정수만 입력할 수 있다. 
코드
import java.util.*;
public class baek12_3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
int d = in.nextInt();
int e = in.nextInt();
int f = in.nextInt();
int x = 0;
int y = 0;
for (int i = -999; i <= 999; i++) {
for (int j = -999; j <= 999; j++) {
if ((a * i + b * j == c) && (d * i + e * j == f)) {
x = i;
y = j;
break;
}
}
}
// < 런타임 에러(/by zero) >
// int y = ((c * d) - (f * a)) / ((b * d) - (e * a));
// int x = (c - (b * y)) / a;
System.out.println(x + " " + y);
in.close();
}
}📕 체스판 다시 칠하기
문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek12_4 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
in.nextLine();
boolean[][] board = new boolean[N][M];
for (int y = 0; y < N; y++) {
String str = in.nextLine();
for (int x = 0; x < M; x++) {
if (str.charAt(x) == 'W')
board[y][x] = true;
else
board[y][x] = false;
}
}
int count = 64;
for (int y = 0; y <= N - 8; y++) {
for (int x = 0; x <= M - 8; x++) {
count = Math.min(count, getCount(x, y, board));
}
}
System.out.println(count);
in.close();
}
public static boolean[][] initBoard(String c) {
boolean[][] board = new boolean[8][8];
boolean white = true;
if (c.equals("W")) {
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
board[i][j] = white;
white = !white;
}
white = !white;
}
return (board);
}
else {
for (int i = 0; i < 8; i++) {
white = !white;
for (int j = 0; j < 8; j++) {
board[i][j] = white;
white = !white;
}
}
return (board);
}
}
public static int getCount(int x, int y, boolean[][] board) {
int count_W = 0;
int count_B = 0;
boolean[][] board_W = initBoard("W");
boolean[][] board_B = initBoard("B");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (board_W[i][j] != board[y + i][x + j])
count_W++;
if (board_B[i][j] != board[y + i][x + j])
count_B++;
}
}
return Math.min(count_W, count_B);
}
}📕 영화감독 숌
문제
종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 이다. 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"와 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수) 와 같다.
숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.코드
import java.util.*;
public class baek12_5 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int count = 1;
int num = 666;
while (count != N) {
num++;
if (String.valueOf(num).contains("666")) {
count++;
}
}
System.out.println(num);
in.close();
}
}
📕 설탕 배달
문제
상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek12_6 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int result = -1;
in.close();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (3 * i + 5 * j == N) {
result = i + j;
System.out.println(result);
return ;
}
}
}
System.out.println(result);
}
}📍 13. 정렬
📕 수 정렬하기
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek13_1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr);
for (int i = 0; i < N; i++) {
System.out.println(arr[i]);
}
in.close();
}
}📕 대표값2
문제
어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30의 평균은 (10 + 40 + 30 + 60 + 30) / 5 = 170 / 5 = 34가 된다.
평균 이외의 또 다른 대표값으로 중앙값이라는 것이 있다. 중앙값은 주어진 수를 크기 순서대로 늘어 놓았을 때 가장 중앙에 놓인 값이다. 예를 들어 10, 40, 30, 60, 30의 경우, 크기 순서대로 늘어 놓으면
10 30 30 40 60
이 되고 따라서 중앙값은 30이 된다.
다섯 개의 자연수가 주어질 때 이들의 평균과 중앙값을 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek13_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] arr = new int[5];
int sum = 0;
for (int i = 0; i < 5; i++) {
arr[i] = in.nextInt();
sum += arr[i];
}
Arrays.sort(arr);
System.out.println((int)(sum / 5));
System.out.println(arr[2]);
in.close();
}
}📕 커트라인
문제
슬기로운 코딩생활에
$N$명의 학생들이 응시했다.
이들 중 점수가 가장 높은
$k$명은 상을 받을 것이다. 이 때, 상을 받는 커트라인이 몇 점인지 구하라.
커트라인이란 상을 받는 사람들 중 점수가 가장 가장 낮은 사람의 점수를 말한다.코드
import java.util.*;
public class baek13_3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int k = in.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
// 버블 정렬 (Arrays.sort(arr))
for (int i = 0; i < N; i++) {
for (int j = 0; j < N - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
System.out.println(arr[N - k]);
in.close();
}
}📕 수 정렬하기 2
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek13_4 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int N = in.nextInt();
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < N; i++) {
list.add(in.nextInt());
}
Collections.sort(list);
for (int value : list) {
sb.append(value).append('\n');
}
System.out.println(sb);
// < 시간 초과 > - dual_pivot_Quicksort 사용 (시간복잡도 : O(nlogn), 최악 : O(n2))
// Arrays.sort(arr);
// < 시간 초과 > - bubble sort (시간복잡도 : O(n2))
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N - 1; j++) {
// if (arr[j] > arr[j + 1]) {
// int tmp = arr[j];
// arr[j] = arr[j + 1];
// arr[j + 1] = tmp;
// }
// }
// }
in.close();
}
}📕 수 정렬하기 3
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.코드
import java.io.*;
import java.util.*;
public class baek13_5 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
for (int num : arr) {
sb.append(num).append('\n');
}
System.out.println(sb);
// < 메모리 초과 >
// StringBuilder sb = new StringBuilder();
// int N = in.nextInt();
// ArrayList<Integer> list = new ArrayList<> ();
// for(int i = 0; i < N; i++) {
// list.add(in.nextInt());
// }
// Collections.sort(list);
// for (int value : list) {
// sb.append(value).append('\n');
// }
// System.out.println(sb);
// <시간 초과 >
// Arrays.sort(arr);
// < 시간 초과 >
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N - 1; j++) {
// if (arr[j] > arr[j + 1]) {
// int tmp = arr[j];
// arr[j] = arr[j + 1];
// arr[j + 1] = tmp;
// }
// }
// }
}
}📕 소트인사이드
문제
배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.코드
import java.util.*;
public class baek13_6 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
char[] arr = in.next().toCharArray();
Arrays.sort(arr);
for(int i = arr.length - 1; i >= 0; i--) {
System.out.print(arr[i]);
}
// < 성공 >
// int N = in.nextInt();
// int[] arr = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
// int i = 0;
// int base = 10;
// while (N != 0) {
// arr[i++] = N % base;
// N /= base;
// }
// Arrays.sort(arr);
// for (int j = 9; j >= 0; j--) {
// if (arr[j] >= 0)
// System.out.print(arr[j]);
// }
in.close();
}
}📕 좌표 정렬하기
문제
2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek13_7 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[][] arr = new int[N][2];
for (int i = 0; i < N; i++) {
arr[i][0] = in.nextInt();
arr[i][1] = in.nextInt();
}
Arrays.sort(arr, (e1, e2) -> { // 람다식 사용
if (e1[0] == e2[0]) {
return e1[1] - e2[1];
} else {
return e1[0] - e2[0];
}
});
for (int i = 0; i < N; i++) {
System.out.println(arr[i][0] + " " + arr[i][1]);
}
in.close();
}
}📕 좌표 정렬하기 2
문제
2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek13_8 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[][] arr = new int[N][2];
for (int i = 0; i < N; i++) {
arr[i][0] = in.nextInt();
arr[i][1] = in.nextInt();
}
Arrays.sort(arr, (e1, e2) -> {
if (e1[1] == e2[1]) {
return (e1[0] - e2[0]);
} else {
return (e1[1] - e2[1]);
}
});
for (int i = 0; i < N; i++) {
System.out.println(arr[i][0] + " " + arr[i][1]);
}
in.close();
}
}📕 단어 정렬
문제
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
1) 길이가 짧은 것부터
2) 길이가 같으면 사전 순으로
단, 중복된 단어는 하나만 남기고 제거해야 한다.코드
import java.util.*;
public class baek13_9 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
String[] arr = new String[N];
// 입력받기
for (int i = 0; i < N; i++) {
arr[i] = in.next();
}
// 순서대로 정렬 (길이 -> 사전)
Arrays.sort(arr, new Comparator<String>() {
public int compare(String s1, String s2) {
if (s1.length() == s2.length()) {
return s1.compareTo(s2);
} else {
return s1.length() - s2.length();
}
}
});
// 중복 제거 및 출력
System.out.println(arr[0]);
for (int i = 1; i < N; i++) {
if (!arr[i].equals(arr[i - 1]))
System.out.println(arr[i]);
}
in.close();
}
}📕 나이순 정렬
문제
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek13_10 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
String[][] arr = new String[N][2];
for (int i = 0; i < N; i++) {
arr[i][0] = in.next();
arr[i][1] = in.next();
}
Arrays.sort(arr, new Comparator<String[]>() {
public int compare(String[] s1, String[] s2) {
return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
}
});
for (int i = 0; i < N; i++) {
System.out.println(arr[i][0] + " " + arr[i][1]);
}
in.close();
}
}📕 좌표 압축
문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.코드
import java.util.*;
public class baek13_11 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] arr = new int[N];
int[] sort = new int[N];
HashMap<Integer, Integer> RankMap = new HashMap<Integer, Integer>();
for (int i = 0; i < N; i++) {
sort[i] = arr[i] = in.nextInt();
}
Arrays.sort(sort);
int rank = 0;
for (int value : sort) {
if (!RankMap.containsKey(value)) {
RankMap.put(value, rank);
rank++;
}
}
StringBuilder sb = new StringBuilder();
for (int key : arr) {
int n = RankMap.get(key);
sb.append(n).append(' ');
}
System.out.println(sb);
// < 시간 초과 >
// int N = in.nextInt();
// int[] arr = new int[N];
// int[] sort = new int[N];
// int count = 0;
// for (int i = 0; i < N; i++) {
// arr[i] = in.nextInt();
// if (isChar(sort, arr[i], count) != 1) {
// sort[count++] = arr[i];
// }
// }
// int[] cut = new int[count];
// cut = Arrays.copyOfRange(sort, 0, count);
// Arrays.sort(cut);
// for (int i = 0; i < N; i++) {
// int n = arr[i];
// System.out.print(isChar(cut, n, count) + " ");
// }
in.close();
}
// public static int isChar(int[] sort, int n, int count) {
// for (int i = 0; i < count; i++) {
// if (sort[i] == n) {
// return (i);
// }
// }
// return (0);
// }
}📘 Map (맵)
- 선언 : HashMap<Element, Element> map = new HashMap<>();
- Element : 데이터 타입 지정
- 개념
- 특정 순서에 따라 key와 value 조합으로 형성된 자료구조
- key(중복x)로 value(중복O) 얻음
- Map 인터페이스로 자료형에는 HashMap, LinkedHashMap, TreeMap 존재
- put(key, value) : key-value 넣기
- get(key) : key에 해당하는 value 가져오기
- containsKey(key) : 키의 유무 확인
- remove(key) : 값 삭제 (삭제한 값 리턴)
- size() : 맵에 저장된 데이터 개수 확인
📘 Set (집합)
- 선언 : HashSet<Element> set = new HashSet<>();
- Element : 데이터 타입 지정
- 개념
- 집합과 관련된 것 처리하는 자료형 (인덱싱을 통해 값 얻음)
- 데이터 중복X, 순서X
- Set 인터페이스로 자료형에는 HashSet, TreeSet, LinkedHashSet 존재
- add() : 값 추가
- remove() : 값 제거
📘 HashTable (해시테이블)
- 선언 :
- Element : 데이터 타입 지정
- 개념
- key와 value를 1:1로 연관지어 저장하는 자료구조
- 내부적으로 배열 사용하여 데이터 저장
- 특정 값 탐색시 index(key)로 접근하여 시간복잡도 O(1)(빠른 검색속도)
📍 14. 집합과 맵
📕 숫자 카드
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.코드
import java.io.*;
import java.util.*;
public class baek14_1 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count_N = Integer.parseInt(br.readLine());
int[] N = new int[count_N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < count_N; i++) {
N[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(N);
int count_M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < count_M; i++) {
int search = Integer.parseInt(st.nextToken());
System.out.print(binary_search(N, count_N, search) + " ");
}
}
public static int binary_search(int[] N, int count, int search) {
int first = 0;
int last = count - 1;
int mid = 0;
while (first <= last) {
mid = (first + last) / 2;
if (N[mid] == search)
return (1);
if (N[mid] < search) {
first = mid + 1;
} else {
last = mid - 1;
}
}
return (0);
}
}
📕 문자열 집합
문제
총 N개의 문자열로 이루어진 집합 S가 주어진다.
입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.코드
import java.io.*;
import java.util.*;
public class baek14_2 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < N; i++) {
map.put(br.readLine(), 0);
}
int count = 0;
for (int i = 0; i < M; i++) {
if (map.containsKey((br.readLine())))
count++;
}
System.out.println(count);
}
}
📕 회사에 있는 사람
문제
각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.
상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.코드
import java.io.*;
import java.util.*;
public class baek14_3 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Map<String, String> map = new HashMap<>();
StringTokenizer st;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String key = st.nextToken();
String value = st.nextToken();
if (map.containsKey(key))
map.remove(key);
else
map.put(key, value);
}
ArrayList<String> list = new ArrayList<String>(map.keySet());
Collections.sort(list, Collections.reverseOrder());
for (var value : list)
System.out.println(value + " ");
}
}
📕 나는야 포켓몬 마스터 이다솜
문제
포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 코드
import java.util.*;
import java.io.*;
public class baek14_4 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
Map<String, Integer> smap = new HashMap<>();
Map<Integer, String> imap = new HashMap<>();
for (int i = 1; i <= N; i++) {
String name = br.readLine();
smap.put(name, i);
imap.put(i, name);
}
for (int i = 1; i <= M; i++) {
String str = br.readLine();
if (isNum(str)) {
System.out.println(imap.get(Integer.parseInt(str)));
} else {
System.out.println(smap.get(str));
}
}
}
public static boolean isNum(String str) {
for (int i = 0; i < str.length(); i++) {
if (!Character.isDigit(str.charAt(i)))
return false;
}
return true;
}
}
📕 숫자 카드 2
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.코드
import java.util.*;
import java.io.*;
public class baek14_5 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
HashMap<Integer, Integer> map = new HashMap<>();
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
int m = Integer.parseInt(st.nextToken());
if (map.get(m) == null)
map.put(m, 1);
else
map.put(m, map.get(m) + 1);
}
int N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
int n = Integer.parseInt(st.nextToken());
if (map.get(n) == null)
sb.append(0).append(" ");
else
sb.append(map.get(n)).append(" ");
}
System.out.println(sb);
}
}
📕 듣보잡
문제
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
듣보잡의 수와 그 명단을 사전순으로 출력한다.코드
import java.util.*;
import java.io.*;
public class baek14_6 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
HashMap<String, Integer> map = new HashMap<>();
List<String> list = new ArrayList<>(); // 사전순 정렬 목적
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
map.put(br.readLine(), 1);
}
for (int i = 0; i < M; i++) {
String input = br.readLine();
map.put(input, map.getOrDefault(input, 0) + 1);
if (map.get(input) == 2)
list.add(input);
}
Collections.sort(list);
sb.append(list.size()).append("\n");
for (String s : list)
sb.append(s).append("\n");
System.out.println(sb);
}
}📕 대칭 차집합
문제
자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.
예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때, A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.코드
import java.util.*;
import java.io.*;
public class baek14_7 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
Set<Integer> set_A = new HashSet<>();
Set<Integer> set_B = new HashSet<>();
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < A; i++) {
int n = Integer.parseInt(st.nextToken());
set_A.add(n);
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < B; i++) {
int n = Integer.parseInt(st.nextToken());
set_B.add(n);
}
int result = 0;
for (int num : set_A) {
if (!set_B.contains(num))
result++;
}
for (int num : set_B) {
if (!set_A.contains(num))
result++;
}
System.out.println(result);
}
}
📕 서로 다른 부분 문자열의 개수
문제
문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.
부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.
예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.코드
import java.util.*;
import java.io.*;
public class baek14_8 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Set<String> set = new HashSet<String>();
String s = br.readLine();
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
set.add(s.substring(i, j));
}
}
System.out.println(set.size());
}
}
📍 15. 약수, 배수와 소수2
📕 최소공배수
문제
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.
두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek15_1 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
for (int i = 0; i < N; i++) {
int a = in.nextInt();
int b = in.nextInt();
int r = gcd(a, b);
System.out.println(a * b / r);
}
// < 시간 초과 >
// for (int i = 0; i < N; i++) {
// int A = in.nextInt();
// int B = in.nextInt();
// for (int j = 2; j <= A * B; j++) {
// if ((j % A == 0) && (j % B == 0)) {
// System.out.println(j);
// break;
// }
// }
// }
in.close();
}
public static int gcd (int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return (a);
}
}
📕 최소공배수
문제
정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다.
예:
10은 5의 배수이다 (5*2 = 10)
10은 10의 배수이다(10*1 = 10)
6은 1의 배수이다(1*6 = 6)
20은 1, 2, 4,5,10,20의 배수이다.
다른 예:
2와 5의 최소공배수는 10이고, 그 이유는 2와 5보다 작은 공배수가 없기 때문이다.
10과 20의 최소공배수는 20이다.
5와 3의 최소공배수는 15이다.
당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.코드
import java.util.*;
public class baek15_2 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
long a = in.nextLong();
long b = in.nextLong();
long r = gcd(a, b);
System.out.println(a * b / r);
in.close();
}
public static long gcd(long a, long b) {
while (b != 0) {
long r = a % b;
a = b;
b = r;
}
return (a);
}
}
📕 분수 합
문제
분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.
두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.코드
import java.util.*;
public class baek15_3 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int a1 = in.nextInt();
int a2 = in.nextInt();
int b1 = in.nextInt();
int b2 = in.nextInt();
int gcf = gcd(a2, b2); // 최대공약수
int lcm = a2 * b2 / gcf; // 최소공배수
int a = (lcm / a2) * a1 + (lcm / b2) * b1;
int b = lcm;
while (gcd(a, b) != 1) {
gcf = gcd(a, b);
b /= gcf;
a /= gcf;
}
System.out.println(a + " " + b);
in.close();
}
public static int gcd (int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return (a);
}
}📕 가로수
문제
직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.
편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.
예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.
심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.코드
import java.util.*;
public class baek15_4 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N ; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr);
int gcf = 0;
for (int i = 0; i < N - 1; i++) {
int distance = arr[i + 1] - arr[i];
gcf = gcd(distance, gcf);
}
System.out.println(((arr[N - 1] - arr[0]) / gcf) + 1 - N);
in.close();
}
public static int gcd (int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return (a);
}
}📕 다음 소수
문제
정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.코드
import java.math.BigInteger;
import java.util.*;
public class baek15_5 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
for (int i = 0; i < N; i++) {
long n = in.nextLong();
// isProbalbePrime()과 nextProbalbePrime()은 BigInteger만 지원
BigInteger b = new BigInteger(String.valueOf(n));
if (b.isProbablePrime(10)) {
System.out.println(n);
} else {
System.out.println(b.nextProbablePrime());
}
}
// < 시간 초과 >
// for (int i = 0; i < N; i++) {
// long n = in.nextLong();
// if (isPrime(n) == 0) {
// System.out.println(n);
// } else {
// System.out.println(getPrime(n));
// }
// }
in.close();
}
// public static long isPrime(long n) {
// long sqrt = (long)Math.sqrt(n);
// for (int i = 2; i <= sqrt; i++) {
// if (n % i == 0)
// return (1);
// }
// return (0);
// }
// public static long getPrime(long n) {
// while (isPrime(n) != 0) {
// n++;
// }
// return(n);
// }
}📕 소수 구하기
문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.코드
import java.math.BigInteger;
import java.util.*;
public class baek15_6 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
for (int i = a; i <= b; i++) {
BigInteger big = new BigInteger(String.valueOf(i));
if (big.isProbablePrime(10)) { // 인자값 : 확실성 정도
System.out.println(big);
}
}
in.close();
}
}📕 베르트랑 공준
문제
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 코드
import java.util.*;
public class baek15_7 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int N = 123456;
boolean[] arr = new boolean[2 * N + 1];
for (int i = 2; i <= 2 * N; i++) {
arr[i] = true;
}
for(int i = 2; i <= Math.sqrt(2 * N); i++) {
for (int j = i + i; j <= 2 * N; j += i) {
arr[j] = false;
}
}
while (true) {
int n = in.nextInt();
if (n == 0)
break;
int count = 0;
for (int i = n + 1; i <= 2 * n; i++) {
if (arr[i]) {
count++;
}
}
System.out.println(count);
}
// < 시간 초과 >
// while (true) {
// int n = in.nextInt();
// if (n == 0)
// break;
// int count = 0;
// for (int i = n + 1; i <= 2 * n; i++) {
// BigInteger b = new BigInteger(String.valueOf(i));
// if (b.isProbablePrime(10)) {
// count++;
// }
// }
// System.out.println(count);
// }
in.close();
}
}📕 골드바흐 파티션
문제
골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.코드
import java.util.*;
public class baek15_8 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
boolean[] arr = new boolean[1000000 + 1];
arr[0] = arr[1] = true;
for (int i = 2; i * i <= 1000000; i++) {
if (!arr[i]) {
for (int j = i + i; j <= 1000000; j += i) {
arr[j] = true;
}
}
}
int T = in.nextInt();
for (int i = 0; i < T; i++) {
int n = in.nextInt();
int count = 0;
for (int j = 2; j <= n / 2; j++) {
if (!arr[j] && !arr[n - j]) {
count++;
}
}
System.out.println(count);
}
in.close();
}
}📕 창문 닫기
문제
서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.
예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,
1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)
결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.코드
import java.util.*;
public class baek15_9 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int n =in.nextInt();
int count = 0;
// 약수가 홀수 인 것 찾기
// 제곱수만 약수가 홀수
for (int i = 1; i * i <= n; i++) {
count++;
}
System.out.println(count);
// < 메모리 초과 >
// long N = in.nextLong();
// boolean[] arr = new boolean[N + 1];
// for (int i = 1; i <= N; i++) {
// for (int j = i; j <= N; j += i) {
// if (arr[j])
// arr[j] = false;
// else
// arr[j] = true;
// }
// }
// int count = 0;
// for (int i = 1; i <= N; i++) {
// if (arr[i])
// count++;
// }
// System.out.println(count);
in.close();
}
}📖출처📖
728x90
반응형