+) 풀이 코드
https://github.com/jung0115/CodingTestPractice.git
GitHub - jung0115/CodingTestPractice: Practice Coding Test with Beakjoon, programmers, etc.
Practice Coding Test with Beakjoon, programmers, etc. - GitHub - jung0115/CodingTestPractice: Practice Coding Test with Beakjoon, programmers, etc.
github.com
+) 백준에 Java 코드를 제출할 때는 class명을 Main으로 해주어야 오류가 발생하지 않는다.
2750번 - 2022.01.14.금
import java.util.Scanner; public class Main { public static void main(String[] args) { int N; Scanner scan = new Scanner(System.in); N = scan.nextInt(); int[] num = new int[N]; for(int i = 0; i < N; i++) { num[i] = scan.nextInt(); } scan.close(); for(int i = 0; i < N-1; i++) { int min = i; for(int j = i+1; j < N; j++) if(num[j] < num[min]) min = j; if(min != i){ int tmp = num[min]; num[min] = num[i]; num[i] = tmp; } System.out.println(num[i]); } System.out.println(num[N-1]); } }
2751번 - 2022.01.17.월 (Time Limited)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main{ static int[] num; public static void main(String[] args) throws IOException { int N; BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(bf.readLine()); num = new int[N]; for(int i = 0; i < N; i++) { num[i] = Integer.parseInt(bf.readLine()); } quickSort(0, N-1); StringBuilder printSet = new StringBuilder(); for(int i = 0; i < N; i++) printSet.append(num[i] + "\n"); System.out.print(printSet); } static int partition(int start, int end) { int pivot, left, right; boolean done; pivot = num[start]; left = start+1; right = end; done = false; while(!done) { while(left <= right && num[left] <= pivot) left++; while(left <= right && num[right] >= pivot) right--; if(right < left) done = true; else { int tmp = num[left]; num[left] = num[right]; num[right] = tmp; } } int tmp = num[start]; num[start] = num[right]; num[right] = tmp; return right; } static void quickSort(int start, int end) { if(start < end) { int pivot = partition(start, end); quickSort(start, pivot-1); quickSort(pivot+1, end); } } }
입출력에서 시간을 줄여봐도 시간초과가 걸리고, Quick sort를 이용해도 시간초과가 됐다. 퀵 정렬을 사용했을 경우 최악의 시간복잡도가 O(n^2)가 나올 수 있는데, 입력 데이터 중에 이 최악의 경우를 나오게 유도하는 값이 있다고 한다. 그래서 평균적인, 최악의 시간 복잡도도 빠른 정렬 방법을 사용해야 한다.
2751번 - 2022.01.19.수 (해결)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(bf.readLine()); ArrayList<Integer> num = new ArrayList<Integer>(); for(int i = 0; i < N; i++) num.add(i, Integer.parseInt(bf.readLine())); Collections.sort(num); //Timsort StringBuilder printSet = new StringBuilder(); for(int set : num) printSet.append(set).append("\n"); System.out.print(printSet); } }
입출력에 BufferedReader, StringBuilder 사용하고 정렬은 Timsort 방법 사용. Timsort 정렬 알고리즘 정확히 이해하고 직접 코드 작성해볼 필요 있음.
10989번 - 2022.01.19.수
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(bf.readLine()); int[] nums = new int[N]; for(int i = 0; i < N; i++) nums[i] = Integer.parseInt(bf.readLine()); int[] count = new int[10001]; int max = 0; //기본적으로 java는 int 배열이 0으로 초기화 됨. for(int n : nums) { count[n]++; if(n > max) max = n; } for(int i = 1; i <= max; i++) count[i] += count[i-1]; int[] setNums = new int[N]; for(int i = N-1; i >= 0; i--) { int n = nums[i]; count[n]--; setNums[count[n]] = n; } StringBuilder printSet = new StringBuilder(); for(int set : setNums) printSet.append(set).append("\n"); System.out.print(printSet); } }
Counting sort 방식 이용
2108번 - 2022.01.20.목
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(bf.readLine()); ArrayList<Integer> nums = new ArrayList<Integer>(); for(int i = 0; i < N; i++) nums.add(i, Integer.parseInt(bf.readLine())); Collections.sort(nums); //Timsort double sum = 0; int[][] cnt = new int[2][2]; boolean check = true; for(int n : nums) { sum += n; if(cnt[1][1] == 0 || cnt[1][0] == n) { cnt[1][0] = n; cnt[1][1]++; } else { if(cnt[0][1] < cnt[1][1]) { check = true; cnt[0][0] = cnt[1][0]; cnt[0][1] = cnt[1][1]; } else if(cnt[0][1] == cnt[1][1] && check) { check = false; cnt[0][0] = cnt[1][0]; cnt[0][1] = cnt[1][1]; } cnt[1][0] = n; cnt[1][1] = 1; } } if(cnt[0][1] < cnt[1][1] || (cnt[0][1] == cnt[1][1] && check)) { cnt[0][0] = cnt[1][0]; cnt[0][1] = cnt[1][1]; } StringBuilder printSet = new StringBuilder(); printSet.append(Math.round(sum/N)).append("\n"); //산술평균 printSet.append(nums.get(N/2)).append("\n"); //중앙값 printSet.append(cnt[0][0]).append("\n"); //최빈값 printSet.append(nums.get(N-1) - nums.get(0)); //범위 System.out.print(printSet); } }
1427번 - 2022.01.20.목
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(bf.readLine()); ArrayList<Integer> nums = new ArrayList<Integer>(); int len = 0; for(int i = 0; N > 0; i++) { nums.add(i, N%10); N /= 10; len++; } Collections.sort(nums); //Timsort StringBuilder printSet = new StringBuilder(); for(int i = len-1; i >= 0; i--) printSet.append(nums.get(i)); System.out.print(printSet); } }
11650번 - 2022.01.20.목 (Time Limited)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(bf.readLine()); int[][] dots = new int[N][2]; for(int i = 0; i < N; i++) { StringTokenizer st = new StringTokenizer(bf.readLine()); dots[i][0] = Integer.parseInt(st.nextToken()); dots[i][1] = Integer.parseInt(st.nextToken()); } int[] set = new int[N]; for(int i = 0; i < N; i++) { int cnt = 0; for(int j = 0; j < N; j++) { //dots[i]보다 앞에 위치하는 좌표의 개수 count if(dots[i][0] > dots[j][0] || (dots[i][0] == dots[j][0] && dots[i][1] > dots[j][1])) cnt++; } set[cnt] = i; } StringBuilder printSet = new StringBuilder(); for(int i = 0; i < N; i++) printSet.append(dots[set[i]][0]).append(" ").append(dots[set[i]][1]).append("\n"); System.out.println(printSet); } }
좌표값이 저장된 배열을 정렬하지 않고 각 좌표의 앞에 위치하는 좌표의 개수를 세어 몇 번째에 올지 파악하는 형태로 코드를 작성했다. 답은 제대로 나오지만 시간초과가 걸리고 말았다... 시간을 단축하는 방법을 생각해봤지만 해당 방법으로는 더이상 단축을 할 수 없을 것 같아 새로운 방법을 찾아보았다.
11650번 - 2022.01.20.목 (해결)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(bf.readLine()); int[][] dots = new int[N][2]; for(int i = 0; i < N; i++) { StringTokenizer st = new StringTokenizer(bf.readLine()); dots[i][0] = Integer.parseInt(st.nextToken()); dots[i][1] = Integer.parseInt(st.nextToken()); } //람다식(익명함수) 이용 Arrays.sort(dots, (dot1, dot2) -> { if(dot1[0] == dot2[0]) //x좌표 값이 같은 경우 y좌표로 비교 return dot1[1] - dot2[1]; else //다른 경우 x좌표로 비교 return dot1[0] - dot2[0]; }); StringBuilder printSet = new StringBuilder(); for(int i = 0; i < N; i++) printSet.append(dots[i][0]).append(" ").append(dots[i][1]).append("\n"); System.out.println(printSet); } }
Array.sort() 메소드를 이용하여 시간초과를 해결하였다. 람다식을 적절히 사용해서 2차원 배열을 정렬할 수 있다.
11651번 - 2022.01.21.금
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(bf.readLine()); int[][] dots = new int[N][2]; for(int i = 0; i < N; i++) { StringTokenizer st = new StringTokenizer(bf.readLine()); dots[i][0] = Integer.parseInt(st.nextToken()); dots[i][1] = Integer.parseInt(st.nextToken()); } //람다식(익명함수) 이용 Arrays.sort(dots, (dot1, dot2) -> { if(dot1[1] == dot2[1]) //y좌표 값이 같은 경우 x좌표로 비교 return dot1[0] - dot2[0]; else //다른 경우 y5좌표로 비교 return dot1[1] - dot2[1]; }); StringBuilder printSet = new StringBuilder(); for(int i = 0; i < N; i++) printSet.append(dots[i][0]).append(" ").append(dots[i][1]).append("\n"); System.out.println(printSet); } }
11650번 푼 방식에서 정렬 기준을 y로만 바꿔주었다.
1181번 - 2022.01.21.금
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(bf.readLine()); String[] words = new String[N]; for(int i = 0; i < N; i++) { words[i] = bf.readLine(); } //람다식(익명함수) 이용 Arrays.sort(words, (word1, word2) -> { int len1, len2; len1 = word1.length(); len2 = word2.length(); if(len1 == len2) //단어의 길이가 같은 경우 사전순으로 return checkDic(word1, word2, len1); else //다른 경우 단어의 길이가 짧은 순으로 return len1 - len2; }); StringBuilder printSet = new StringBuilder(); String checkSame = ""; for(int i = 0; i < N; i++) { if(!words[i].equals(checkSame)) printSet.append(words[i]).append("\n"); checkSame = words[i]; } System.out.println(printSet); } static int checkDic(String word1, String word2, int len) { char[] word1Char, word2Char; word1Char = word1.toCharArray(); word2Char = word2.toCharArray(); for(int i = 0; i < len; i++) { if(word1Char[i] < word2Char[i]) return -1; else if(word1Char[i] > word2Char[i]) return 1; } return -1; } }
10814번 - 2022.01.25.화
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(bf.readLine()); String[][] people = new String[N][2]; for(int i = 0; i < N; i++) { StringTokenizer st = new StringTokenizer(bf.readLine()); people[i][0] = st.nextToken(); people[i][1] = st.nextToken(); } Arrays.sort(people, (person1, person2) -> { int age1, age2; age1 = Integer.parseInt(person1[0]); age2 = Integer.parseInt(person2[0]); if(age1 == age2) return 0; else return age1 - age2; }); StringBuilder printSet = new StringBuilder(); for(int i = 0; i < N; i++) printSet.append(people[i][0]).append(" ").append(people[i][1]).append("\n"); System.out.println(printSet); } }
18870번 - 2022.01.25.화(Time Limited)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; import java.util.ArrayList; import java.util.HashSet; public class Main { public static void main(String[] args) throws IOException{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(bf.readLine()); ArrayList<Integer> Xdots = new ArrayList<Integer>(); StringTokenizer st = new StringTokenizer(bf.readLine()); for(int i = 0; i < N; i++) Xdots.add(i, Integer.parseInt(st.nextToken())); HashSet<Integer> hashSet = new HashSet<Integer>(Xdots); //HashSet 이용하여 중복 값 삭제 //좌표 압축 int[] resultXdots = new int[N]; for(int i = 0; i < N; i++) { int checkXdot = Xdots.get(i); for(int Xdot : hashSet) if(Xdot < checkXdot) resultXdots[i]++; } StringBuilder printSet = new StringBuilder(); for(int i = 0; i < N; i++) printSet.append(resultXdots[i]).append(" "); System.out.println(printSet); } }
HashSet을 이용하여 입력 좌표들 중 중복값을 삭제하고, 자신보다 작은 수를 세는 형태로 계산을 했는데, 답은 나오지만 시간초과가 걸렸다.
18870번 - 2022.01.25.화(해결)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; public class Main { public static void main(String[] args) throws IOException{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(bf.readLine()); StringTokenizer st = new StringTokenizer(bf.readLine()); ArrayList<Integer> Xdots = new ArrayList<Integer>(); ArrayList<Integer> copys = new ArrayList<Integer>(); for(int i = 0; i < N; i++) { Xdots.add(i, Integer.parseInt(st.nextToken())); copys.add(Xdots.get(i)); } Collections.sort(copys); //Timsort HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>(); int rank = 0; for(int copy : copys) { if(!rankingMap.containsKey(copy)){ rankingMap.put(copy, rank); rank++; } } StringBuilder printSet = new StringBuilder(); for(int Xdot : Xdots) printSet.append(rankingMap.get(Xdot)).append(" "); System.out.println(printSet); } }
도처히 방법이 생각나질 않아서 또 검색 찬스... HashMap의 key 값을 이용하는 방식으로 했더니 시간 초과가 발생하지 않고 잘 동작했다.

'Programming > JAVA' 카테고리의 다른 글
[Java] StringBuilder로 출력하기 (0) | 2022.01.21 |
---|---|
[Java] BufferedReader로 입력 받기 (0) | 2022.01.21 |
[백준] 단계별로 풀어보기 > 브루트 포스 (Java) (0) | 2022.01.11 |
[백준] 단계별로 풀어보기 > 재귀 (Java) (0) | 2022.01.09 |
[백준] 단계별로 풀어보기 > 기본 수학2 (Java) (0) | 2021.12.29 |