# 시작
지난 주 자바스크립트 알고리즘 스터디를 들어갔다.
이전까지만 해도 자바로 프로그래머스 1단계를 풀었었는데 지금 들어가보니 1100점 정도의 점수였다. 1단계였기 때문에 실력적으로 뛰어나지 않은데 생각보다 점수가 높았다.
프로그래머스 2단계를 선택해서 문제를 풀게 된 이유는 스터디에서 이미 한달 전부터 1단계를 다 풀고 2단계를 진행중이였기 때문이다. 한동안 알고리즘 공부를 안해서 적응하기 굉장히 힘들겠다는 생각이 들었다. 이 문제는 알고보니 3단계 문제였고, 총 3문제 중에 1문제만 2단계고 나머지는 3단계였다. 스터디에서 11월 11일까지 풀어야 했던 문제가 내가 풀어봤던 1단계 문제였다. 스터디는 매주 3문제씩 과제를 풀어야 하는데 진도 차이가 어마어마해서 큰일이다.
깃헙에서 리드미 파일로 문제와 문제 풀이 등을 올릴까 했는데 문법도 불편하고 아는 문법 내에서 예쁘게 꾸미려고 해도 티스토리에 비해 많이 부족하다 느껴서 티스토리 블로그를 만들어서 여기에 올리면서 정리할 것이다. 일단은 코드만 깃헙에 올릴 생각이다.
=> 코드 작성하다가 var을 남발하던 것을 let과 const로 변경하였으나 여기에 올린 코드는 console.log나 let으로 바뀐 코드로 두지 않았다. 알고리즘 공부하는 데에는 좀더 보기 편할 것 같아서 그대로 뒀다.
# 문제
문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
입출력 예 설명
예제 #1
[ICN, JFK, HND, IAD] 순으로 방문할 수 있습니다.
예제 #2
[ICN, SFO, ATL, ICN, ATL, SFO] 순으로 방문할 수도 있지만 [ICN, ATL, ICN, SFO, ATL, SFO] 가 알파벳 순으로 앞섭니다.
# 과정 (Java -> Javascript)
- ICN에서 출발해야 하고 ICN이 출발지인 티켓이 몇 장일지는 알 수 없다.
- 리턴 조건에서 리턴 배열의 첫 번째는 ICN이 들어가야만 한다.
- ICN이 있는 티켓은 출발지와 도착지를 모두 남기고, 나머지 티켓들은 도착지만 남겨야 한다.
"재귀함수를 통해 DFS를 수행하려면 항상 똑같은 조건이 필요하므로 (같은 내용의 함수를 계속 호출하므로) 위의 내용을 이해해야 한다.
이번 문제는 단순한 재귀함수가 아니라 출발지가 ICN이면 처리가 달라진다.(재귀함수 내에 조건문 or 첫 재귀함수 호출 전에 ICN을 따로 처리한 다음 재귀함수 호출), 후자로 구현.
먼저 결과를 담아줄 List를 만든다. 그리고 첫 티켓을 설정할 반복문을 선언한다. 첫 티켓은 출발지가 ICN인 모든 티켓으로 설정한다. 그리고 이 티켓이 처음 사용될 때마다 모든 경우의 수를 찾는 재귀함수를 시작한다.
한번의 재귀함수에 사용할 결과 배열을 생성해주고, 티켓의 사용 여부를 체크해줄 boolean 배열도 생성해줍니다. 한번 사용한 티켓은 다시 사용하면 안되기 때문에 상태값을 설정해주는 용도이다.
첫 번째 티켓 정보를 result 배열에 넣어준 뒤 사용 처리를 하고 재귀함수를 호출해줍니다. 티켓을 사용해 모든 경우의 수를 탐색한 뒤, 다른 "ICN" 티켓을 사용하는 경우로 넘어가기 전에 다시 티켓 사용여부를 false로 바꿔줘야 하는 점에 주의해야 합니다. 재귀함수를 이용한 DFS에 가장 흔하게 사용되는 방법입니다. 자신이 있을 경우와 없을 경우를 모두 탐색하는 것이죠.
이제 DFS를 수행할 재귀함수를 작성할 차례입니다. 티켓을 타고 들어가는 재귀함수이므로 더 이상 타고 갈 티켓이 없으면 자동으로 리턴되기 때문에 탈출문이 따로 필요 없습니다. 대신 모든 티켓을 다 사용해 결과 배열을 가득 채운 경우라면 결과 리스트에 추가해줘야하기 때문에 일단 이 부분을 먼저 작성해줍니다.
result 배열의 인덱스가 length와 동일해졌다는 것은 인덱스를 벗어난 상태라는 것이므로 더 이상의 배열 작업은 하지 않고 리턴시켜주면 됩니다. 리턴 시키기 전에 결과 리스트에 최종 배열을 담아줘야 하는데, 여기서 주의할 점은 매개변수로 받은 result 배열을 바로 담아주면 안된다는 것입니다.
객체는 메모리 주소를 담고 있는 참조변수이기 때문에 새로 new을 사용해 만들어주지 않는 이상 딱 하나밖에 없습니다. C언어의 포인터와 동일한 개념입니다. 따라서 그냥 result 배열을 담았을 경우 앞으로 수행되는 다른 재귀함수에서 계속 내용을 바꾸게 되기 때문에 새로운 배열을 하나 생성해 복사해둔 뒤에 리스트에 붙여줘야 합니다.
재귀함수의 나머지 부분은 처음 재귀함수를 호출했을 때와 유사합니다. 이전 티켓의 도착지 정보를 매개변수로 받았으므로 반복문으로 도착지와 동일한 출발지를 가진 티켓을 검색해 도착지를 결과배열에 담아주고 다시 재귀함수를 호출합니다.
위와 동일하게 티켓을 사용했을 때의 모든 경우의 수를 탐색한 뒤에는 다시 티켓 사용 여부를 false로 바꿔줘서 다른 경우의 수에서 해당 티켓을 사용할 수 있도록 만들어줘야 합니다.
모든 경우의 수를 다 찾았고, 리스트에 모든 결과 배열이 담겼습니다. 문제에서는 결과가 여러개일 경우 알파벳 순으로 가장 작은 경우를 제출하라고 했으므로 배열 객체들을 오름차순으로 정렬해주면 됩니다."
package pojoPrj;
import java.util.ArrayList;
import java.util.List;
class Solution {
List<String[]> resultList;
public String[] solution(String[][] tickets) {
resultList = new ArrayList<>();
String[] result = new String[tickets.length + 1];
boolean[] used = new boolean[tickets.length + 1];
for (int i = 0; i < tickets.length; i++) {
// 최초 출발지는 ICN
if (tickets[i][0].equals("ICN")) {
// 첫번째 티켓 정보는 미리 담아두고 재귀 함수 호출
result[0] = tickets[i][0];
result[1] = tickets[i][1];
// 재귀함수 호출
// 해당 티켓을 사용한 경우와 사용하지 않았을 경우를 모두 체크해줘야 함
used[i] = true;
dfs(tickets, used, 2, tickets[i][1], result);
used[i] = false;
}
}
// 배열 오름차순 정렬
resultList.sort((o1, o2) -> {
for (int i = 0; i < o1.length; i++) {
if (o1[i].compareTo(o2[i]) > 0) {
return 1;
} else if (o1[i].compareTo(o2[i]) < 0) {
return -1;
}
}
return 0;
});
// 오름차순 정렬된 배열의 첫번 째 리턴
return resultList.get(0);
}
private void dfs(String[][] tickets, boolean[] used, int resultIdx, String pre,
String[] result) {
// 모든 티켓을 다 썼을 경우
if (resultIdx == result.length) {
String[] temp = new String[result.length];
for (int i = 0; i < result.length; i++) {
temp[i] = result[i];
}
resultList.add(temp);
return;
}
for (int i = 0; i < tickets.length; i++) {
// 이전 티켓의 목적지와 현재 티켓의 출발지가 같다면
if (!used[i] && tickets[i][0].equals(pre)) {
result[resultIdx] = tickets[i][1]; // 도착지 입력
// 재귀함수 호출
used[i] = true; // 티켓 사용
dfs(tickets, used, resultIdx + 1, tickets[i][1], result);
used[i] = false; // 티켓 미사용
}
}
}<참고한 Java 코드 ( codevang.tistory.com/306 )>
function solution(tickets) {
var answer = [];
return answer;
}<프로그래머스의 주어진 solution.js>
# 잡설
프로그래머스 1단계 문제만 풀다가 이걸 풀려고 보니까 굉장히 어렵게 느껴졌다. dfs를 써야한다는 것만 알고 계속 고민했는데 알고보니 3단계 문제였다.. 2단계를 건너뛰고 하는 거였고 자괴감에서 조금은 벗어날 수 있었지만 얼마나 뒤쳐져있었는지도 깨닫게 되었다.
solution.js에서 제시한 틀은 위와 같았는데, 풀이들을 보면 solution 함수에 파라미터를 넣어서 정답을 리턴해주면 되는 거였다.
위의 자바 코드를 보면서 자바스크립트로 구현해보았는데 코드는 아래와 같았다.
이 문제에서 DFS, sort, backtraking이라는 키워드가 관련 있었다. DFS부터 복습하기 시작했다.
# 코드
// 테스트 케이스
// const tickets = [
// ["ICN", "JFK"],
// ["HND", "IAD"],
// ["JFK", "HND"],
// ];
const tickets = [
["ICN", "SFO"],
["ICN", "ATL"],
["SFO", "ATL"],
["ATL", "ICN"],
["ATL", "SFO"],
];
var answer = []; // resultList
function solution(tickets) {
// 2차원 배열 tickets
// var answer = []; // resultList
var result = new Array(tickets.length + 1);
var used = new Array(tickets.length + 1);
for (var i = 0; i < tickets.length; i++) {
// 최초 출발지는 ICN
if (tickets[i][0] === "ICN") {
// 최초 출발지마다 재귀함수 호출 수행
// 첫 번째 티켓 정보는 미리 담아두고 재귀함수 호출
result[0] = tickets[i][0];
result[1] = tickets[i][1];
// 재귀함수 호출
// 해당 티켓을 사용한 경우와 사용하지 않았을 경우를 모두 체크해줘야 함
used[i] = true;
dfs(tickets, used, 2, tickets[i][1], result);
used[i] = false;
}
}
// 배열 오름차순 정렬
answer.sort(function (o1, o2) {
for (var i = 0; i < o1.length; i++) {
if (o1[i].localeCompare(o2[i]) > 0) {
return 1;
} else if (o1[i].localeCompare(o2[i]) < 0) {
return -1;
}
}
return 0;
});
// 오름차순 정렬된 배열의 첫번 째 리턴
console.log(answer[0]);
return answer[0];
// return answer;
}
function dfs(tickets, used, resultIdx, pre, result) {
// 모든 티켓을 다 썼을 경우
if (resultIdx === result.length) {
var tmp = new Array(result.length);
for (var i = 0; i < result.length; i++) {
tmp[i] = result[i];
} // tmp = result.slice(); // 얕은 복사
answer.push(tmp);
return;
}
for (var i = 0; i < tickets.length; i++) {
// 이전 티켓의 목적지와 현재 티켓의 출발지가 같으면
if (!used[i] && tickets[i][0] === pre) {
result[resultIdx] = tickets[i][1]; // 도착지 입력
// 재귀함수 호출
used[i] = true; // 티켓 사용
dfs(tickets, used, resultIdx + 1, tickets[i][1], result);
used[i] = false; // 티켓 미사용
}
}
}
// 코드 실행
solution(tickets);
# 이해하기 어려웠던 것들
result 배열의 사이즈를 2차원 배열 tickets의 length + 1로 주었는데 테스크케이스를 보면 length가 5이므로 5+1=6이 된다. 여기까지는 쉽게 이해가 된다. dfs문으로 들어가보자.
dfs는 재귀적으로 호출된다. 파라미터로 티켓 배열 tickets, 사용 배열 used, result의 도착지를 입력할 인덱스(resultIdx, resultIdx +1,,,), tickets[i][1]는 pre, 그리고 결과 배열 result를 받는다.
여기서 pre이 무슨 역할을 하는지 이해가 안됐다. 처음에 출발지를 ICN으로 두고 tickets[i][1](tickets[0][1])을 pre로 보냈다. 이것은 ICN을 출발지로 가진 티켓의 목적지이다. 이 목적지는 왜 dfs에 보내줘야 할까?
dfs함수에서 pre가 어떻게 쓰이는지 보았다.
아래 for 문을 보면
for (var i = 0; i < tickets.length; i++) {
// 이전 티켓의 목적지와 현재 티켓의 출발지가 같으면
if (!used[i] && tickets[i][0] === pre) {
result[resultIdx] = tickets[i][1]; // 도착지 입력
// 재귀함수 호출
used[i] = true; // 티켓 사용
dfs(tickets, used, resultIdx + 1, tickets[i][1], result);
used[i] = false; // 티켓 미사용
}
}
i = 0 : if문의 조건이 used[0]이 false이고 tickets[i][0](tickets[0][0])가 pre(tickets[0][1] : JFK - 고정!)와 같을 때 조건문을 실행한다.
근데 이미 used[0]을 dfs문을 실행하기 전에 true로 주었기 때문에 조건문은 작동하지 않는다.(SKIP)
i = 1 : used[1]이 false이고 tickets[1][0](테스트케이스 1 - HND)이 pre(tickets[0][1] : JFK - 고정!)와 같을 때 조건문을 실행한다. 다르니까 SKIP.
i = 2 : used[2]이 false이고 tickets[2][0](테스트케이스 2 - JFK)이 pre(JFK)와 같을 때 조건문을 실행한다. 실행되었다.
result[resultIdx] = tickets[i][1] result는 아까 ICN과 JFK를 받은 배열이다. resultIdx는 2를 넣었으므로 그 다음 인덱스에 tickets[2][1](HND)를 넣는다.
이제 used[2]를 true로 바꿔주고 다시 dfs문으로 들어간다. 여기서 다른 점은 resultIdx(현재 2)+1=3로 바뀌었다. result 배열에 한개를 추가해줬으니 다음 인덱스는 1칸 뒤로 밀리는 것이다. pre는 tickets[2][1](HND)
pre(ICN을 출발지로 하는 티켓의 목적지)는 다음 티켓의 출발지와 비교해서 같으면 그 티켓의 목적지를 result에 넣어 티켓들을 연결해준다!
다시 dfs문으로 들어가보자.
if문은 result 배열의 length가 4니까 resultIdx가 3이라서 실행되지 않는다.
for문을 실행해본다. used[0]은 true인 상태였고 방금 들어오기 전에 used[2]도 true로 만들고 들어왔다. 그러니까 i=0과 i=2는 계산 안한다.
i = 1 : used[1] === false고 tickets[1][0](HND) === pre(HND)이니까 조건문이 실행된다.
result[resultIdx] = tickets[i][1] 위 코드를 실행하면 result 배열의 다음 인덱스에 tickets[1][1](IAD)이 들어갈 것이다.
여기까지 console.log로 출력해보면 아래와 같았다.
여기서 다음 라인은 다시 used[1]을 true로 바꿔주고 dfs문으로 들어가는 일이다. resultIdx는 4가 되고(result 배열이 꽉 찼고), tickets[1][1](IAD)를 넘겨준다. 어차피 작동은 안한다. if문으로 가자.
// 모든 티켓을 다 썼을 경우
if (resultIdx === result.length) {
var tmp = new Array(result.length);
for (var i = 0; i < result.length; i++) {
tmp[i] = result[i];
}
answer.push(tmp);
return;
}resultIdx(4) === result.length(4)이므로 조건문이 실행된다.
tmp는 result 크기만큼의 배열로 선언한다.
for문은 result의 크기만큼 반복되면서 tmp[0]=result[0](ICN), tmp[1]=result[1](JFK), tmp[2]=result[2](HND), tmp[3]=result[3](IAD)
이렇게 tmp에 result를 그대로 복사해주는 이유는 뭘까?
"result 배열의 인덱스가 length와 동일해졌다는 것은 인덱스를 벗어난 상태라는 것이므로 더 이상의 배열 작업은 하지 않고 리턴시켜주면 됩니다. 리턴 시키기 전에 결과 리스트에 최종 배열을 담아줘야 하는데, 여기서 주의할 점은 매개변수로 받은 result 배열을 바로 담아주면 안된다는 것입니다.
객체는 메모리 주소를 담고 있는 참조변수이기 때문에 새로 new을 사용해 만들어주지 않는 이상 딱 하나밖에 없습니다. C언어의 포인터와 동일한 개념입니다. 따라서 그냥 result 배열을 담았을 경우 앞으로 수행되는 다른 재귀함수에서 계속 내용을 바꾸게 되기 때문에 새로운 배열을 하나 생성해 복사해둔 뒤에 리스트에 붙여줘야 합니다."
=> 우리는 아직 for문의 첫번째 출발지가 ICN인 티켓을 DFS로 탐색한 것이다. 다시 돌아가면 만약 다른 티켓에 출발지가 ICN인 것이 있으면 다시 DFS를 수행하면서 result 배열을 수정하게 된다.(테스트케이스 1은 ICN 티켓이 하나뿐) 따라서 tmp로 복사한 다음 이 tmp를 리스트에 붙여준다.
테스트케이스 1은 ICN 티켓이 하나뿐이다. 테스트케이스 2를 확인해본다. 출발지 ICN인 티켓이 2개다.
const tickets = [
["ICN", "SFO"],
["ICN", "ATL"],
["SFO", "ATL"],
["ATL", "ICN"],
["ATL", "SFO"],
];먼저, ticket[0]의 티켓이 ICN을 출발지로 하므로 아래와 같은 출력이 나타난다.
solution의 for문 첫 if문에서 result 배열에 2개 들어간다음 resultIdx = 2, pre = SFO로 들어갈 것이다.
그럼 dfs함수에서는 앞서 알아본 것처럼 SFO가 출발지인 티켓을 찾아낸다. tickets[2](SFO, ATL)에 있다. 여기서 result 배열에는 ATL이 추가되고 used = true와 함께 dfs함수를 실행한다. pre는 ATL
다시 dfs의 for문에서 ATL이 출발지인 티켓을 골라낸다. tickets[3](ATL, ICN)와 ticket[4](ATL, SFO) 2개인데, 여기서는 tickets[3]부터 들어가서 깊이 우선으로 탐색하게 된다. 따라서 result 배열에 ICN이 들어간다. pre는 ICN으로 dfs 실행
dfs의 for문에서 pre와 출발지가 같은 tickets[1](ICN, ATL)이 있으므로 result에 ATL을 추가한다. 이제 tickets[1]도 used[1]이 true가 되었다. 남은 건 tickets[4], used[4]뿐이다. pre는 ATL로 해서 dfs함수를 실행한다.
dfs의 for문에서 SFO까지 result에 넣어주고 dfs를 실행하면 if문에 의해서 tmp로 result 배열을 복사하여 answer에 붙여준다.
테스트케이스 2는 출발지가 ICN인 티켓이 하나 더 있다.
따라서 solution의 for문 i=1일 때의 경우를 알아보자.
result 배열에는 ICN, ATL이 들어간다. 그리고 pre는 ATL이 보내진다.
... 과정을 거쳐서 [ ICN, ATL, ICN, SFO, ATL, SFO ]가 된다. result가 꽉 차면 answer에 붙여진다음 return;되면서 dfs를 되돌아올라간다.
그럼 ATL -> ICN을 끝냈으니 다시 ATL -> SFO를 가야한다. 이것은 tickets[4]이다. 우선 dfs를 끝내고 오면서 지금까지 사용한 티켓들의 used배열이 전부 false로 초기화되고 ATL -> ICN도 마찬가지다. 이제 다시 사용할 수 있다.
다시 for문이 돌아가므로 i가 4가 되고 tickets[4](ATL, SFO)부터 for문을 순회하고 나면 [ 'ICN', 'ATL', 'SFO', 'ATL', 'ICN', 'SFO' ]
이 과정은 아래와 같다.
마지막으로 return 배열들을 전부 붙여 넣은 answer 배열을 sort 함수를 사용해서 오름차순 정렬한다음 리턴을 한다. 이 부분도 이해가 필요했다. db로 orderby만 사용했었는데 js에서 sort함수를 사용하는 것이 처음이기 때문이다.
// 배열 오름차순 정렬
answer.sort(function (o1, o2) {
for (let i = 0; i < o1.length; i++) {
if (o1[i].localeCompare(o2[i]) > 0) {
return 1;
} else if (o1[i].localeCompare(o2[i]) < 0) {
return -1;
}
}
return 0;
});
// 오름차순 정렬된 배열의 첫 번째 리턴
console.log("리턴 전체", answer);
console.log("리턴", answer[0]);
return answer[0];solution 함수 내의 sort 함수를 활용한 부분이다.
sort 함수에 대한 내용은 javacript 카테고리에 정리해야겠다.
js mdn을 보면 sort 함수의 인수로 compareFunction에 대해 설명해주고 있다.
compareFunction이 제공되면 배열 요소는 compare 함수의 반환 값에 따라 정렬됩니다. a와 b가 비교되는 두 요소라면,
- compareFunction(a, b)이 0보다 작은 경우 a를 b보다 낮은 색인으로 정렬합니다. 즉, a가 먼저옵니다.
- compareFunction(a, b)이 0을 반환하면 a와 b를 서로에 대해 변경하지 않고 모든 다른 요소에 대해 정렬합니다. 참고 : ECMAscript 표준은 이러한 동작을 보장하지 않으므로 모든 브라우저(예 : Mozilla 버전은 적어도 2003 년 이후 버전 임)가 이를 존중하지는 않습니다.
- compareFunction(a, b)이 0보다 큰 경우, b를 a보다 낮은 인덱스로 소트합니다. (b가 먼저)
- compareFunction(a, b)은 요소 a와 b의 특정 쌍이 두 개의 인수로 주어질 때 항상 동일한 값을 반환해야합니다. 일치하지 않는 결과가 반환되면 정렬 순서는 정의되지 않습니다.
따라서 compareFunction의 return 값이 -1이면 a가 먼저 오게 되고, 1이 되면 b가 먼저 오게 될 것이다.
여기에는 localeCompare함수를 함께 사용했다.
이 함수는 비교했을 때 사전 순으로 있으면 음수 값을 반환하고, 반대의 경우 양수 값을 반환한다. 따라서 아래의 함수와 같다.
function strcmp(a, b) {
if(a === b) {
return 0;
}
if (a > b) {
return 1;
}
return -1;
}
직접 과정을 출력해보았다.
가장 중요한 것은 o1, o2가 다르다는 것이다. 거꾸로 할당되어 있다!
여기서 o1이 먼저 오게 만드는 return -1을 만나면 순서가 서로 바뀌게 된다!
위의 strcmp함수를 보면 a가 b보다 작았을 때 return -1이였는데 여기서는 a=o1, b=o2이므로 o1이 o2보다 작았을 때 return -1이 되는 것이다. 그렇다면 당연히 o1은 상대적으로 앞쪽으로 이동해야 할 것이다.
코드에서 이것을 판단하기 위해서 아래와 같이 출력문을 넣었다.
answer.sort(function (o1, o2) {
for (let i = 0; i < o1.length; i++) {
console.log("1", o1);
console.log("2", o2);
if (o1[i].localeCompare(o2[i]) > 0) {
console.log("사전반대", o1[i]);
console.log("사전반대", o2[i]);
return 1; // o2가 먼저 오게 한다. 원래 앞에 위치함.
} else if (o1[i].localeCompare(o2[i]) < 0) {
console.log("사전순", o1[i]);
console.log("사전순", o2[i]);
return -1; // o1이 먼저 오게 한다. 순서가 뒤집힌다? 여기서 o1은 [ 'ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO' ]
}
}
return 0;
});사전순이라고 나오는 if문에서 o1과 o2의 순서 변경이 필요하다는 것을 알 수 있다. (사전순이라는 말이 이상한데 사전순으로 바꿔야하는 상황이라고 보면 된다.)
사전순으로 출력되는 쌍이 2번 있다.
순서는 이렇게 변경된다.
정렬 전 리턴 전체 [
[ 'ICN', 'SFO', 'ATL', 'ICN', 'ATL', 'SFO' ], // o2
[ 'ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO' ], // o1
[ 'ICN', 'ATL', 'SFO', 'ATL', 'ICN', 'SFO' ]
]0번 인덱스(o2)와 1번 인덱스(o1)에서 사전순이 나타났다. 변경해보자.
[
[ 'ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO' ], // o2
[ 'ICN', 'SFO', 'ATL', 'ICN', 'ATL', 'SFO' ],
[ 'ICN', 'ATL', 'SFO', 'ATL', 'ICN', 'SFO' ] // o1
]자 여기에서 0번 인덱스는 바뀌지만 이 인덱스는 o2이다. 2번 인덱스(o1)와 비교하여 사전반대가 나오므로 변화없다.
[
[ 'ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO' ],
[ 'ICN', 'SFO', 'ATL', 'ICN', 'ATL', 'SFO' ], // o2
[ 'ICN', 'ATL', 'SFO', 'ATL', 'ICN', 'SFO' ] // o1
]이제 다음 순서는 1번 인덱스(o2)와 2번 인덱스(o1)를 비교한다. 사전순이 나왔다. 순서를 변경해본다.
[
[ 'ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO' ],
[ 'ICN', 'ATL', 'SFO', 'ATL', 'ICN', 'SFO' ],
[ 'ICN', 'SFO', 'ATL', 'ICN', 'ATL', 'SFO' ]
]다 돌았다. 이게 답이다. 아래에서 정렬된 배열의 첫 번째를 리턴한다.
return answer[0];코드를 하나하나 뜯어 보았는데 굉장한 시간이 흘렀다. 앞으로 sort 함수는 그냥 쓰도록 하자.
(궁금해서 찾아봤는데 Mozilla / Firefox의 경우 Array.sort ()가 mergesort를 사용한다고 한다. -stackoverflow)
'Algorithm > ProblemSolving' 카테고리의 다른 글
| [CodingTest]프로그래머스 파일명 정렬 (0) | 2020.12.28 |
|---|
댓글