백준
백준 닷컴 단계 별로 풀어보기 20단계
CD가참둥그렇다
2023. 10. 23. 17:55
1단계 약수
- 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.
- 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.
- 첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.
import java.io.*;
import java.util.*;
public class Step_1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int temp = Integer.parseInt(st.nextToken());
int min = temp;
int max = temp;
for (int i = 0; i < n - 1; i++) {
temp = Integer.parseInt(st.nextToken());
if (temp > max) {
max = temp;
}
if (temp < min) {
min = temp;
}
}
bw.write(min * max + "\\n");
bw.flush();
bw.close();
}
}
A.
- 약수 중 가장 큰 값과 작은 값을 곱하면 n이 나오는 것을 이용한다.
2단계 인사성 밝은 곰곰이
- ENTER는 새로운 사람이 채팅방에 입장했음을 나타낸다. 그 외는 채팅을 입력한 유저의 닉네임을 나타낸다. 닉네임은 숫자 또는 영문 대소문자로 구성되어 있다.
- 새로운 사람이 입장한 이후 처음 채팅을 입력하는 사람은 반드시 곰곰티콘으로 인사를 한다. 그 외의 기록은 곰곰티콘을 쓰지 않은 평범한 채팅 기록이다.
- 채팅 기록 중 곰곰티콘이 사용된 횟수를 출력하시오.
import java.io.*;
import java.util.*;
public class Step_1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int count = 0;
HashMap<String, Boolean> user = new HashMap<>();
for (int i = 0; i < n; i++) {
String chat = br.readLine();
if (chat.equals("ENTER")) {
count += user.size();
user.clear();
} else {
user.put(chat, true);
}
if (i == n - 1) {
count += user.size();
}
}
bw.write(count + "\\n");
bw.flush();
bw.close();
}
}
A.
- hashmap은 입력 값이 중복된 경우 value만 바뀌는 점을 이용할 수 있다.
- enter 이후 hashmap에 값을 입력하고 다음 엔터가 나오면 hashmap의 크기를 출력하고 비우도록 반복문을 만든다.
- 반복문의 마지막 반복에서는 남아있는 hashmap의 크기를 더해주고 출력한다.
3단계 붙임성 좋은 총총이
- 사람들이 만난 기록이 시간 순서대로 N개 주어진다. (총총이는 토끼이지만 이 문제에서는 편의상 사람이라고 가정한다.)
- 무지개 댄스를 추지 않고 있던 사람이 무지개 댄스를 추고 있던 사람을 만나게 된다면, 만난 시점 이후로 무지개 댄스를 추게 된다.
- 기록이 시작되기 이전 무지개 댄스를 추고 있는 사람은 총총이 뿐이라고 할 때, 마지막 기록 이후 무지개 댄스를 추는 사람이 몇 명인지 구해보자!
import java.io.*;
import java.util.*;
public class Step_3 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
HashMap<String, Boolean> man = new HashMap<>();
man.put("ChongChong", true);
for(int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
String man1 = st.nextToken();
String man2 = st.nextToken();
if(man.containsKey(man1)) {
man.put(man2, true);
} else if(man.containsKey(man2)) {
man.put(man1, true);
}
}
bw.write(man.size()+"\\n");
bw.flush();
bw.close();
}
}
A.
- hashmap은 입력 값이 중복된 경우 value만 바뀌는 점을 이용할 수 있다.
- 해시맵에 총총이를 먼저 넣어준다.
- 반복문을 통해 둘 중의 한 값이 해시맵에 있는 값이면 나머지 값을 해시맵에 추가하는 반복문을 작성한다.
- 해시맵의 사이즈를 출력한다.
4단계 통계학
- 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.
- 첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.
- 둘째 줄에는 중앙값을 출력한다.
- 셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.
- 넷째 줄에는 범위를 출력한다.
import java.io.*;
import java.util.*;
public class Step_5 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int sum = 0;
int[] arr = new int[n];
int[][] arrCount = new int[8001][2];
for (int i = 0; i < n; i++) {
int temp = Integer.parseInt(br.readLine());
sum += temp;
arr[i] = temp;
arrCount[temp + 4000][0]++;
arrCount[temp + 4000][1] = temp;
}
Arrays.sort(arr);
Arrays.sort(arrCount, (o1, o2) -> {
if (o1[0] == o2[0]) {
return Integer.compare(o1[1], o2[1]);
} else {
return Integer.compare(o2[0], o1[0]);
}
});
double avg = (double) sum / n;
bw.write(Math.round(avg) + "\\n");
bw.write(arr[(n - 1) / 2] + "\\n");
if(arrCount[0][0]==arrCount[1][0]) {
bw.write(arrCount[1][1] + "\\n");
} else {
bw.write(arrCount[0][1] + "\\n");
}
bw.write(arr[n-1]-arr[0]+"\\n");
bw.flush();
bw.close();
}
}
A.
- 평균은 sum을 구하고 double연산으로 avg를 구한 다음 math의 round메소드를 사용해 소수 첫자리로 반올림한다.
- 중앙값은 배열을 만들고 정렬하여 가운데 값을 출력한다.
- 최빈값은 각 값의 개수를 배열로 저장하고 중복 개수가 많은 순서, 숫자가 작은 순서로 정렬하고, 최빈값이 하나면 첫 값을, 최빈값이 둘 이상이면 두 번째 값을 출력한다.
- 범위는 정렬한 배열의 맨 앞과 끝의 값의 차를 출력한다.
5단계 영단어 암기는 괴로워
import java.io.*;
import java.util.*;
import java.util.Map.Entry;
public class Step_5 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
String temp = br.readLine();
if (temp.length() >= m) {
map.put(temp, map.getOrDefault(temp, 0) + 1);
}
}
List<String> list = new ArrayList<>(map.keySet());
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (Integer.compare(map.get(o1), map.get(o2)) != 0) {
return Integer.compare(map.get(o2), map.get(o1));
}
if (o1.length() != o2.length()) {
return Integer.compare(o2.length(), o1.length());
}
return o1.compareTo(o2);
}
});
StringBuilder sb = new StringBuilder();
for (String str : list) {
sb.append(str+"\\n");
}
bw.write(sb+"");
bw.flush();
bw.close();
}
}
A.
- 최대한 연산 시간을 줄이는 것이 중요하다.
- 해시맵을 이용하여 사전에 들어갈 단어를 넣는다. 해시맵은 중복이 되지 않는 특징을 이용한다.
- 해시맵의 value는 hashmap.getofdefault를 이용하면 null의 경우 대신 입력할 값을 지정할 수 있다.
- 해시맵의 keyset을 list에 넣고, collections.sort를 이용하여 정렬한다.
- 정렬 방법은 익명메소드를 이용하여 작성한다.
- 문자열을 여러 줄 입력할 경우 시간을 줄이기 위해 StringBuilder를 이용한다.
- StringBuilder에 각 list의 값과 개행문자열을 넣어준다.
- sb를 출력한다.