728x90
반응형
2024.08.14기준 - 실버4
백준, BEAKJOON, BOJ, JAVA, 자바
풀이
이 문제는 n이 주어질 때, 1 ~ n을 이용해서 부분 수열들의 합이 가장 높은 수열을 출력하는 문제입니다.
예제를 통해 문제를 이해하도록 하겠습니다.
1. n이 4가 주어지면 인덱스별로 호출되는 횟수를 정의해봤습니다.
가운데 있는 수들이 가장 많은 횟수를 나오는걸 확인할 수 있습니다.
(큰 수가 많이 호출될 수록 합이 높게 나옵니다.)
2. 이를 이용해 높은 수 일수록 가운데에 배치하며 작은 수 일수록 가장자리에 위치하도록 Deque를 이용했습니다.
앞 뒤를 한 번 씩 넣어 수열을 완성해주었습니다.
// 수열을 저장할 큐
Deque<Integer> qu = new LinkedList<>();
boolean check = false; // 앞 뒤를 구분해줄 변수
for (int i = n; i >= 1; i--) {
if (!check) { // 뒤로 넣기
qu.addLast(i);
} else { // 앞으로 넣기
qu.addFirst(i);
}
check = !check;
}
3. 완성된 수열을 출력합니다.
// 수열을 출력
while (!qu.isEmpty()) {
sb.append(qu.poll()).append(" ");
}
코드
package Main;
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine()); // 순열의 길이
// 수열을 저장할 큐
Deque<Integer> qu = new LinkedList<>();
boolean check = false; // 앞 뒤를 구분해줄 변수
for (int i = n; i >= 1; i--) {
if (!check) { // 뒤로 넣기
qu.addLast(i);
} else { // 앞으로 넣기
qu.addFirst(i);
}
check = !check;
}
// 수열을 출력
while (!qu.isEmpty()) {
sb.append(qu.poll()).append(" ");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
728x90
반응형
'코딩테스트 일기 (BAEKJOON)' 카테고리의 다른 글
BEAKJOON / 백준 - JAVA 9291번 스도쿠 채점 (0) | 2024.08.16 |
---|---|
BEAKJOON / 백준 - JAVA 7662번 이중 우선순위 큐 (0) | 2024.08.15 |
BEAKJOON / 백준 - JAVA 9613번 GCD 합 (0) | 2024.08.13 |
BEAKJOON / 백준 - JAVA 18511번 큰 수 구성하기 (0) | 2024.08.12 |
BEAKJOON / 백준 - JAVA 7569번 토마토 (0) | 2024.08.11 |