2751번
반복문을 통해 num개의 입력값들을 list로 넣어준다
Collections.sort() 메서드를 사용하여 해당 list를 오름차순으로 정렬
처음엔 배열을 사용해서 Arrays.sort() 사용 했는데 시간 초과 떴다
import java.util.*;
public class Practice {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int num = sc.nextInt();
List <Integer> list = new ArrayList<>();
for(int i = 0; i<num; i++) {
list.add(sc.nextInt());
}
Collections.sort(list);
for(int i =0; i<num; i++) {
sb.append(list.get(i)).append("\n");
}
System.out.println(sb);
}
}
찾아보니 Arrays.sort() 의 경우 dual-pivot Quicksort 알고리즘을 사용하는데 이는 평균 시간복잡도가 O(nlogn) 이고 매우 빠른 알고리즘이지만 최악의 경우 시간복잡도는 O(n2) 이기 때문에 주의해야 한다고 한다.
StringBuilder를 사용하지 않고 for문과 System.out.println(list.get(i)); 를 통해 실행할 경우 시간이 오래 걸려 StringBuilder를 사용하여 시간을 줄인다. 입력의 경우는 Scanner 보다는 BufferedReader 사용하는 것이 빠르다고 한다
2231번
문제를 이해하는 것이 까다로웠다
생성자는 1개 이상이므로 최솟값을 찾기 위해 for 문을 돌려 작은 수부터 찾아본다. 생성자는 num보다 클 수 없으므로 0 부터 num 전까지 만족하는 값을 찾기 전까지는 for 문을 계속 돌려서 탐색
만약 num과 [각 자리수의 합+i] 이 동일하다는 것은 생성자의 값이 찾았다는 뜻이므로 break;로 반복문을 종료한다
result의 초기값을 0으로 설정해두었으므로 만약 for문을 다 돌렸는데도 생성자가 존재하지 않는다면 0을 출력
import java.util.*;
public class Practice {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int result = 0;
for(int i = 0; i<num; i++) {
int number = i;
int sum = 0;
while(number>0) {
sum += number%10;
number/=10;
}
if(num == sum+i) {
result = i;
break;
}
}
System.out.println(result);
}
}
1110번 > 어려워....
중복되지 않는 정수를 담을 Set 타입의 참조 변수를 선언한다.
입력한 숫자 num이 다시 set에 들어올 때까지 과정을 반복한 뒤 set 에 num이 들어오면 반복문 종료
주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수는 String으로 변환한 뒤 substring() 을 사용하여 마지막 문자열을 뽑아내서 문자열 결합을 한다. 마지막 문자열만 뽑아내려면 시작점은 length()-1 로 잡으면 된다
합친 문자열을 다시 숫자로 변환한 뒤 이 숫자를 num 으로 재정의한다
해당 반복문이 돌아가는 횟수를 출력해야 하기 때문에 반복문이 돌아갈 때마다 count 가 하나씩 증가하도록 한다
import java.util.*;
public class Practice {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
Set <Integer> set = new HashSet<>();
int count = 0;
while(set.add(num)) {
int sum = 0;
String last1 = String.valueOf(num);
// if(num<10) {
// last1 = "0"+last1;
// }
String last2 = last1.substring(last1.length()-1);
while(num > 0) {
sum += num%10;
num/=10;
}
String str1 = String.valueOf(sum);
String str2 = str1.substring(str1.length()-1);
String str3= last2+str2;
num = Integer.valueOf(str3);
count++;
}
System.out.println(count);
}
}
1181번
다중 조건 정렬을 사용한다 (익명 클래스를 통해 Comparator 구현, 정렬할 배열의 타입은 String)
중복을 허용하지 않으므로 hashset 사용하여 입력을 받는다
<객체를 정렬하는데 필요한 메서드를 정의한 인터페이스>
Comparable: 기본 정렬 기준을 구현하는데 사용, 자기 자신과 매개변수 1개를 비교
Comparator: 기본 정렬 외에 다른 기준으로 정렬하고자 할 때 사용
compare(): Comparator 인터페이스를 구현할 때 작성해야 하는 메서드, 실제 구현할 때 compare()에 두 객체를 넘겨 내부의 구현에 따라 int 값을 반환한다. compare 메소드 리턴 타입이 int 형인 이유는 기본적으로 compare 메소드는 3가지 리턴 값에 의해 위치를 바꿀지 결정하기 때문이다. 3가지 반환값에 의해 두 객체(인자)의 우선순위를 판단하며 양수를 리턴할 경우 정렬 알고리즘에 의해 위치를 바꾼다
compareTo(): 두개의 값을 비교하여 int 값으로 반환, 주어진 객체와 자기 자신을 비교
import java.util.*;
public class Practice {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
Set<String> set = new HashSet<>(); // 중복되는 값 삭제
for (int i = 0; i < num; i++) {
set.add(sc.next()); // sc.nextLine() 썼을 때 실패, sc.next()로 바꾸니까 성공
}
int size = set.size();
String[] arr = new String[size];
set.toArray(arr);
Arrays.sort(arr, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
if (s1.length() == s2.length()) {
return s1.compareTo(s2);
} else {
return s1.length() - s2.length(); // 길이 오름차순 정렬
}
}
});
for(int i = 0; i< arr.length; i++) {
System.out.println(arr[i]);
}
}
}
next()는 엔터를 무시하고 입력을 받으며 nextLine은 한줄 단위로 입력을 받기 때문에 엔터도 포함된다
nextInt() 가 버퍼의 내용을 가져올 때 분리자를 제외하고 가져오기 때문에 num만 가져오게 된다. 그러면 버퍼에 \n이 남아있게 되는데 nextLine()은 공백과 엔터인 분리자를 포함시키기 때문에 \n만 가져오고 프로그램이 종료되는 것이다
1436번
666을 포함하는 숫자 중에 작은 숫자가 차례대로 나와야 한다
666 부터 시작하여 1씩 증가시켜 해당 값이 666 을 포함하고 있다면 count값을 증가
count 값이 num과 같아질 경우 반복문 종료
import java.util.*;
public class Practice {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int count = 1;
int n = 666;
while(count<num) {
n++;
if(String.valueOf(n).contains("666")) {
count++;
}
}
System.out.println(n);
}
}브루트포스를 사용한 문제 풀이라고 한다. 부루트포스는 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져온다는 것을 의미한다.
10814번
앞서 풀어본 Comparator 구현하는 문제와 비슷한 유형이다
나이를 오름차순으로 정렬하는 문제
StringBuilder 사용하기
import java.util.*;
public class Practice {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
StringBuilder sb = new StringBuilder();
List <Member> list = new ArrayList<>();
for(int i = 0; i<num; i++) {
list.add(new Member(sc.nextInt(),sc.next()));
}
Collections.sort(list, new Comparator<Member>() {
@Override
public int compare(Member m1, Member m2) {
return m1.getAge()-m2.getAge();
}
});
for(Member member : list) {
sb.append(member).append("\n");
}
System.out.println(sb);
}
}
class Member {
private int age;
private String name;
Member (int age, String name) {
this.age = age;
this.name = name;
}
public int getAge() {
return age;
}
@Override
public String toString() {
return age +" "+name;
}
}
맞았는데 메모리 너무 큰 거 같다....ㅎ 그래서 StringBuilder와 BufferedReader 사용했다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Practice {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
List <Member> list = new ArrayList<>();
for(int i = 0; i<num; i++) {
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int age = Integer.parseInt(st.nextToken());
String name = st.nextToken();
list.add(new Member(age,name));
}
Collections.sort(list, new Comparator<Member>() {
@Override
public int compare(Member m1, Member m2) {
return m1.getAge()-m2.getAge();
}
});
for(Member member : list) {
sb.append(member).append("\n");
}
System.out.println(sb);
}
}
class Member {
private int age;
private String name;
Member (int age, String name) {
this.age = age;
this.name = name;
}
public int getAge() {
return age;
}
@Override
public String toString() {
return age +" "+name;
}
}'백준 문제 풀이' 카테고리의 다른 글
| 10818번(스택), 18866번(큐), 1654번(이진 탐색) (0) | 2022.07.18 |
|---|---|
| 1966번(큐), 1010번(조합), 1789번 (0) | 2022.07.15 |
| 10815번 (이진 탐색), 1874번 (스택), 11650번 (정렬) (0) | 2022.07.13 |
| 14954번, 15649번, 15650번, 15651번, 15625번 (0) | 2022.07.11 |
| 4344번, 11729번, 10870번, 2447번, 10872번, 16395번 (0) | 2022.07.10 |