백준 (30) 썸네일형 리스트형 16165번: 걸그룹 마스터 준석이(Java) 익숙한 문제이다. HashMap을 써서 그룹명을 key로 가지고 멤버를 value로 가지게 한 후, 문제 유형에 따라 처리하면 된다. 우선 데이터를 입력받는다. Scanner scanner = new Scanner(System.in); int groupNum = scanner.nextInt(); int quizNum = scanner.nextInt(); HashMap glist = new HashMap(); String groupName, problem; int groupSize; for(int i = 0; i 9935번:문자열 폭발(Java) 처음에는 String과 contains, replace 함수를 사용해 풀었다. 그런데 메모리 초과가 났다. 문자열의 길이가 1,000,000이나 되는 것이 원인이라고 생각해 Stack을 사용해 풀었다. Stack에 문자열을 하나씩 넣으면서 Stack에 폭탄이 들어가게 되면 그 부분만큼 pop()을 해 주었다. stack의 크기가 폭탄 문자열의 길이 이상이 되었을 때부터 검사를 시작한다. stack에서 폭탄 문자열이 시작되는 지점부터 폭탄 문자열이 끝나는 지점까지의 모든 문자가 같으면 stack은 현재 폭탄 문자열을 포함하고 있는 의미이기 때문에, find에 true를 넣고 stack의 크기에서 폭탄 문자열의 길이만큼을 뺸 것을 get() 해 문자를 얻고 이게 폭탄 문자열의 charAt()과 다르면 fin.. 5052번:전화번호 목록(Java) 문제에서 전화번호는 10자리 이하라고 했다. int 자료형의 범위는 -2,147,483,648 ~ 2,147,483,647 이므로 int 자료형을 쓰면 모든 전화번호를 저장할 수 없으므로 String 배열을 전화번호부로 사용했다. 전화번호를 입력받고 Arrays.sort()로 오름차순으로 정렬한 후, startsWith 함수로 현재 index + 1 번째 문자열이 현재 index를 포함하는지 검사한 후 출력했다. 오름차순으로 정렬되어 있으므로 +1 번째만 검사하면 된다. 이렇게 하면 시간복잡도를 O(n^2)으로 줄일 수 있다. 결과 코드 import java.util.*; public class Main { public static void main(String[] args) { Scanner scann.. 5430번:AC(Java) int 배열과 시작, 끝, 현재 index를 사용해 풀었다. R을 할 때마다 순서를 바꾸는 것은 시간이 너무 오래 걸릴 것이라 판단했다. 배열을 그대로 두고 연산 실행 시 시작, 끝, 현재 index 연산만 하면 시간복잡도를 줄일 수 있을 거라고 생각했다. 메모리는 D를 할 때마다 조금씩 낭비될 수는 있지만 시간을 줄이는 것이 더 이득이라 생각한 결과이다. 변수들을 다음과 같이 선언했다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] list;//배열 int n = Integer.parseInt(br.readLine());//반복 횟수 String[] order;//명령 int size;//배열 크기 int .. 1927번:최소 힙(Java) PriorityQueue를 사용했다. 오름차순으로 우선순위가 되는 PriorityQueue를 선언하고 0이 입력되면 PriorityQueue가 비어있는지 확인 후 출력한다. 0이 아닌 수가 입력되면 PriorityQueue에 add 해 준다. 결과 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sy.. 11286번:절댓값 힙(Java) PriorityQueue를 두 개 사용해 풀었다. 양수를 저장하는 positive PriorityQueue는 오름차순으로 정령하도록 선언하고 음수를 저장하는 negavite PriorityQueue는 내림차순으로 정렬하기 위해 Collections.reverseOrder()를 사용했다. 입력된 수의 조건에 따라 저장했다. 0이 입력됐을 때는 PriorityQueue의 peek()를 통해 절댓값을 비교해 출력했다. 변수 선언 Scanner scanner = new Scanner(System.in); PriorityQueue positive = new PriorityQueue(); PriorityQueue negative = new PriorityQueue(Collections.reverseOrder());.. 1302번: 베스트셀러(Java) HashMap을 써서 제목과 입력 횟수를 저장하고 keySet을 순환하면서 최대로 입력받는 제목을 구함과 동시에 사전순으로 제일 빠른 제목을 찾았다. 우선 HashMap을 써서 제목을 입력받을 때마다 몇 번 입력받았는지 Value에 저장했다. Scanner scanner = new Scanner(System.in); String title; HashMap list = new HashMap(); int n = scanner.nextInt(); int max = 1; String result; for(int i = 0; i max) { result = i; max = list.get(i); } else if(list.get(i) == max && i.compareTo(result) < 0) { result .. 1158번: 요세푸스 문제(Java) Queue를 사용해 풀었다. 우선 필요한 변수를 선언하고 데이터를 입력받아 Queue에 넣는다. Queue queue = new LinkedList(); StringBuilder result = new StringBuilder(""); System.out.println(result); 결과 코드 import java.util.*; public class Main { public static void main(String[] args) { Queue queue = new LinkedList(); StringBuilder result = new StringBuilder(""); System.out.println(result); } } 11399번: ATM(Java) 정렬 문제이다. 정렬 후 P1, P1+P2, P1+P2+P3 ....... 을 모두 더하면 된다. 이걸 나열해 보면 if(n = 5) result = P1+ P1+P2+ P1+P2+P3+ P1+P2+P3+P4+ P1+P2+P3+P4+P5 가 되고 이것은 P1*n + P2*n-1 + P3*n-2 + P4*n-3 + P4*n-4 + P5*n-5 을 의미한다. 이걸 반복문으로 나타내면 다음과 같다. for(int i = 0; i 1406번: 에디터(Java) 처음에는 LinkedList로 간단하게 풀 수 있을 거라고 생각했다. BufferedReader와 LinkedList로 풀었는데 계속 시간 초과가 나왔다. 생각해 보니 시간복잡도가 O(n^2)이 나왔다. 시간복잡도를 O(n)으로 줄일 수 있는 방법이 무엇인지 고민하다가 Stack 두 개를 사용하면 삽입, 삭제를 O(1) 만에 할 수 있을 것 같아 Stack 두 개를 사용하기로 했다. left, right 라는 Stack을 두 개 만들고 우선 left에 모든 문자를 넣은 후 커서를 left의 top으로 잡았다. 커서가 왼쪽으로 갈 때마다 right에 left.pop()을 push 하고 커서가 오른쪽으로 갈 때는 left에 right.pop()을 push 하면 된다. BufferedReader br = ne.. 이전 1 2 3 다음
