본문 바로가기

분류 전체보기

 (56)
[Baekjoon] 백준 5635번: 생일 (JAVA) 문제 5635번 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net [ 문제 풀이 ] ArrayList 안에 넣어야 할 요소를 Student 클래스로 정의하고, Comparable을 implement 시켜 ArrayList 안에 요소를 넣을 때 정렬할 기준을 정의해줍니다. 나이가 적은 순으로 정렬하려면 연, 월, 일이 큰 순서대로(생일이 늦는 순서대로) 정렬 기준을 정의하면 됩니다. 입력받은 대로 ArrayList에 넣은 후, Collections.sort()을 사용하여 정의한 정렬 기준대로 정렬해줍니다. [ 코드 ] import java.io.*; import java.util.ArrayL..
[Baekjoon] 백준 10974번: 모든 순열 (JAVA) 문제 10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net [ 문제 풀이 ] N에 대한 모든 순열들을 출력해야 하는 문제로, DFS 탐색을 활용하여 모든 경우의 수를 탐색하면 됩니다. visit[]으로 이미 뽑은 숫자는 다시 뽑지 않도록 하고, for()을 사용하여 배열에 탐색한 숫자를 하나씩 넣어줍니다. dfs(1)부터 시작하여 1부터 탐색을 시작합니다. depth를 매개변수로 하여 현재 dfs()을 몇 번째 돌고 있는지 확인합니다. visit[]을 활용하여, 뽑은 숫자가 아니라면 res[]에 현재 위치의 숫자를 넣어주고, 방문 표시를 합니다. depth를 하나 늘려 dfs()을 다시 돌고, ..
[Baekjoon] 백준 1240번: 노드 사이의 거리 (JAVA) 문제 1240번 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net [ 문제 풀이 ] 무향 그래프로 각 노드를 연결하는 ArrayList[]에 저장하고, 두 정점 사이의 거리를 구하는 문제입니다. Node 클래스를 정의하여 각 정점 값들과 거리를 저장합니다. BFS 탐색을 활용하여 Queue에 다음 방문할 위치와 거리를 저장하고 탐색하며 거리를 계속 더해주면 됩니다. 무향 그래프이므로 visit[]을 사용하여 방문한 정점인지 체크해줍니다. [ 코드 ] import java.io.*; impor..
[Baekjoon] 백준 2910번: 빈도 정렬 (JAVA) 문제 2910번 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net [ 문제 풀이 ] 수열에서 등장하는 횟수가 많은 순으로 정렬을 해야 합니다. 횟수가 동일한 경우에는 수열에서 먼저 나온 숫자가 앞에 있어야 하므로 2가지의 정렬 조건을 만족해야 합니다. 숫자를 key로 하고, 해당 숫자가 나온 빈도를 value값으로 하는 HashMap을 만들고, 이 HashMap의 keySet에 위의 2가지 정렬 조건을 정의해주면 됩니다. keySet의 sort()를 사용하여 람다 함수로 구현하였습니다. 두 수의 등장하는 횟수가 동일한 경우에 어느 수가 앞에 위치하는지를..
[Baekjoon] 백준 1439번: 뒤집기 (JAVA) 문제 1439번 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net [ 문제 풀이 ] 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이므로 0끼리, 1끼리 묶었을 때 더 적은 묶음의 개수를 찾으면 됩니다. 여러가지 간단한 방법들도 많지만, dfs로 탐색과 StringTokenizer 방법 2가지로 각각 풀어보았습니다. [ 코드 ] 1) DFS 탐색 문자열을 순회하며 0을 만났을 때와 1을 만났을 때, 각각 res1, res2를 증가시키고 dfs()를 돌려 0의 묶음과 1의 묶음의 개수를 카운트해줍니다. 이 때, ..
[Baekjoon] 백준 2234번: 성곽 (JAVA) 문제 2234번 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net [ 문제 풀이 ] 1) 방의 개수 / 가장 넓은 방의 넓이 구하기 이 문제에서 벽에 대한 정보를 얻기 위해서는 비트 연산을 이용해야 합니다. 각 4방향(서, 북, 동, 남)이 2^0, 2^1, 2^2, 2^3으로 더해지기 때문에, &와 = N) continue; if (visit[nextR][nextC]) continue; visit[nextR][nextC] = true; queue.offer(new Node(nextR, nextC)); }..
[Baekjoon] 백준 1388번: 바닥장식 (JAVA) 문제 1388번 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net [ 문제 풀이 ] 같은 바닥 장식끼리 한 묶음으로 묶어서 몇 개의 묶음이 있는지 카운트를 해주면 되는 문제입니다. 이중 for()문을 순회하며 방문하지 않은 곳인 경우 카운트를 하나 증가시키고 BFS를 돌아 나무 판자의 무늬에 따라 같은 행 또는 열로 이동하며 같은 무늬인 곳들을 탐색해주면 됩니다. [ 코드 ] import java.io.*; import java.util.LinkedList; import java.util.Queue; import ja..
[Baekjoon] 백준 13417번: 카드 문자열 (JAVA) 문제 13417 13417번: 카드 문자열 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처 www.acmicpc.net [ 문제 풀이 ] 입력받은 순서대로 문자를 가져와서 적절하게 배치하여 사전 순으로 가장 빠른 문자열을 만들어야 합니다. 문제에서 나온 조건대로 도식화하면 아래와 같습니다. 문자열의 맨 앞의 문자와 맨 뒤의 문자를 각각 저장하기 위한 변수를 만들고, 맨 앞과 맨 뒤에 배치하기 위해 Deque을 사용하였습니다. [ 코드 ] import java.io.*; import java.util.*; public class Main { private static..

티스토리툴바