hhseob1211   1년 전

안녕하세요 백준 단계별로 풀어보기로 코딩 공부하고 있는 학생입니다.

제가 이번 10814 문제를

Arrays.sort(arr, (a, b) -> {

return Integer.parseInt(a[0])-Integer.parseInt(b[0]) ;

});

이것을 이용하여 문제를 해결했는데

다른 사람들의 코드를 보니까 대부분이 StringBuilder를 이용하여 해결하는 것을 확인했습니다.

아직 초보인 제가 보기엔 StringBuilder보다 Arrays.sort에 람다식을 사용하는 것이 더 좋아보이는데 StringBuilder를 사용한 이유가 무엇이 있을까요?

arrays.sort는 제가 알고 있는 내용과는 다르게 안정 정렬이 안 되는 건가요? 아님 메모리적으로 또는 시간적으로 더 좋은 건가요?

djm03178   1년 전

어떤 코드를 보신 것인지 모르겠지만 정렬을 하는 것과 StringBuilder를 쓰는 것은 전혀 별개의 사안 같습니다. 말씀하신 대로 정렬을 하고 답 문자열을 StringBuilder로 출력하는 것도 가능합니다. Arrays.sort는 정렬하는 방법 중 하나이고, StringBuilder는 답을 출력하는 방법 중 하나로 서로 아무런 연관이 없습니다.

hhseob1211   1년 전

죄송합니다. 제가 질문글을 처음 올려서 설명이 부족했던 것 같습니다.

StringBuilder[] sb = new StringBuilder[201];

for(int i = 0; i <=200; i++) {

sb[i] = new StringBuilder();
}

이런식으로 구현해서 입력된 나이를 sb의 index로 사용하여 해당 index에 존재하는 StringBuilder에 입력된 나이와 이름을 추가하는 것입니다. 주어진 input이 끝나면 sb의 0부터 각 StringBuilder에 입력된 값들을 순서대로 출력하는 방식으로 구현하는 방법을 확인했습니다. 

저의 질문을 아직 많이 미숙한 제가 보기엔 해당 방법보단 Arrays.sort방식이 더 간결해 보이는데 해당 방법을 사용한 이유를 조금 알고싶습니다.

bupjae   1년 전

목격하신 프로그램은 계수 정렬 (Counting sort) 이라는 알고리즘을 구현한 것으로, 다소 특이한 방식으로 정렬하는 알고리즘입니다.

정렬해야 할 값의 범위가 '셀 수 있으면서' 좁을 때 효율적으로 동작하는 알고리즘입니다.

범용 정렬 알고리즘의 시간복잡도가 O(n log n) 이라면, 계수 정렬의 시간복잡도는 O(n) 입니다.

반면, 계수 정렬은 공간 복잡도로 O(m) 을 가집니다. (여기서 m 은 계수의 범위로, 이 문제에서는 나이로 주어지는 범위 1~200 인 200 을 의미합니다)

.

쉽게 풀어쓰자면, 이 정렬을 하기 위해 추가적으로 O(m) 만큼의 저장공간이 더 필요하다는 뜻으로, StringBuilder[] sb = new StringBuilder[201]; 가 바로 그 역할을 합니다.

.

(엄밀히 이여기하면 이 문제에서는 정렬 과정에서 단순 계수 이상의 정보를 저장해야 하므로 실질적인 공간 복잡도는 O(n+m) 이긴 합니다만, 중요한 내용은 아닙니다)

djm03178   1년 전

제 생각에 counting sort로 구현한 사람은 극소수에 불과할 것 같은데, 아마도 '맞은 사람' 탭에서 보셔서 그런 코드들만 보게 되신 것 같습니다. '맞은 사람' 탭은 수행 시간이 빠른 순으로 정렬되어 있고, 해당 방식은 이 문제에서 효율적이기 때문에 수행 시간이 빨라 1페이지에는 그런 코드가 많을 가능성이 높아 보입니다.

단지 알고리즘의 차원에서만 빠른 것이 아니라 말 그대로 수행 시간 랭킹 상위권을 달성하기 위해 극한의 최적화를 하는 사람들의 코드니 그 방식은 간결함과는 다소 거리가 멀 수 있습니다. 평균적인 코드를 보시려면 '채점 현황' 탭에서 최근에 맞은 사람들의 코드를 열어보는 것이 낫습니다.

댓글을 작성하려면 로그인해야 합니다.