백준
9주차_백준 문제풀이
JANNNNNN
2023. 6. 24. 21:26
문제
1. 1021
2. 2798
3. 11725
1. 문제 1021
문제풀이
이 문제는 양방향으로 접근해야하기 때문에 Deque, 덱으로 구현해야한다.
+ offerLast, offerFirst, pollFirst, pollLast 만 정확하게 구현하면 됨
문제에서는 세 가지 연산이 주어졌다.
1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
즉, 전체 과정으로 보자면 두 가지 프로세스를 거친다.
1. 뽑고자 하는 원소가 덱의 중앙에서 끝쪽에 가까운 쪽 방향으로 이동(연산)하여 뽑고자 하는 원소가 첫 번째 위치에 갈 때까지 반복
2. 원소를 뽑음
이 두가지 프로세스를 구현해주면 된다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
LinkedList<Integer> deque = new LinkedList<Integer>();
int count = 0; // 2, 3번 연산 횟수 누적 합 변수
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken()); // 큐의 크기(1 ~ N)
int M = Integer.parseInt(st.nextToken()); // 뽑으려는 숫자의 개수
// 1부터 N까지 덱에 담아둔다.
for(int i = 1; i <= N; i++) {
deque.offer(i);
}
int[] seq = new int[M]; // 뽑고자 하는 수를 담은 배열
st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < M; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < M; i++) {
// 덱에서 뽑고자 하는 숫자의 위치(index) 찾기
int target_idx = deque.indexOf(seq[i]);
int half_idx;
/*
* 만약 현재 덱의 원소가 짝수 개라면 중간 지점을
* 현재 덱의 절반 크기에서 -1 감소시킨다.
*
* {1, 2, 3, 4} 일 때, 2를 중간지점으로 하면
* 인덱스는 1이기 때문
*/
if(deque.size() % 2 == 0) {
half_idx = deque.size() / 2 - 1;
}
else {
half_idx = deque.size() / 2;
}
// 중간 지점 또는 중간 지점보다 원소의 위치가 앞에 있을 경우
if(target_idx <= half_idx) {
// idx 보다 앞에 있는 원소들을 모두 뒤로 보낸다. (2번 연산)
for(int j = 0; j < target_idx; j++) {
int temp = deque.pollFirst();
deque.offerLast(temp);
count++;
}
}
else { // 중간 지점보다 원소의 위치가 뒤에 있는 경우
// idx를 포함한 뒤에 있는 원소들을 모두 앞으로 보낸다. (3번 연산)
for(int j = 0; j < deque.size() - target_idx; j++) {
int temp = deque.pollLast();
deque.offerFirst(temp);
count++;
}
}
deque.pollFirst(); // 연산이 끝나면 맨 앞 원소를 삭제
}
System.out.println(count);
}
}2. 문제 2798
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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(), " ");
int N = Integer.parseInt(st.nextToken());
int M = 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());
}
int result = search(arr, N, M);
System.out.println(result);
}
// 탐색
static int search(int[] arr, int N, int M) {
int result = 0;
// 3개를 고르기 때문에 첫번째 카드는 N - 2 까지만 순회
for (int i = 0; i < N - 2; i++) {
// 두 번째 카드는 첫 번째 카드 다음부터 N - 1 까지만 순회
for (int j = i + 1; j < N - 1; j++) {
// 세 번째 카드는 두 번째 카드 다음부터 N 까지 순회
for (int k = j + 1; k < N; k++) {
// 3개 카드의 합 변수 temp
int temp = arr[i] + arr[j] + arr[k];
// M과 세 카드의 합이 같다면 temp return 및 종료
if (M == temp) {
return temp;
}
// 세 카드의 합이 이전 합보다 크면서 M 보다 작을 경우 result 갱신
if(result < temp && temp < M) {
result = temp;
}
}
}
}
// 모든 순회를 마치면 result 리턴
return result;
}
}
전체 카드(N)에서 3개를 고를 수 있는 경우의 수 모두 탐색하여 각 경우 별 선택한 카드의 합을 모두 구한 뒤, 주어진 M 을 넘지 않는 최댓값을 찾으면 된다.
즉, 3중 for문을 사용하여 모든 경우의 수를 탐색하면 끝이다.
3. 문제 11725
문제풀이
2번 노드부터 차례대로 노드들의 부모를 출력하면된다.
BFS를 활용해 문제를 풀면 된다.
코드
import java.util.ArrayList;
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);
int n = sc.nextInt(); // 노드 개수 입력
// 트리 구조 표현을 위한 그래프 구현
ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
for (int i = 0; i < n; i++)
tree.add(new ArrayList<>());
// 그래프 입력
for (int i = 0; i < n - 1; i++) {
int n1 = sc.nextInt() - 1;
int n2 = sc.nextInt() - 1;
tree.get(n1).add(n2);
tree.get(n2).add(n1);
}
boolean[] visited = new boolean[n]; // 방문 여부 확인용 배열
int[] parentNode = new int[n]; // 부모 노드 저장 배열
// BFS
Queue<Integer> queue = new LinkedList<>();
queue.add(0);
visited[0] = true;
while (!queue.isEmpty()) {
int v = queue.remove();
for (int node : tree.get(v))
if (!visited[node]) {
visited[node] = true;
queue.add(node);
parentNode[node] = v; // 부모 노드 찾은 후 저장
}
}
// 루트 노드를 제외한 나머지 노드의 부모 노드 출력
for (int i = 1; i < n; i++)
System.out.println(parentNode[i] + 1);
}
}