오늘 한 일
- leetcode
- Combination Sum II. (medium)
- 걷기 운동(산책)
문제 풀이
Combination Sum II. (medium)
주어진 배열의 값들의 합으로 정해진 값을 만족하는 중복되지 않는 조합을 돌려주는 문제.
대부분 어제의 문제와 비슷하나, 배열내의 값을 한번씩만 사용이 가능하다.
그래서 풀이방향을 비슷하게 잡아 조합을 찾을 재귀함수를 만들고, 해당 재귀함수를 수행시켜 결과를 구하는 방식을 취하였다.
재귀함수는 주어진 배열, 타겟값, 선택한 배열 을 입력 값으로 받는다.
주어진 배열을 for문으로 순회하면서 타겟값을 해당 값들로 차감하였을때, 결과가 0이면 선택된 값과 입력된 선택된 배열을 묶어서 하나의 조합으로 정리하고 오름차순으로 정렬하여 객체내에 존재하는지를 확인하고 없다면 새로운 결과로 추가한다.
결과가 양수라면 다음 재귀함수를 수행하는데 선택된 배열과 현재 값을 묶어서 다음 선택된 배열로,
주어진 배열에서 현재 값을 제거하여 다음 주어진 배열로, 타겟값에서 현재 값을 차감하여 다음 타겟값으로 사용한다. 얻어진 결과는 현재 결과에 추가하여 돌려준다.
위방식을 통해 결과를 얻었으나, 일부 예문에서는 결과를 얻는데 소용되는 시간이 너무 길다는 평가를 받았다. 해당부분에서 풀이가 막혀 좀 더 고민해봐야할것 같다.
새로운 재귀함수를 수행하기전에 입력 받은 값들을 객체화하여 해당값의 갯수를 value 값으로 정하였다.
위에서 사용한 방식의 경우 동일한 값이 여러개 있을 경우 불필요한 계산을 수행하게 되는 경우가 있었으나. 풀이를 진행하면서 사용한 방식으로는 해당값의 사용 되는 갯수를 볼것이기에 이전과 같은 방식의 연산을 진행하지 않게 된다.
[10,1,2,7,6,1,5]
=> {'1':2, '2':1, '5':1, '6':1, '7':1, '10':1}재귀함수 에서는 이러한 값들을 요소로 같는 배열, 목표로 하는 값, 조합할 배열을 인자로 받는다.
그리고 배열의 첫 값을 현재 사용 값으로 정하고, 0 부터 해당 값의 존재하는 갯수만큼 반복수행을 하게 한다.
이 경우 값이 값이 1 이고 반복 값이 1이면 1 * 1 한값을 목표값에서 차감하여 결과를 확인한다.
먼저 배열의 길이가 1보다 크고 차감된결과가 0보다 큰경우, 뒷배열의 값으로 넘어가 다시 연산을 수행하게 된다. 재귀함수를 사용하는데 배열을 1부터 slice 한것을 입력하고 참감된 결과를 입력하고 현재 선택한 값과 갯수를 배열화 하여 조합 배열에 포함 시켜 작업을 수행한다. 그리고 수행된 작업의 결과는 결과에 포함시킨다.
다음 조건은 차감된 결과가 0과 일치하는 경우이다. 이 경우 조합에 현재 선택한 값과 갯수를 배열화한것을 포함시키고 결과에 추가한다.
그리고 그렇게 얻어진 결과를 내보낸다.
위 과정을 통해 주어진 예문을 시간 초과 없이 잘 통과하는것을 확인할 수 있었다.
남은 것
클라이언트
현재 상태에서 로그인 창 부분을 재활용하여 로그인 된상태 창을 구현 로그인 결과를 표기하고 로그아웃 버튼구현.실패시에는 실패 문구를 표현하고 로그인창으로 돌아가는 버튼구현.- 로그인 성공, 실패에 따른 결과 부분의 표현을 적용할 것.
서버
- 데이터베이스와의 연결고리 구성
데이터베이스
- 유저 네임, 비번만을 컬럼으로 가지는 유저 테이블 구성
공부 할 것(꾸준히)
오늘은...
회복중
