| 문제번호 | 제목 | 난이도 |
|---|---|---|
| 17225번 | 세훈이의 선물가게 | 실버 1 |
17225번 세훈이의 선물가게
해결코드:
import java.io.*;
import java.util.*;
class Present{
int time;
char color;
public Present(int time, char color) {
this.time = time;
this.color = color;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
PriorityQueue<Present> pq = new PriorityQueue<>((o1,o2) ->{
if(o1.time == o2.time){
return o1.color - o2.color;
}
return o1.time - o2.time;
});
int tmpA = 0;
int tmpB = 0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int time = Integer.parseInt(st.nextToken());
char color = st.nextToken().charAt(0);
int count = Integer.parseInt(st.nextToken());
for (int j = 0; j < count; j++) {
if(color == 'B'){
if(tmpA >= time){
pq.add(new Present(tmpA, color));
tmpA += A;
}else{
pq.add(new Present(time, color));
tmpA = time + A;
}
}else{
if(tmpB >= time){
pq.add(new Present(tmpB, color));
tmpB += B;
}else{
pq.add(new Present(time, color));
tmpB = time + B;
}
}
}
}
int count = 1;
List<Integer> p1 = new ArrayList<>();
List<Integer> p2 = new ArrayList<>();
while(!pq.isEmpty()){
Present present = pq.poll();
if(present.color == 'B'){
p1.add(count);
}else{
p2.add(count);
}
count++;
}
bw.write(p1.size() + "\n");
for (int i = 0; i < p1.size(); i++) {
bw.write(p1.get(i) + " ");
}
bw.write("\n" + p2.size() + "\n");
for (int i = 0; i < p2.size(); i++) {
bw.write(p2.get(i)+" ");
}
br.close();
bw.close();
}
}
해결 키포인트:
- 우선순위 큐를 사용해서 시간복잡도를 줄이고,
입력 단계에서 누적시간을 계산하여 우선순위 큐에 넣는 것이 해결 키포인트
고민/풀이흐름:
- 주어진 조건을 위해 우선순위 큐를 사용하였다. 시간이 같을 경우 색깔을 기준으로 오름차순 정렬하고 다른 경우 시간을 기준으로 오름차순 정렬한다.
- 색깔을 기준으로 오름차순 정렬하는 이유는 어차피 B가 R보다 사전상 앞에 있기 때문에 같은 시간에 올 경우 상민이가 먼저 시작한다는 조건을 만족하기 때문이다
- tmpA와 tmpB 변수는 누적 시간을 담을 변수이다. 만약 각각이 현재 입력 시간보다 크거나 같다면 대신하여 넣고 아닐 경우 현재 입력 시간을 넣어준다.
- tmpA와 tmpB에는 각각 반복하는 만큼 작업 시간을 더해서 넣어준다
- 상민이와 지수의 작업 선물 번호는 리스트에 관리한다
- 우선순위큐가 빌때까지 반복해서 꺼내고 각 색깔에 맞게 count를 넣어준다
- 이후 출력 조건에 맞게 출력하면 정답이 된다.
문제 발생
서브태스크 2번이 시간초과 되는 문제가 발생하였다.
문제를 차근차근 되돌아가면서 분석하였을 때, 2가지 위치에서 시간초과가 발생할 수 있음을 예상하였다
1. 입력값을 받고 우선순위 큐에 넣는 부분
2. 리스트에 넣고 조회하는 부분
문제 원인 분석
1 . 입력값을 받고 우선순위 큐에 넣는 부분
이 부분은 이중포문이기에 시간초과 발생 위험이 가장 큰 곳이다.
하지만 시간복잡도를 계산했을 때, O(n*m)이 최악의 경우이고,
이때 1,000 x 100 = 100,000이기 때문에 시간초과 문제가 발생하지는 않는다.
2 . 리스트에 넣고 조회하는 부분
그렇다면 2번 부분에서 발생했을 확률이 높아진다.
수많은 검색과 힌트를 찾아본 결과 처음에 List를 LinkedList로 선언해서 발생한 문제임을 발견하였다.
ArrayList vs LinkedList 비교
ArrayList와 LinkedList의 특징을 비교하면 다음과 같다
| ArrayList | LinkedList | |
|---|---|---|
| 컬렉션 | 배열이용 | 노드 이용 |
| 데이터 접근시간 | 모든 데이터 상수 시간 접근 | 위치에 따라 이동시간 발생 |
현재 중심으로 살펴보아야하는 특징만 가져왔다.
데이터 접근시간과 컬렉션 특징을 비교했을 때, 조회를 하는 get에서의 성능 차이를 보일 것임을 짐작할 수 있다.
ArrayList는 연속적인 묶음으로 자료를 메모리에 저장하지만,
LinkedList는 자료를 메모리에 불연속적인 단위로 저장한다
위 방식이 ArrayList의 저장 방식이다. 스택 영역에 메모리를 하나 할당하고 그 내부 값은 힙 영역에 저장한다
다음은 LinkedList의 저장방식이다. 각각의 요소별로 별도의 메모리에 할당하는 것을 확인할 수 있다.
두 저장방식을 그림으로 확인했을 때, 왜 LinkedList가 ArrayList보다 get에서의 속도가 더 걸리는지 이해할 수 있을 것이다
다음 코드로 직접 시간을 측정해보았다
public class Main {
public static void main(String[] args) throws IOException {
List<Integer> p1 = new ArrayList<>();
List<Integer> p3 = new LinkedList<>();
for (int i = 0; i < 100000; i++) {
p1.add(i);
p3.add(i);
}
System.out.println("ArrayList 시간: " + li(p1));
System.out.println("LinkedList 시간: " + li(p3));
}
public static long li(List p){
long start = System.nanoTime();
for (int i = 0; i < 100000; i++) {
p.get(i);
}
long end = System.nanoTime();
return end-start;
}
}
두번 정도 실행했을 때, 다음과 같은 결과를 얻었다
원소를 찾는 get을 호출할때,
ArrayList에 비해 LinkedList에서 압도적으로 시간이 많이 걸리는 것을 실제 코드로도 확인해볼 수 있었다
위 성능 테스트 표를 보았을 때도 get에서의 두 시간차이는 엄청 많이 나는 것을 확인할 수 있다.
해당 문제와의 비교
최악의 경우 n*m의 시간복잡도가 발생할 것으로 예상한다면 대략 100,000정도의 순회를 돌게 된다.
ArrayList의 경우 O(1)이기 때문에 문제 없이 통과하게 된다.
하지만 LinkedList는 통과하지 못한다
LinkedList는 앞서 말했듯이 get에서 O(n)이라는 시간복잡도를 갖는다.
따라서 순회에서의 nm, 조회에서의 nm이 만나 O((n*m)^2)라는 최악의 시간복잡도를 낳는다
100,000 ^ 2은 10,000,000,000은 10억이므로 시간제한 1초를 아득히 넘어서게 된다.
따라서 ArrayList로 리스트를 선언해야지 시간제한없이 해결할 수 있다
결론
LinkedList가 ArrayList에 비해 강점을 갖을 때는 중간 삽입 삭제가 들어가는 경우다.
그 이외의 경우에는 ArrayList를 사용하자.
또한 해당 문제에서는 시간제한을 피하기 위해 리스트를 ArrayList로 선언하자!
문제 링크:
참고:
