오늘의 학습 키워드 및 문제
#큐 #Queue #ArrayDeque
백준 실버4) 식당 메뉴
문제풀이
이 문제.. 나로서는 풀기가 상당히 어려웠다..
문제를 맞췄을 때 실행 시간 보고 한번 놀랐고 다른 사람들과 비교했을 때 내 시간이 꽤나 오래걸려서 두번 놀랐다.
그래도 결국 맞춰서 기분은 좋다><
문제에서는 문자열 유형을
1 a b (a: 학생번호, b: 식사메뉴) => 학생 대기
2 b (b: 식사메뉴) => 배식
이렇게 나누고 있었다.
나는 학생이 원하는 식사 메뉴를 큐에 담고 메뉴가 나오면 원하는 메뉴인지, 원하지 않는 메뉴인지에 따라 나누면 되겠구나 생각했다.
그런데 학생이 원하는 식사 메뉴를 큐에 담으면 학생 번호는 어떻게 해야하는거지..? 라는 생각에 Map이 바로 떠올랐다.
그러면서 Key가 중복되어도 상관이 없고, 순서가 있도록 하는 방법이 없나 생각하다가 List<Map.Entry<Integer,Integer>>로 풀어야겠다고 생각했다.
[시간초과]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
List<Integer> A = new ArrayList<>();
List<Integer> B = new ArrayList<>();
List<Map.Entry<Integer, Integer>> list = new ArrayList<>();
int n = Integer.parseInt(br.readLine());
for (int i=0; i<n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
if (st.nextToken().equals("1")) {
// 학생번호, 음식번호 저장
int key = Integer.parseInt(st.nextToken());
int value = Integer.parseInt(st.nextToken());
list.add(new AbstractMap.SimpleEntry<>(key, value));
} else {
// 음식 비교 및 그룹 나누기기
if (list.size() > 0) {
Map.Entry<Integer, Integer> map = list.get(0);
if (map.getValue() == Integer.parseInt(st.nextToken())) {
A.add(map.getKey());
} else {
B.add(map.getKey());
}
list.remove(0);
}
}
}
// 출력
// A
if (A.size() > 0) {
A.sort((a,b) -> a.compareTo(b)); // 오름차순 정렬
for (Integer a : A) {
sb.append(a).append(" ");
}
} else {
sb.append("None");
}
sb.append("\n");
// B
if (B.size() > 0) {
B.sort((a,b) -> a.compareTo(b)); // 오름차순 정렬
for (Integer b : B) {
sb.append(b).append(" ");
}
} else {
sb.append("None");
}
sb.append("\n");
// C
if (list.size() > 0) {
Collections.sort(list, Map.Entry.comparingByKey()); // 오름차순 정렬
for (Map.Entry<Integer, Integer> m : list) {
sb.append(m.getKey()).append(" ");
}
} else {
sb.append("None");
}
System.out.println(sb);
br.close();
}
}이 코드로 작성하면서도 이게 맞나.. 싶었지만 그래도 끝까지 해보는 것도 중요하다고 생각하여 끝까지 작성해봤다.
이 방법이 아니라면 어떻게 학생번호를 저장하면서 학생이 원하는 메뉴도 저장하지..? 생각하던 중
내 코드에서 List<Map.Entry<Integer,Integer>>를 학생 목록 C로 출력한 것이 보여서
아! List<Map.Entry<Integer,Integer>> 대신 A,B와 똑같이 학생 목록 담을 곳을 List로 만들면 되겠군! 학생은 C에 넣고 학생이 원하는 메뉴는 ArrayDeque에 넣어서 메뉴가 나오면 ArrayDeque의 값을 빼서 비교하여 A와 B에 알맞게 넣어주고 C에 있는 값은 제거하면 될 것 같았다.
[결과] 189952KB 2916ms
++ 다른 날 같은 코드를 다시 제출했더니 시간초과 뜸.. 통과는 운이 좋았던건가..
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
Deque<Integer> queue = new ArrayDeque<>();
List<Integer> A = new ArrayList<>();
List<Integer> B = new ArrayList<>();
List<Integer> C = new ArrayList<>();
int n = Integer.parseInt(br.readLine());
for(int i=0; i<n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
if(st.nextToken().equals("1")) {
int student = Integer.parseInt(st.nextToken());
int menu = Integer.parseInt(st.nextToken());
C.add(student);
queue.add(menu);
} else {
int menu = Integer.parseInt(st.nextToken());
if (C.size() > 0 && !queue.isEmpty()) {
if(menu == queue.remove()) {
A.add(C.get(0));
} else {
B.add(C.get(0));
}
C.remove(0);
}
}
}
// 출력
if (A.size() > 0) {
A.sort((a,b) -> a.compareTo(b));
for(Integer a : A) {
sb.append(a).append(" ");
}
} else {
sb.append("None");
}
sb.append("\n");
if (B.size() > 0) {
B.sort((a,b) -> a.compareTo(b));
for(Integer b : B) {
sb.append(b).append(" ");
}
} else {
sb.append("None");
}
sb.append("\n");
if (C.size() > 0) {
C.sort((a,b) -> a.compareTo(b));
for(Integer c : C) {
sb.append(c).append(" ");
}
} else {
sb.append("None");
}
System.out.println(sb);
br.close();
}
}다른방법
이 문제를 풀었긴 했지만 내 코드는 메모리 사용량도 많고 시간도 오래걸리는 편이었다..
다른 사람의 코드를 참고하여 다시 풀어보았다.
[기존방법] 189952KB 2916ms
[다른방법] 203364KB 1376ms
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
List<Integer> A = new ArrayList<>();
List<Integer> B = new ArrayList<>();
Deque<int[]> queue = new ArrayDeque<>();
int n = Integer.parseInt(br.readLine());
for(int i=0; i<n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
if(st.nextToken().equals("1")) {
int student = Integer.parseInt(st.nextToken());
int menu = Integer.parseInt(st.nextToken());
queue.add(new int[]{student, menu});
} else {
int menu = Integer.parseInt(st.nextToken());
if (!queue.isEmpty()) {
if(menu == queue.peek()[1]) {
A.add(queue.poll()[0]);
} else {
B.add(queue.poll()[0]);
}
}
}
}
// 출력
// A
if (A.size() > 0) {
A.sort((a,b) -> a.compareTo(b)); // 오름차순 정렬
for(Integer a : A) {
sb.append(a).append(" ");
}
} else {
sb.append("None");
}
sb.append("\n");
// B
if (B.size() > 0) {
B.sort((a,b) -> a.compareTo(b)); // 오름차순 정렬
for(Integer b : B) {
sb.append(b).append(" ");
}
} else {
sb.append("None");
}
sb.append("\n");
// C
if (queue.size() > 0) {
List<Integer> C = new ArrayList<>();
for(int[] i : queue) {
C.add(i[0]);
}
C.sort((a,b) -> a.compareTo(b)); // 오름차순 정렬
for(Integer c : C) {
sb.append(c).append(" ");
}
} else {
sb.append("None");
}
System.out.println(sb);
br.close();
}
}시간은 줄었지만 메모리 사용량은 더 많아진 아이러니한..
확실하진 않지만 원인을 적어보았다.
메모리 사용량 증가 원인?
- 배열을 사용하여 큐에 저장?
기존 방법으로는Deque<Integer>를 사용하여 단일 값만 저장했지만
다른 방법으로는Deque<int[]>을 사용하여 다중 값을 저장
속도 증가 원인?
- C 변수의 원소 제거 (ArrayList의 remove)
ArrayList의 첫번째 요소를 제거하면, 뒤의 모든 요소를 한 칸씩 앞으로 이동해야 함으로 O(n)의 시간복잡도를 가짐
ArrayDeque의 poll()을 사용하여 O(1)로 제거하여 속도 빠름
공부한 내용정리
- ArrayList의 정렬방법
- Collection.sort(list) - 오름차순
- list.sort((a,b) -> a.compareTo(b)) - 오름차순
- list.sort((a,b) -> b.compareTo(a)) - 내림차순
Please, Steadily