두번째 알고리즘 스터디
오늘은 처음 내배캠 안에서 대대적인 전수참여 알고리즘 스터디가 있었다. 다른 챌린지 반 분들과 함께 팀을 이루어 각자 정해온 문제를 풀었고 나만 못 풀었다. ... ... ..
사실 이번 알고리즘 스터디 이전에도 전에 속했던 팀에서 팀 내부적으로 알고리즘 스터디를 진행했었는데, 때마침 팀프로젝트가 나오고 각자 할 일이 막 불어나면서 유야무야되었었다. 개인적으로는 상당히 반가웠는데, 지난번 팀에서 알고리즘 스터디를 할 때 문제를 보다 폭넓게 보게 되고 내 것이 아닌 풀이를 보면서 배우는 것도 상당히 많았기 때문이다. 오늘의 스터디에서도 배운 점이 있었는데, 그걸 중심으로 한 번 이야기해볼까 한다.
삼총사
오늘 내가 가져간 문제는 삼총사 라는 문제였는데, 상당히 재미있는골아픈 문제였다.
이런 문제인데, 만만해보이지 않아서 골랐는데 이정도일줄은 몰랐다... 물론 프로그래머스에는 난이도 1 로 설정되어있는 문제고, 내 수준에서나 어려운 문제이긴 하다.
접근 방법
일단 문제를 쭉 읽었을 때 눈에 들어오는 부분이 있었다. 다음과 같다.
- '방법의 수'
- 서로 다른 학생의 정수 번호가 같을 수 있다.
흠.. 방법의 수라 하면 지금도 기본적으로 순열조합이 생각난다. 정확히는 경우의 수가 더 그 쪽이지만.. 말투만 조금 바꿔
전체 학생 중 세 명을 뽑았을 때, 각 학생의 번호를 더해 0이 나오는 경우의 수는?
이렇게 하면 확 수학문제같아진다. 암튼.. 그게 중요한 게 아니고.. 내가 느꼈던 건, 일단 순열조합 문제는 모든 경우의 수 중에서 조건에 만족하는 경우만 골라내는 방법이다. 이 문제도 그렇지 않을까 싶었다.
기본적으로 다른 복잡한 메소드 체이닝을 통해서 가진 데이터를 이리 굴리고 저리 만지는 게 아닌, 모든 데이터를 살펴봐야 하는 문제
라고 느꼈다. 이렇게 써 놓고 보면 당연하다고 느낄 수도 있겠지만 문제를 처음 만났을 때 내 머릿속에 든 생각은
1. 세 명을 어떻게 뽑지? 방법의 수? 방법의 수를 어떻게 찾더라?
2. 전체 학생의 번호를 다 더해놓고 한 명씩 빼가면서 0이 될 때를 볼까?
3. 필터? 리듀스? 맵?
4. 이게 난이도 1이라고?
이런 것들이었다. 하나도 정리가 안 되고 허우적대고만 있는 꼴이다.
아아, 이거는 배열의 모든 원소를 순회하며 조건과 대조해봐야 하는 문제이구나.
사실 저렇게 허우적대지 않고 위 같이 생각만 할 수 있어도 지금처럼 헤매지는 않았을 것 같다. 저기까지 생각이 미치고 나면 이 문제에서 고민할 만 한 건 어떻게 하면 배열의 원소를 참조하는 세 개의 변수가 서로 겹치지 않게, 즉 같은 원소를 참조하지 않도록 할 것인가? 정도만 남는다.
기본적으로 배열을 순회하는 변수를 이용하려면 반복문을 사용해야 하고, 이 문제의 경우 그런 제각기 다른 변수가 세 개 이므로 삼중 배열을 사용해야 각각의 변수를 순회하도록 할 수 있다. 그리고 바로 위에서 말한 변수가 겹치지 않게 하는 것은 각 반복문에서 변수가 참조하는 인덱스의 초기값들이 겹칠 수 없게끔, 그러니까 이런 식으로처리를 해주면 될 일이다.
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
for (let k = j + 1; k < n; k++) {
if(number[i] + number[j] + number[k] === 0) answer++;
}
}
}메서드를 알자!
조원 중 한 분이 같은 문제를 두 가지 방법으로 푸신 방법을 공유해주셨다. 두 번째의 풀이를 보니 훨씬 보기에 좋고 이해도 잘 갔다. Array.reduce() 를 이용해 필요한 코드를 대폭 줄이신 거였다. 처음도 그렇고 지금도 메서드를 잘 몰라서 하드코딩으로 풀 떄가 종종 있는데, 잘 모르겠을때마다 정리해둔 메서드를 다시 한 번 봐야겠다.
정리
문제를 읽자 마자 바로 코딩하려 하지 말고 똑바로 보자. 문제 안에 답이 있다.
Links
