문제
https://www.acmicpc.net/problem/10825 를 풀다가, 시간 초과가 발생하였다. 스스로 생각할 때는 전혀 시간초과가 날 로직이 아닌데도 불구하고 계속 시간 초과가 나는게 이상했다.
입력의 크기가 10만인데,, 아마 정렬알고리즘의 최선은 특수한 경우가 아닌경우 NlogN 으로 알고 있다. 그리고 자바스크립트의 내장 API sort 도 NlogN 으로 알고 있는데, 왜 자꾸 시간 초과가 나는지 납득하기 힘들었다. 코드를 보자.
const fs = require('fs');
const inputs = fs.readFileSync('./input.txt').toString().trim().split('\n');
const [n, ...classPeopleInfos] = inputs;
class Student {
constructor(name, kor, eng, math) {
this.name = name;
this.kor = kor;
this.eng = eng;
this.math = math;
}
}
let students = classPeopleInfos.map((people) => {
const arr = people.split(' ');
return new Student(arr[0], +arr[1], +arr[2], +arr[3]);
});
students.sort((a, b) => {
if (a.kor !== b.kor) {
return b.kor - a.kor;
}
if (a.eng !== b.eng) {
return a.eng - b.eng;
}
if (a.math !== b.math) {
return b.math - a.math;
}
if (a.name > b.name) {
return 1;
}
if (a.name < b.name) {
return -1;
}
return 0;
});
students.forEach(student => {
console.log(student.name);
});
여기서 시간초과가 나는 부분을 찾기 위해 고민을 많이 했다. 첫 번째는 sort 자체의 문제라고 생각했다.(남탓하기)
그래서 찾아보았더니 Timsort 라는 정렬 방식을 사용한다고 한다.stack overflow : what is array.prototype.sort time complexity
간략하게 설명하자면, Timsort는 최선의 경우 n, 평균, 최악의 경우 nlogn이라고 한다.. 그럼 sort의 문제도 아니다.
결국 소거법에 의해 시간복잡도가 걸리는 부분을 보면.. console.log 뿐이라는 생각이 들었다.
이러한 생각이 든 이유는 C++로 문제를 해결할 때, 간혹 endl을 사용할 때 시간초과가 나는 점이 있었다.
그래서 찾아 보았더니 아니나 다를까 console.log 문제 였다. console.log는 디버깅 용도라서 시간이 느리다고 한다.
디버깅 용이여서 그런지 알고리즘 문제에서 단순히 출력만을 제외한 부수적인 로직이 들어가 있는 것 같다.
// 기존 코드
students.forEach(student => {
console.log(student.name);
});
// 개선한 코드
let answer = '';
for (let i = 0; i < students.length; i++) {
answer += students[i].name + '\n';
}
console.log(answer);개선한 코드처럼, 한개의 문자열을 만들어서 한꺼번에 출력하면 통과하게 된다.
물론 마지막에 개행 문자가 들어가지만 PS사이트에서는 마지막에 오는 개행문자나 공백은 무시하는 것 같다.
오늘의 결론
- 되도록 for문을 통해 출력하지 말자.
추가 참고자료
