[Java] 시간낭비 방지 메모: HashXX를 보고 O(1)을 곧바로 떠올렸어야지...!

https://www.acmicpc.net/problem/11723

11723번: 집합

 

단순한 Set 문제다.

근데 시간 초과!

 

 

---

25% 시간초과

25%에서 28%까지 뚫었던 방법은, 새로운 객체 생성을 줄이는 방법으로 했다.

// set과 initSet을 두고
Set<Integer> set = new HashSet();
Set<Integer> initSet = new HashSet<>();
for(int i=1; i<=20; i++) {
    initSet.add(i);
}

...

// 기존 set에 addAll(initSet)으로 초기화시켜준다. 
// (어차피 set 내용물은 1~20인데, 이문제의 "all"은 1~20을 전부 넣어주는 연산임)
if (operator.equals("all")) {
    set.addAll(initSet);
}
// "empty"를 만들 때에는 new HashSet이 아니라 clear()를 사용해준다.
if (operator.equals("empty")) {
    set.clear();
}

 

결론적으로 시간초과를 해결하지 못했다는 것은.. 다른 부분이 문제겠지만!

 

---

28% 시간초과

 

시도1:

// 인풋 데이터가 1~20 자연수로 한정되어 있으니 배열 인덱스를 사용하는 게 가장 빠르겠다.
boolean[] set = new boolean[21];

는 역시 시간초과 ㅠㅂ ㅠ

 

애초에 잘못 생각했다. HashSet 또한 해시를 사용하기 때문에 배열인덱스처럼 O(1)이다. 즉 나는 아무런 개선을 하지 않은 것이다. HashSet을 보고 당연히 생각했어야 하는 부분인데... 옌 실망..! 다만 앞으로는 Hash라는 이름을 딱 보고 O(1)임을 파악할 수 있을 것이다.

 

 

시도2:

다른 장치를 생각해보다가... 이런 일반적인 O(1)에서 더 시간을 줄이는 것이 있을까 싶어서 System.out.println가 의심갔다(출력 줄이 M (1 ≤ M ≤ 3,000,000)로 큰 상태임) StringBuilder로 바꿔보았더니 바로 성공.. 그래도 출력이 느려서 시간초과였다니까 좀 편안해진다. 

다만 sb.append()할 때 "\n"도 넣는건 앞으로 유의해주자. 

sb.append(set.contains(operand) ? 1 : 0).append("\n");

 

 

---