SkyLife는 예매의 편리함과 커뮤니티를 제공하여 정보를 공유할 수 있게 만들어진 항공 예매 플랫폼 서비스입니다.
여행을 즐기는 사람들이 증가하게 되면서 자연스레 항공을 이용하는 빈도 또한 높아지고 있다. 그러나 항공 이용객의 증가 추세에 비하여 항공권 예매 플랫폼 서비스에는 미흡한 부분이 있다. 원하는 시간과 가격 등을 반영한 항공권 티켓을 예매하기위해 항공권을 검색하면 검색 결과에는 원치않는 정보가 많아 가독성이 떨어진다. 이에 항공권 검색 과정의 가독성을 높여 예매의 편리함을 제공하고, 주변 여행지 추천 및 커뮤니티를 제공하여 여행 준비의 편리함과 여행 지역의 정보를 공유할 수 있는 항공 예매 플랫폼 서비스를 만들고자 한다.
처음 이 문제를 봤을 때 이분 탐색 문제라는 것을 떠올리지 못했다. 최솟값을 구하기 위해 min에다 long의 최댓값을 선언하고 start를 0 end를 입력 숫자 n으로 잡고 mid를 (start + end) / 2로 정해준다. value라는 변수를 하나 더 만들어 Math.pow(mid, 2) pow 메소드는 제곱근을 구할 수 있는 메소드이다. 제곱근이 0보다 커야 되니 if(value > 0)에서 if(value >= n) 일 때 최솟값 min = Math(min, mid)로 최솟값으로 바꿔준다. if(value >= n) 일 때 end 값을 mid - 1 value가 n 보다 작으면 start 값을 mid + 1로 바꿔준다. while문 밖에서 min의 값을 출력해준다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2417 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(br.readLine());
long start = 0;
long end = n;
long min = Long.MAX_VALUE;
while(start <= end) {
long mid = (start + end) / 2;
long value = (long)Math.pow(mid, 2);
if(value >= 0) {
if(value >= n) {
min = Math.min(min, mid);
end = mid - 1;
}
else {
start = mid + 1;
}
}
}
System.out.println(min);
}
}
백준 10815번 숫자 카드
내가 떠올린 풀이 해설
어제 풀었던 29번 수 찾기 문제와 비슷한 접근을 하면 풀리는 문제입니다. 기본 이분 탐색 문제입니다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek10815 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int m = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < m; i++) {
int look = Integer.parseInt(st.nextToken());
int start = 0;
int end = arr.length - 1;
boolean result = false;
while(start <= end) {
int mid = (start + end) / 2;
int midV = arr[mid];
if(midV < look) {
start = mid + 1;
}
else if(midV > look){
end = mid - 1;
}
else {
result = true;
break;
}
}
if(result) {
System.out.print(1 + " ");
}
else {
System.out.print(0 + " ");
}
}
}
}
백준 2805번 나무 자르기
내가 떠올린 풀이 해설
이 문제는 이분 탐색 문제인데 언제 이분 탐색을 사용하는지 못 떠올리다가 문제를 풀면서 떠올리게 되었습니다. arr배열에 넣으면서 end값을 최댓값으로 구한다. while(start < end) sum 변수를 만들고 mid 값을 (start + end) / 2 넣어준다. for문을 배열만큼 탐색하면서 arr [i] - mid값이 0보다 클 때 sum에 계속 더해준다. for문 밖에서 만약 sum이 m 보다 작으면 end에 mid를 넣어주고 작지 않으면 start에 mid + 1을 넣어주고 while문 밖에서 start - 1을 출력해준다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2805 {
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];
int start = 0;
int end = 0;
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
if(end < arr[i]) {
end = arr[i];
}
}
while(start < end) {
long sum = 0;
int mid = (start + end) / 2;
for(int i = 0; i < n; i++) {
if(arr[i] - mid > 0) {
sum += arr[i] - mid;
}
}
if(sum < m) {
end = mid;
}
else{
start = mid + 1;
}
}
System.out.println(start - 1);
}
}
오늘의 회고
오늘은 이분 탐색 기본 문제를 풀었습니다. 이분 탐색을 공부하면서 젤 어려운 점이 이분 탐색을 언제 적용해야 되는지 떠올리는데 어려움이 있었습니다. 아직까지 많이 부족하다고 생각하고 알고리즘을 풀면서 계속 복습하고 새로운 문제를 풀겠습니다. 하루하루 열심히 꾸준히 노력하겠습니다.
N의 최대 범위가 100,000이므로 단순 반복문으로는 풀 수가 없다. 이진 탐색을 적용하면 logn의 시간 복잡도를 사용하므로 이진 탐색을 이용해서 풀어야 된다. 이진 탐색은 정렬이 된 상태여야 하므로 정렬을 하고 start = 0 end = arr.length - 1로 기준을 잡는다. midV에 중앙값을 넣는다. 만약 midV가 크면 end의 값을 mid - 1로 바꿔준다. 작으면 start값을 mid + 1의 값으로 바꿔준다. 같으면 find를 true로 넣어준 후 break로 빠져나온다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1920 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int []arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int m = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < m; i++) {
int target = Integer.parseInt(st.nextToken());
boolean result = false;
int start = 0;
int end = arr.length - 1;
while(start <= end) {
int mid = (start + end) / 2;
int midV = arr[mid];
if(midV > target) {
end = mid - 1;
}
else if(midV < target) {
start = mid + 1;
}
else {
result = true;
break;
}
}
if(result) {
System.out.println(1);
}
else {
System.out.println(0);
}
}
}
}
30번 문제 기타 레슨
내가 떠올린 풀이 해설
문제를 이해하는데 시간이 걸렸다. 블루레이 크기가 모두 같고 녹화 순서가 바뀌지 않아야 함이라는 조건에서 이진 탐색을 사용해야된다는 단서이다. 첫 레슨부터 마지막까지 차례대로 저장하다 보면 지정한 크기로 모든 레슨을 저장할 수 있는지 판단할 수 있기 때문이다.
모두 저장할 수 있으면 크기를 줄이고 저장할 수 없다면 크키를 늘려주는 방식으로 크기의 최솟값을 알 수 있다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2343 {
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];
int start = 0;
int end = 0;
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
if(start < arr[i]) {
start = arr[i]; // 레슨 최댓값을 시작 인덱스로 저장하기
}
end = end + arr[i]; // 모든 래슨의 총합을 종료 인덱스로 저장하기
}
while(start <= end) {
int mid = (start + end) / 2;
int sum = 0;
int count = 0;
for(int i = 0; i < n; i++) { // mid 값으로 모든 레슨을 저장할 수 있는지 확인
if(sum + arr[i] > mid) {
count++;
sum = 0;
}
sum = sum + arr[i];
}
if(sum != 0) { // 탐색후 sum이 0이 아니면 블루레이가 1개 더 필요하므로 더함
count++;
}
if(count > m) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
System.out.println(start);
}
}
31번 문제 K번째 수
책 풀이 해설
k의 범위가 1 ~ min(10^9, N^2)이므로 시간 복잡도가 N^2인 알고리즘은 사용할 수 없다. 이진 탐색으로 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄이는 방법으로 B [k] 값을 구한다. 작은 수의 개수가 k - 1 개인 중앙값이 정답이다.
정확한 풀이
import java.util.*;
public class Baek1300 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
long start = 1;
long end = m;
long answer = 0;
while(start <= end) {
long mid = (start + end) / 2;
long cnt = 0;
for(int i = 1; i <= n; i++) {
cnt += Math.min(mid / i, n);
}
if(cnt < m) {
start = mid + 1;
}
else {
answer = mid;
end = mid - 1;
}
}
System.out.println(answer);
}
}
문제점
이진탐색을 떠올리기 힘들었고중앙값보다 작은 수의 개수를 세면서 줄이는 방법을 이용해서작은 수의 개수가 k -1 개인 중앙값이 정답이라는 아이디어를 못 떠올렸다.
백준 11866번 요세푸스 문제 0
내가 떠올린 풀이 해설
기본 큐를 이용해서 푸는 문제이다. 큐가 비어 있을 때까지 반복한다. 큐를 pop 하고 다시 그 수를 push 해서 k번째 pop을 할 때 String str에 더해준다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek11866 {
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());
Queue<Integer> que = new LinkedList<>();
for(int i = 1; i <= n; i++) {
que.offer(i);
}
int cnt = 0;
String str = "<";
while(!que.isEmpty()) {
cnt++;
if(cnt == m) {
str += que.poll() + ", ";
cnt = 0;
}
else {
que.offer(que.poll());
}
}
str = str.substring(0, str.length() - 2);
System.out.print(str + ">");
}
}
오늘의 회고
오늘은 이진탐색 문제를 풀었습니다. 이진 탐색을 사용하는 문제에서 이진 탐색을 사용해야 되는 아이디어를 떠올리기 힘들었습니다. 마지막 문제는 어려워서 풀지 못했습니다. 이진 탐색에 대해 공부하기 위해 내일은 이진 탐색 중에 난의도가 높지 않은 문제를 풀겠습니다.
문제 조건에서 작은 번호의 노드부터 탐색한다고 했으므로 인접 노드를 오름차순으로 정렬한 후 구현한다. 또한 DFS가 끝났을 떼 방문 배열을 초기화해준다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1260 {
static ArrayList<Integer> arr[];
static boolean visited[];
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 v = Integer.parseInt(st.nextToken());
arr = new ArrayList[n + 1];
for(int i = 1; i <= n; i++) {
arr[i] = new ArrayList<>();
}
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int e = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
arr[e].add(s);
arr[s].add(e);
}
for(int i = 1; i <= n; i++) {
Collections.sort(arr[i]);
}
visited = new boolean[n + 1];
DFS(v);
System.out.println();
visited = new boolean[n + 1];
BFS(v);
}
private static void BFS(int i) {
Queue<Integer> que = new LinkedList<>();
que.add(i);
visited[i] = true;
while(!que.isEmpty()) {
int now = que.poll();
System.out.print(now + " ");
for(int b : arr[now]) {
if(!visited[b]) {
visited[b] = true;
que.add(b);
}
}
}
}
private static void DFS(int i) {
System.out.print(i + " ");
visited[i] = true;
for(int b : arr[i]) {
if(!visited[b]) {
DFS(b);
}
}
}
}
27번 미로 탐색
내가 떠올린 풀이 해설
N, M의 최대 크기가 100으로 매우 작기 때문에 DFS나 BFS의 시간제한은 생각하지 않아도 되는 문제다.
지나야 하는 칸수의 최솟값을 구하는 문제이므로 BFS로 풀었다. 상하좌우를 탐색하면서 칸의 숫자가 1이면서 아직 방문하지 않았다면 큐에 삽입한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2178 {
static int arr[][];
static boolean visited[][];
static int []dx = {1, 0, -1, 0};
static int []dy = {0, 1, 0, -1};
static int n,m;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
visited = new boolean[n][m];
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String line = st.nextToken();
for(int j = 0; j < m; j++) {
arr[i][j] = Integer.parseInt(line.substring(j, j + 1));
}
}
BFS(0,0);
System.out.println(arr[n - 1][m - 1]);
}
private static void BFS(int i, int j) {
Queue<int[]> que = new LinkedList<>();
que.offer(new int[]{i, j});
visited[i][j] = true;
while(!que.isEmpty()) {
int now[] = que.poll();
for(int k = 0; k < 4; k++) {
int x = now[0] + dx[k];
int y = now[1] + dy[k];
if(x >= 0 && x < n && y >= 0 && y < m) {
if(arr[x][y] != 0 && !visited[x][y]) {
visited[x][y] = true;
arr[x][y] = arr[now[0]][now[1]] + 1;
que.add(new int[] {x,y});
}
}
}
}
}
}
문제점
자연스럽게 Integer.parseInt(st.nextToken())으로 코드를 작성했는데 오류가 발생했다. 왜 오류가 났는지 찾다가 입력 예제가 띄어쓰기로 되어있는 게 아니라 한 줄로 붙어었다는것을 발견했다... que.add 할 때 {x, y}를 add 해야 되는데 {i, j}를 add를 해서 계속 답이 안 나왔다. 이번 문제 오류를 찾느라 한참 걸렸다.
28번 문제 트리의 지름
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1167 {
static boolean visited[];
static int[] distance;
static ArrayList<Edge> []arr;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
arr = new ArrayList[n + 1];
for(int i = 1; i <= n; i++) {
arr[i] = new ArrayList<Edge>();
}
for(int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
while(true) {
int e = Integer.parseInt(st.nextToken());
if(e == -1) {
break;
}
int v = Integer.parseInt(st.nextToken());
arr[s].add(new Edge(e, v));
}
}
distance = new int[n + 1];
visited = new boolean[n + 1];
BFS(1);
int max = 1;
for(int i = 2; i <= n; i++) {
if(distance[max] < distance[i]) {
max = i;
}
}
distance = new int[n + 1];
visited = new boolean[n + 1];
BFS(max);
Arrays.sort(distance);
System.out.println(distance[n]);
}
private static void BFS(int index) {
Queue<Integer> que = new LinkedList<>();
que.add(index);
visited[index] = true;
while(!que.isEmpty()) {
int now = que.poll();
for(Edge i : arr[now]) {
int e = i.e;
int v = i.value;
if(!visited[e]) {
visited[e] = true;
que.add(e);
distance[e] = distance[now] + v;
}
}
}
}
}
class Edge {
int e;
int value;
public Edge(int e, int value) {
this.e = e;
this.value = value;
}
}
문제점
문제를 고민해봤지만 풀지 못했다. 아직 골드까지 풀기는 부족한 실력인 것 같다.
오늘의 회고
오늘은 책에 있는 문제를 풀었습니다. 책이 실전 대비 책이라 그런지 어려운 문제들이 포함되어있습니다.ㅠㅠ 안 풀린다고 좌절하지 말고 천천히 기본부터 익혀 나가겠습니다. 내일은 그동안 학습했던 문제들 복습하고 정리하는 시간과 시간이 되면 오늘 보단 쉬운 문제를 풀겠습니다.
어제 풀었던 연결 요소의 개수 문제를 응용해서 풀면 된다. 어제 문제는 DFS 총 수행 횟수를 구하는 문제였지만 오늘 하나의 기준점에서 DFS가 몇 번 수행되는지 count를 구하는 문제이다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2606 {
static ArrayList<Integer> arr[];
static boolean visited[];
static int cnt, v;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
arr = new ArrayList[n + 1];
visited = new boolean[n + 1];
for(int i = 1; i <=n; i++) { // 인덱스 편의상 n+1설정, 0번째 요소는 사용 X
arr[i] = new ArrayList<>();
}
v = 1; // 탐색 시장할 정점의 번호
for(int i = 0; i < m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
arr[e].add(v);
arr[v].add(e);
}
System.out.println(DFS(v));
}
private static int DFS(int i) {
visited[i] = true;
for(int b : arr[i]) {
if(visited[b] == false) {
cnt++;
DFS(b);
}
}
return cnt;
}
}
오늘의 회고
오늘은 늦잠을 자고 게으름이 발동해서 점심 먹고 스터디 카페에 도착해서 DFS 한문제 밖에 풀지 못했습니다. 정신 차리고 내일 DFS문제를 더 풀겠습니다.
import java.io.*;
import java.util.*;
public class Baek1377 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int[n +1];
for(int i = 1; i <= n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
boolean change = false;
for(int i = 1; i <= n + 1; i++) {
change = false;
for(int j = 1; j <= n - i; j++) {
if(arr[j] > arr[j + 1]) {
change = true;
int swap = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = swap;
}
}
if(change == false) {
System.out.println(i);
break;
}
}
}
}
내가 떠올린 풀이 해설
C++ 예시로 보여준 코드를 그대로 적용해서 풀었습니다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1377 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Sort [] arr = new Sort[n];
for(int i = 0; i < n; i++) {
arr[i] = new Sort(Integer.parseInt(br.readLine()), i);
}
Arrays.sort(arr);
int max = 0;
for(int i = 0; i < n; i++) {
if(max < arr[i].index - i) {
max = arr[i].index - i;
}
}
System.out.println(max + 1);
}
}
class Sort implements Comparable<Sort> {
int value;
int index;
public Sort(int value, int index) {
this.value = value;
this.index = index;
}
@Override
public int compareTo(Sort o) {
return this.value - o.value;
}
}
문제점
이 문제는 N의 최대 범위가 500,000이므로 버블 정렬로 문제를 풀면 시간 초과가 나온다. 각 데이터마다 정렬 전 index값에서 정렬 후 index값을 빼고 최댓값을 찾는다. 그리고 swap이 일어나지 않은 반복문이 한번 더 실행되는 것을 감안해 max에 + 1을 해준다.
17번 문제 소트 인사이드
내가 떠올린 풀이 해설
N의 크기가 1,000,000,000 보다 작거나 같은 자연수이다. 자연수를 받아 자릿수 별로 정렬하는 문제이므로 숫자를 String으로 받은 후 정렬을 List에 Arrays.stream(arr).boxed().collect(Collectors.toList()); 로 담아 Collections.sort(integer, Comparator.reverseOrder()); 를 이용해 내림차순 정렬을 진행했다.
정확한 풀이
import java.util.*;
import java.util.stream.Collectors;
public class Baek1427 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int []arr = new int[str.length()];
for(int i = 0; i < str.length(); i++) {
arr[i] = str.charAt(i) - 48;
}
List<Integer> integer = Arrays.stream(arr).boxed().collect(Collectors.toList());
Collections.sort(integer, Comparator.reverseOrder());
for(int i = 0; i < str.length(); i++) {
System.out.print(integer.get(i));
}
}
}
18번 문제 ATM
내가 떠올린 풀이 해설
N의 최댓값이 1,000이고 시간제한이 1초이므로 시간 복잡도가 O(n^2) 이하인 정렬 알고리즘 아무거나 사용해도 된다.
Arrays.sort로 정렬을 하고 인출 시간을 sum에 더하고 total 걸린 시간을 구하기 위해 sum을 다시 total에 더했다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek11399 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int []arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int sum = 0;
int total = 0;
for(int i = 0; i < n; i++) {
sum += arr[i];
total += sum;
}
System.out.println(total);
}
}
19번 문제 K번째 수
내가 떠올린 풀이 해설
N의 최대 범위가 5,000,000이므로 O(nlogn)의 시간 복잡도로 정렬을 해야 된다. 간단하게 Arrays.sort로 풀었다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek11004 {
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());
}
Arrays.sort(arr);
System.out.println(arr[m - 1]);
}
}
20번 문제 수 정렬하기 2
내가 떠올린 풀이 해설
N의 최대 범위가 1,000,000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행해야 된다. Collections.sort을 이용해서 해결했다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2751 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuffer bf = new StringBuffer();
int n = Integer.parseInt(br.readLine());
int [] arr = new int[n];
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < n; i++) {
list.add(Integer.parseInt(br.readLine()));
}
Collections.sort(list);
for(int i = 0; i < n; i++) {
bf.append(list.get(i) + "\\n");
}
System.out.println(bf.toString());
}
}
문제점
Arrays.sort 로 쓰면 시간 초과가 난다.Arrays.sort() 의 경우dual-pivot Quicksort알고리즘을 사용한다. 물론 평균 시간 복잡도가O(nlogn) 이고 매우 빠른 알고리즘이다. 그러나 최악의 경우 시간 복잡도는O(n2) 이다. Collections.sort() 은 Timsort이다. Timsort 의 경우 합병 및 삽입 정렬 알고리즘을 사용한다. 두 가지가 섞여있는 정렬 알고리즘을hybrid sorting algorithm이라고 하는데, 합병 정렬은 최선, 최악 모두O(nlogn)을 보장하고 삽입 정렬은 최선의 경우는O(n), 최악의 경우는O(n2)이다. 그리고 두 정렬 모두 안정 정렬이기 때문에 Timsort를hybrid stable sorting algorithm이라고도 한다. 즉, 합병 정렬의 최악의 경우와 삽입 정렬의 최선의 경우를 짬뽕한 알고리즘이 Timsort라는 것이다.
오늘은 Do it 알고리즘 책에 있는 문제를 풀었습니다. 정렬에 관한 기본적인 문제 5문제를 풀었고 그동안 문제를 풀면서 Arrays.sort, Collections.sort를 많이 사용하였는데 시간 복잡도와 어떤 정렬을 사용하는지 모르고 사용하였습니다. sort에 대해 오늘 정렬 문제를 풀면서 학습하게 되었습니다. 정렬에 관한 알고리즘을 공부하고 시간 복잡도를 고려에 적절한 알고리즘을 사용해야 될 것 같습니다.
기준점 (0, 0)에서 끝점 (w, h)까지의 직사각형이 생기는데 기준점과 끝면으로 생긴 직사각형 면에 가장 가까운 거리를 구하는 문제이다. 저는 x의 좌표에서 기준점을 빼고 w좌표에서 x를 빼주고 Math.min을 이용해서 최솟값을 저장하고 y도 같은 방법으로 최솟값을 저장하고 두개의 최솟값을 다시 Math.min으로 최솟값을 구해서 출력해준다.
정확한 풀이
import java.util.*;
import java.io.*;
public class Baek1085 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
int endX = w - x;
int endY = h - y;
int m = Math.min(x, y);
int n = Math.min(endX, endY);
int answer = Math.min(m, n);
System.out.println(answer);
}
}
백준 1181번 단어 정렬
내가 생각한 풀이
String 배열로 문자열을 받아서 Comparator를 이용해서 단어 길이가 같을 경우 return o1.compareTo(o2);를 해주고 길이가 다르면 길이 순으로 정렬을 한다. 같은 단어가 있을 때 for문으로 탐색 후 그 전의 단어와 같을 경우 하나만 출력을 해줘서 중복을 방지한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1181 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String []str = new String[n];
for(int i = 0; i < n; i++) {
str[i] = br.readLine();
}
Arrays.sort(str, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if(o1.length() == o2.length()) {
return o1.compareTo(o2);
}
else {
return o1.length() - o2.length();
}
}
});
System.out.println(str[0]);
for(int i = 1; i < n; i++) {
if(!str[i].equals(str[i - 1])) {
System.out.println(str[i]);
}
}
}
}
오늘의 회고
오늘은 어제 못풀었던 정렬에 관한 쉬운 문제 2문제를 풀어봤습니다. 정렬의 comparator를 이용하는 문제에서 아직은 완벽하게 구현하기 부족한 점이 있고 복습을 하면서 완전하게 내것으로 만들어야 될 것 같습니다. 아직 갈 길이 멀지만 급하게 하지 않고 천천히 꾸준하게 준비하겠습니다.
