Remove Invalid Parentheses 문제 내용 '(' 와 ')' 로 구성된 문자열이 있다. 해당 문자열을 중괄호라고 부를때 '(' 와 ')'의 pair가 맞게 할 수 있는 최소한의 delete가 된 가능한 모든 문자열을 결과로 return 해라 단, 중간에 문자가 있을 수 있다. 접근 방법 일반적인 Parentheses 문제를 이용해서 문제를 해결해 나가야 한다. 우선 validation check에 대해서 생각해 보자. 기본적으로 Parentheses 문제는 '('의 갯수가 무조건 ')'의 갯수보다 많은 경우 Validation이 된다고 생각해야한다. 2020.09.15 - [Problem Solving] - 괄호 변환 문제에서 getBalancedCount 부분을 참고하자. 이 내용을 기..

Regular Expression Matching 문제 내용 s와 p라는 문자열이 주어진다. p는 일반 영문자와 아래 2개의 char로 구성될 수 있다. `.` : 단 한개의 모든 char 종류와 동일하다 `*` : * 직전에 오는 char가 0개 이상 존재 할 수 있다. s와 p가 동일한 문자열이 가능한지 비교하라 접근 방법 가장 쉬운 방법 부터 생각을 해보자 `*` wildcard가 없는 경우를 생각하자. 단순히 왼쪽에서 오른쪽으로 s와 p의 index를 하나씩 움직여 가면서 모든 문자열이 동일한지 확인 하고 만약에 동일하지 않은 것이 나오면 false를 return 하면된다. 주의 해야할 것은 `.`이 모든 문자열을 대치 할 수 있다는 것이다. 그러면 wildcard가 들어간다고 생각해 보자. 이 ..

Word Search II 문제 내용 주어진 m x n 문자 배열이 있고, Dictionary가 주어진다면 해당 문자배열에서 조합가능한 모든 Dictionary내 words를 찾아라. 접근 방법 이런 board가 주어 졌다고 생각해 보자 가장 쉬운 접근 방법은 하나씩 조회해 보는 것일것 같다. 가령 'o'가 있이니까 Dictionary내에서 'o'가 있는 모든 words를 1회 search한다. 그리고 다음으로 a또는 e로 이동한다. 다시 앞서 조회된 o의 words에서 a또는 e가 있는 words를 찾는다. 이렇게 찾다가 words의 마지막 char와 board의 char가 동일해지는 순간 결과 값으로 등록 하면 된다. 그리고 다시 (0,1)인 'a'부터 다시 조회를 시작하면 된다. 이 방법을 최악의 ..

Sudoku Solver 문제 내용 수도쿠에 빈 칸을 모두 채우시오 접근 방법 full search를 제외하고 해결 방법은 없다. 가장 쉬운 방법은 모든칸에 모든 값을 대입하는 방법이다. row 9개 col 9개의 cell로 구성된 board가 수도쿠 임으로 모든 cell은 81칸으로 이루어져 있다. 각 cell은 1부터 9까지 9개의 값을 갖을 수 있다. 이런칸이 81칸임으로 $$ 9^{81} $$ 이 된다. 이것을 약간 최적화 해보자면 다음과 같이 바꿀수 있다. - 앞서 선택된 값을 선택하지 않는다. 예를 들자면 9개의 네모칸이 있다고 생각해 보겠다. 이중 첫번째 네모칸을 1로 선택한다면 뒤에있는 8개의 칸은 2에서 9사이 선택권을 갖는다. 이런방식으로 첫번째 칸은 9가지 선택권을 두번째 칸은 8가지..