코딩테스트/[백준] 코딩테스트 연습

숫자고르기 - 2668번

내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int N; static boolean[] visited; static int[] arr; static HashSet set = new HashSet(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); arr = new int[N + 1]; for (int i = 1; i

문자열 잘라내기 - 2866번

풀이 방법 이분 탐색을 이용해서 풀이했다. mid값은 지운 열의 갯수라서 중복일 경우 right를 mid-1로 해줘서 더 위를 확인해주고 중복이 아니라면 지워질 수 있기 때문에 count값을 mid로 주고 left를 mid+1로 해줘서 더 지울 수 있는지 확인해주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int R, C; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokeni..

줄어들지 않아 - 2688번

풀이 방법 dp를 이용해서 모든 자리 수의 개수를 구해주었다. 자릿수는 마지막 자릿수가 0,1,2....9 일 경우 따로 갯수를 구하고 더해서 총합을 구하는 방식을 사용했다. 마지막 자리가 0으로 나오는 경우는 0~9까지 모두 나오고 1로 나오는 경우는 1~9, 2로 나오는 경우는 3~9까지 나온다. 예를 들면 4자리수 중 마지막 자릿수가 0으로 나오는 수는 3자리 수의 모든 경우에서 나오고 1로 나오는 수는 3자리 수에서 마지막 자릿수가 1~9인 경우만 나오게 된다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int T; public static void main(String[] ar..

팀 배정 - 18768번

풀이 방법 그리디로 풀어야 하는 문제이지만 무조건 능력이 큰 것부터 넣게 되면 안된다. 반례 1 2 3 4 5 6 6 6 6 6 각 참가자는 공, 수 능력 중 더 큰것을 선택해야 하는데 그러기 위해서는 공, 수 능력의 차이가 가장 큰 것부터 넣어줘야 한다. 우선순위 큐를 이용해서 차이가 더 큰것을 우선순위로 주고 차이가 같다면 값이 더 큰 참가자를 우선으로 해주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int N, M, T; public static void main(String[] args) throws IOException { BufferedReader br = new Buf..

거짓말 - 1043번

풀이 방법 사람 수가 50까지로 비교적 적기 때문에 플로이드 워셜을 이용해서 사람끼리 연결되어 있는지 확인해주었다. 그 후 파티에 있는 사람마다 진실을 아는 사람과 연결되어 있는지 체크해서 count 해주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int N, M, K; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(b..

십자가 2개 놓기 - 17085번

풀이 방법 격자판의 크기가 크지 않아서 완전탐색을 이용했다. max값을 만들 수 있는 모든 십자가의 넓이를 비교해서 max 값을 처음 정해서 넓이가 1인 경우는 제외했다. list에 만들 수 있는 십자가가 차이자는 위치를 넣어주고 십자가가 겹치지 않는 경우에 넓이 곱의 최댓값을 구해주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int N, M; static String[][] arr; static ArrayList list = new ArrayList(); public static void main(String[] args) throws IOException { BufferedRe..

Coins - 3067번

내 코드 package com.company; import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int T, N, M; static int[] arr; static int[] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; T = Integer.parseInt(br.readLine()); for (int i = 0; i < T;..

뱀 - 3190번

풀이 방법 문제에 나온대로 구현을 통해 풀이했다. board 판을 (N + 2) * (N + 2) 크기로 만들어서 벽을 생성해 주었고 way 배열에는 오른쪽, 아래, 왼쪽, 위 방향 순서대로 경로를 넣어주었고 map에 방향 전환 정보를 넣고 Queue로 뱀이 현재 위치한 정보를 담아주었다. tail 함수는 뱀 머리가 뱀 몸통에 닿는지 확인하는 함수이다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int N, K, L; static int[][] board; static int[][] way = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; static HashMap m..

A -> B - 16953번

내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int A, B; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); A = Integer.parseInt(st.nextToken()); B = Integer.parseInt(st.nextToken()); PriorityQueue pq = new Priorit..

특정한 최단 경로 - 1504번

풀이 방법 bfs를 이용해서 최단 경로를 구하는 메소드를 만들어서 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 두 가지 경로로 나눠서 계산해주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int N, E, v1, v2; static ArrayList list = new ArrayList(); static boolean[] visited; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syste..