백준 문제풀이 (실버 3)
2023. 1. 29. 15:20ㆍ백준 문제풀이/실버3
1. 순열 사이클(10451)
👉 소스코드
public class Main {
static int tc, leng;
static StringBuilder sb = new StringBuilder();
static int[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
tc = Integer.parseInt(br.readLine());
for(int i = 0; i < tc; i++) {
int count = 0;
leng = Integer.parseInt(br.readLine());
arr = new int[leng + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 1; j < arr.length; j++) {
arr[j] = Integer.parseInt(st.nextToken());
}
boolean[] visited = new boolean[leng + 1];
for(int k = 1; k < arr.length; k++) {
if(!visited[k]) {
visited[k] = true;
int visit = arr[k];
while(true) {
if(visited[visit]) {
count++;
break;
}
visited[visit] = true;
visit = arr[visit];
}
}
}
System.out.println(count);
}
}
}- 인덱스에 있는 값을 인덱스로 따라가다보면 다시 원점으로 오게되는데 해당 식이 성립되면 순열 사이클이라고 부른다. 순열 사이클이 몇개 인지 구하는 문제인데 입력 값을 받아서 visited 배열을 선언하고 인덱스로 방문한 자리를 체크해두고 다시 처음 시작점으로 가려고할 때 break해주면서 counting을 함으로써 문제풀이를 진행했다.
2. 바이러스(2606)
👉 소스코드
public class Main {
static int node, edge, count;
static int[][] arr;
static boolean[] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
node = Integer.parseInt(br.readLine());
edge = Integer.parseInt(br.readLine());
arr = new int[node + 1][node + 1];
visited = new boolean[node + 1];
for(int i = 0; i < edge; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr[a][b] = arr[b][a] = 1;
}
bfs(1);
System.out.println(count );
}-bfs, dfs
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<Integer>();
visited[start] = true;
q.offer(start);
while(!q.isEmpty()) {
int find = q.poll();
for(int i = 1; i <= node; i++) {
if(arr[find][i] == 1 && !visited[i]) {
q.offer(i);
visited[i] = true;
count++;
}
}
}
}
public static void dfs(int start) {
visited[start] = true;
count++;
for(int i = 0; i <= node; i++) {
if(!visited[i] && arr[start][i] == 1) {
dfs(i);
}
}
}3. 피보나치 함수(1003)
👉 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static Integer[][] dp = new Integer[41][2];
public static void main(String[] args) throws IOException {
dp[0][0] = 1; dp[0][1] = 0; dp[1][0] = 0; dp[1][1] = 1;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
fibo(N);
sb.append(dp[N][0] + " " + dp[N][1] + '\n');
}
System.out.println(sb.toString());
}
public static Integer[] fibo(int num) {
if(dp[num][0] == null || dp[num][1] == null) {
dp[num][0] = fibo(num - 1)[0] + fibo(num - 2)[0];
dp[num][1] = fibo(num - 1)[1] + fibo(num - 2)[1];
}
return dp[num];
}
}- 대표적인 dp문제인 피보나치 수열문제로 호출했더 수에 대하여 배열에 저장하며 풀이를 진행해야 시간초과 해결이 가능했던 문제
4. 회전하는 큐(1021)
👉 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
LinkedList<Integer> dq = new LinkedList<Integer>();
ArrayList<Integer> list = new ArrayList<Integer>();
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());
for(int i = 1; i < N + 1; i++) {
dq.offer(i);
}
st = new StringTokenizer(br.readLine());
// 큐의 사이즈 만큼 큐 길이 세팅
for(int i = 0; i < M; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
int count = 0;
while(list.size() > 0) {
// 앞에 있는 수가 찾는 수라면
if(dq.peekFirst() == list.get(0)) {
dq.pollFirst();
list.remove(0);
}else{ // 아니라면 2, 3번 연산 수행
// checkCnt는 2번 연산을 할지 3번 연산을 할지 판단하기 위해서
// 즉, 내가 뽑으려는 수가 큐에서 중간보다 앞인지 뒤인지 판단
int checkCnt = dq.indexOf(list.get(0));
int indexFound;
// 인덱스는 0부터 시작하기 때문에 짝수이면 -1
if(dq.size() % 2== 0) indexFound = dq.size() / 2 - 1;
else indexFound = dq.size() / 2;
// 앞에서 뽑는 경우 (내가 찾는 수의 인덱스가 중간 수 보다 앞이라면)
if(checkCnt <= indexFound) {
for(int i = 0; i < checkCnt; i++) {
dq.offerLast(dq.pollFirst());
count++;
}
}else {
// 뒤에서 뽑는 경우 ( 내가 찾는 수의 인덱스가 중간 수 보다 뒤라면)
for(int i = 0; i < dq.size() - checkCnt; i++) {
dq.offerFirst(dq.pollLast());
count++;
}
}
}
}
System.out.println(count);
}
}- 간단하게 덱을 활용하여 풀이할 수 있는 문제 여기서 Deque를 사용하지 않은 이유는 LinkedList에 있는 indexOf 함수를 활용하여 2번 연산을 할지, 3번 연산을 할지 판변하기 위해서
5. 게임(1072)
👉 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long x = Long.parseLong(st.nextToken());
long y = Long.parseLong(st.nextToken());
long z = y * 100 / x;
if(z >= 99) System.out.println(-1);
else {
long start = 0;
long end = x;
while(start <= end) {
long mid = (start + end) / 2;
if(z < 100 * (y + mid) / (x + mid)) end = mid - 1;
else start = mid + 1;
}
System.out.println(start);
}
}
}- z가 99 이상이면 게임을 무한대 진행해도 탐색불가 98이하부터 이진탐색 진행
6. 팰린드롬 만들기
👉 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map.Entry;
public class Main1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String ans = "";
char[] c = br.readLine().toCharArray();
int[] arr = new int[26];
for(int i = 0; i < c.length; i++) {
arr[c[i] - 'A']++;
}
int count = 0;
for(int i = 0; i < arr.length; i++) {
if(arr[i] % 2 != 0) {
count++;
}
}
if(count > 1) {
System.out.println("I'm Sorry Hansoo");
} else {
for(int i = 0; i < arr.length; i++) {
for(int j = 0; j < arr[i] / 2; j++) {
sb.append((char) (i + 'A'));
}
}
ans += sb.toString();
String end = sb.reverse().toString();
sb = new StringBuilder();
for(int i = 0; i < arr.length; i++) {
if(arr[i] % 2 == 1) sb.append((char) (i + 'A'));
}
ans += sb.toString();
ans += end;
}
System.out.println(ans);
}
}- 홀수인 알파벳이 1개이거나 없어야지만 회문을 만들 수 있다. 따라서 먼저 홀수인 알파벳을 체크하여 해당 조건에 부합하지 않으면 "I'm Sorry Hansoo"를 출력하여주고 아니라면 알파벳의 개수 / 2만큼 문자열에 넣어주고 홀수인 알파벳읏 하나씩 넣어준뒤, 처음에 절반만큼 넣어두었던 문자열을 뒤집어서 마지막에 문자열을 합쳐주면 회문이 완성된다.
7. 미로 만들기
👉 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.StringTokenizer;
public class Main {
static int[] moveX = {0, 1, 0, -1, 0}, moveY = {0, 0, -1, 0, 1};
static int dir = 1;
public static void main(String[] args) throws IOException {
char[][] map = new char[100][100];
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int num = Integer.parseInt(br.readLine());
char[] move = br.readLine().toCharArray();
// 미로 초기화
// 맵의 모든곳을 #으로 만들어놓고 움직이며 다녀간 곳을 '.'으로 바꿀 예정
for(int i = 0; i < map.length; i++) {
Arrays.fill(map[i], '#');
}
// 임의의 시작점을 50,50로 지정 동서남북 어디로든 50만큼 움직여도 맵을 벗어날 수 없기 때문에
int curX = 50, curY = 50, leftTopX = 50, leftTopY = 50, rightBtmX = 50, rightBtmY = 50;
map[curX][curY] = '.';
for(int i = 0; i < move.length; i++) {
if(move[i] != 'F') {
next(move[i]);
} else {
curX += moveX[dir]; curY += moveY[dir];
map[curX][curY] = '.';
}
}
for(int i = 0; i < map.length; i++) {
for(int j = 0; j < map.length; j++) {
if(map[i][j] == '.') {
// map에서 다녀간 위치 중 i,j가 더 작다면 좌측 상단
// i,j가 더 크다면 우측 하단
if(leftTopX > i) leftTopX = i;
if(leftTopY > j) leftTopY = j;
if(rightBtmX < i) rightBtmX = i;
if(rightBtmY < j) rightBtmY = j;
}
}
}
for(int i = leftTopX; i <= rightBtmX; i++) {
for(int j = leftTopY; j <= rightBtmY; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
}
public static void next(char direction) {
if(direction == 'R') {
dir += 1;
if(dir == 5) dir = 1;
} else {
dir -= 1;
if(dir == 0) dir = 4;
}
}
}- 맵을 어떻게 그릴건지와 어떤 조건으로 미로를 다닐지만 생각한다면 간단하게 풀이가 가능한 문제
8. 시리얼 번호
👉 소스코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int num = Integer.parseInt(br.readLine());
String[] serial = new String[num];
for(int i = 0; i < num; i++) {
serial[i] = br.readLine();
}
Arrays.sort(serial, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
// 뒤에 있는 문자열이 더 길면 정렬 불필요
if(s1.length() < s2.length()) {
return -1;
} else if(s1.length() == s2.length()) {
if(sum(s1) == sum(s2)) {
return s1.compareTo(s2);
} else return Integer.compare(sum(s1), sum(s2));
} else return 1;
}
});
for(String s : serial) System.out.println(s);
}
public static int sum(String tmp) {
int sum = 0;
for(int i = 0; i < tmp.length(); i++) {
if(tmp.charAt(i) >= '0' && tmp.charAt(i) <= '9') sum += tmp.charAt(i) - '0';
}
return sum;
}
}- comparator를 이용한 정렬문제
9. 삼각형 만들기
👉 소스코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = 0;
int num = Integer.parseInt(br.readLine());
// 내림차순을 위해 Integer 배열 사용
Integer[] arr = new Integer[num];
while(num--> 0) arr[t++] = Integer.parseInt(br.readLine());
// 가장 큰 값이 나올 수 있는 조건을 그리디하게 찾기 위해 내림차순 정렬
Arrays.sort(arr, Collections.reverseOrder());
int result = 0;
for(int i = 0; i < arr.length - 2; i++) {
int sum = 0;
if(arr[i] < arr[i + 1] + arr[i + 2]) sum = arr[i] + arr[i + 1] + arr[i + 2];
result = Math.max(result, sum);
}
if(result == 0) System.out.println(-1);
else System.out.println(result);
}
}10. 수리공 항승
👉 소스코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int res = 0, tmp = 0;
for(int i = 0; i < arr.length; i++) {
if(arr[i] > tmp) {
res++;
tmp = arr[i];
tmp += L - 1;
}
}
System.out.println(res);
}
}11. 분수 합
👉 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.StringTokenizer;
public class Main {
static int A = 0, B = 0, ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int c = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
if(b == d) {
B = d;
A = a + c;
} else {
B = b * d;
A = (a * d) + (c * b);
}
int ans = op(A, B);
System.out.println(A/ans + " " + B/ans);
}
public static int op(int bigN, int smallN) {
if (bigN % smallN == 0) return smallN;
else return op(smallN, bigN % smallN);
}
}