인프런 커뮤니티 질문&답변

정재우님의 프로필 이미지

작성한 질문수

[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편

알고리즘 수업 - 깊이 우선 탐색 1 (백준 24479)

(백준 24479) 강의에서 오름차순 정렬시 궁금한 점이 있습니다!

해결된 질문

작성

·

363

·

수정됨

1

선생님 매번 감사합니다 유튜브부터 많이 도움을 받아 오늘 강의까지 결제하게 되었네요 :)

  1. for 문 안에 collections.sort를 사용하셔서 정렬하셨는데 저는 사실 그동안 Arrays.sort만 사용했었거든요

프로그래머스에서 다른사람 풀이를 참고하다보면 Collections.sort 가 꽤 많이 나오더라구요

합병정렬과 퀵정렬의 차이라는 이론적인 부분 외에 바꿔 사용해도 문제가 없는지, 효율적으로 다른부분이 있는지 궁금합니다!

 

  1. 추가적으로 궁금한게 하나 더 생겨서 수정합니다!

문제에서 보면 노드의 방문순서를 출력하라고 했는데

for(int i = 1; i <=N, i++) {

bw.write(String.valueOf(answer[i]));

로 출력해주셨습니다!
리스트를 정렬해주었기에 크게 문제가 없는것인가 싶은데...

조금 극단적으로 예시를

answer[1] = 1

answer[2] = 4

answer[3] = 2

answer[4] = 5

answer[5] = 3

이라고 했을때

사용해주신 방식으로 출력하면 1,4,2,5,3 이 출력되나

실제로 방문한 순서는 1,3,5,2,4로 상이하다는 생각이 들었습니다
그래서 이중 for문을 사용하여
for(int i = 1; i <=N; i++) {

for (int j = 1; j <= N; j++) {

if (i == answer[j]) 일때 j 의 값을 출력하는게

순서를 출력하는게 아닌가.. 라는 의구심이 들었습니다

혹시 제가 이해를 잘못하고 있는거라면 지적해주시면 감사히 듣겠습니다!

답변 2

2

안녕하세요 :)

  1. Arrays.sort와 Collections.sort의 가장 큰 차이점은 정렬하는 대상의 데이터 타입일 것 같아요. Arrays.sort는 말 그대로 배열에 담긴 정보를 정렬할 때 사용되는 반면, Collections.sort는 List 형태에 담긴 정보를 정렬할 때 사용한다고 생각하면 될 것 같습니다. 말씀하신 대로의 이론적인 차이가 있지만, 결국 전체 정렬을 해야 되기 때문에 저도 성능의 관점에서 유의미한 차이가 있다고 생각하진 않고 있어요. 대부분의 코딩테스트 문제는 sort 알고리즘에 따라 합격/불합격을 가르진 않을 것이라 크게 고민하진 않으셔도 될 것 같습니다!

  2. 이 부분은 문제에서 요구하는 정답이 "정점 i의 방문 순서를 출력" 였기 때문에 answer[i]를 이와 같이 정의했습니다! answer[i]는 "i번째 요소를 방문하는 순서"라고 정의했고, 그래서 1부터 N까지 순서대로 출력하면 정답이 될 것 같습니다. 예제에서 1, 2, 3, 4, 0이라고 출력한건 1번 요소 -> 2번 요소 -> 3번 요소 -> 4번 요소 순서로 방문했다는 의미가 아니라, 1번 요소는 첫번째로 방문했다 -> 2번 요소는 두번째로 방문했다 -> 3번 요소는 세번째로 방문했다 -> 4번 요소는 네번째로 방문했다 라는 의미입니다! 그래서 answer[i]를 문제에서 요구한 대로 정의했고 그대로 출력해주면 정답이 됩니다.

 

너무 좋은 질문 감사합니다! 혹시 제가 잘못 이해해서 설명을 잘못했으면 언제든 말씀해주세요!!

오늘도 공부 화이팅입니다 :)

1

정재우님의 프로필 이미지
정재우
질문자

감사합니다 선생님! 문제를 제가 잘못 이해했군요 ㅠㅠ
다시 확인하고 풀어보겠습니다! 감사합니다!

네 :) 공부 화이팅하시고 언제든 질문 남겨주세요!