[백준] 코딩테스트 문제 풀이 : 2798.블랙잭 #브루투포스#완전탐색

오늘은 알고리즘 문제 풀이를 기록해보려고 한다. 개발 공부를 시작하면서 코딩 테스트 준비와 간간이 토이 프로젝트를 병렬적으로 진행해 왔는데, 아무래도 혼자 공부하다 보니 토이 프로젝트는 생각보다 삽질을 많이 하게 되고 시간도 오래 걸리고… 그렇다. 그러나 토이 프로젝트를 하면서도 배우는 게 많아 다음번 포스팅에서는 카카오 지도 API를 활용한 웹 사이트를 만들면서 익힌 개념인 이벤트 캡쳐링과 버블링을 정리해보고, e.currentTarget과 e.target의 차이를 활용하여 코드를 작성한 부분에 대해서 기록하려고 한다.(복습하는 차원에서!)

오늘은 코딩 테스트를 풀면서 개인적으로 이제는 정말 눈 감고도 풀고 싶은 순열과 조합(완전탐색)을 완전 정복하기 위해 백준 문제를 가져왔다.

사실 JS로 코딩테스트를 준비하면서 프로그래머스로 넘어갔었는데, 프로그래머스보다는 확실히 백준이 문제가 많아 다시 백준으로 돌아가야 하지 않을까라는 생각이 들어 백준에서 오랜만에 문제를 풀었다. 백준에서 JS로 문제를 푸는 일은 조금 까다롭다. 파일 입출력으로 테스트 케이스를 받아서 처리해야 하기 때문에 function 함수를 작성하는 프로그래머스나 해커랭크, 코딜리티와는 input/output 방식이 다르다.

일단 백준에서 입력을 받기 위해서는 readline 모듈 또는 fs 모듈을 사용해야 하는데 fs 모듈이 readline보다 처리 시간이 빠르다고 해서 fs 모듈로 사용해서 문제를 풀었다.

공백을 기준으로 받으면 한 줄에 공백을 나뉘어진 문자열이 배열 요소로 들어가고, 줄바꿈을 기준으로 받으면 한 줄이 하나의 배열 요소가 된다. 각 줄에 대해서 공백을 기준으로 다시 나누고 싶으면 split(“ “)을 해주면 된다.

일단 블랙잭 문제를 먼저 보면, 문제는 굉장히 간단하다. N개의 카드 숫자 중 3개를 선택해 그 총합이 M을 넘지 않으면서 M에 최대 가깝게 만들면 된다. total(3개의 숫자 카드 합) <= M을 만족하는 total 중 Math.max(…total)을 return하면 된다.

(시간 제한 1초, 메모리 제한 128MB)

이건 일단, 카드 순서는 상관 없으니 조합 문제이고 결국 완전 탐색 문제다. 그래서 첫 번째 시도는 늘 하던대로 배열을 만들어 재귀함수를 호출하는 코드를 구현했는데, 메모리를 초과가 뜨는 것이 아니겠는가…!!
🥲 😱 😨 😰

[메모리 초과 코드]

계속해서 rest 배열을 만들고 이를 result에 저장해서 리턴해 다시 answer에 저장하기 때문에 카드 개수가 최대 100개인 점을 감안하면 length가 100C3 = 100 * 33 * 49 = 161700인 2차원 배열이 result, answer 총 2개가 생기기 때문에 메모리 초과가 나는 것으로 보였다. 그래서 배열 size를 줄일 수 있는 다른 알고리즘을 찾아 보았고, 같은 로직이지만 조합을 만들 arr를 매개변수로 주고 전역 배열 변수에 한 번만 저장하는 코드로 다시 구현했더니 통과할 수 있었다.

[1차 통과]

그런데 코드를 가만히 보니, arr이 자리에 sum을 넣고 다 더한 값을 answer에 push하면 나중에 map+reduce 조합을 쓰지 않고 바로 합이 담긴 1차원 배열을 return 받을 수 있어서 메모리 낭비를 줄일 수 있을 것 같았다. 그리고 1차 버전에서는 그냥 완전 탐색으로 배열 내 모든 값을 비교해서 max 값을 출력했는데, 사실 이진 탐색으로 하면 더 빨리 계산할 수 있다.

[2차 통과]

1차 통과보다 코드 수는 살짝 더 길어진 감이 있지만, 메모리 사용과 처리 시간 측면에서 훨씬 향상된 것을 볼 수 있다. 뿌-듯.

다음 번에는 더 빨리 통과하도록! 노력해야지 🔥 👊