바위타는 두루미

문제 MXN행렬의 한원소가 0인경으 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라 접근법 행렬을 순회해 나가면서 0인 셀을 발견하면 그 셀이 속한 행과 열을 모두 0으로 바꾸는 방식을 취한다면 0으로 바뀐 행이나 열의 또다른 셀을 나중에 방문하면 그 셀이 속한 행과 열도 모두0으로 바뀌는 문제가 발생한다. 따라서 0인 셀의 위치를 저장해두고 이후에 탐색 후 해당 행과 열을 변경해주어야 할 것이다. 1. 0의 위치를 기록할 행렬 하나를 더둔다 -> Space Complexity O( MN) 2. 바뀔 행과 열만 체크한다 -> Space Complexity(M+N) 3. 행렬의 0번째 행과 열에 바뀌어야 하는지의 여부를 체크한다. -> Space Complexity 0(1) -..

문제 반복되는 문자의 개수를 세는 방식의 기본적인 문자열 압축 메서드를 작성하라. 예를 들어 문자열 aabccccaaa를 압축하면 a2b1c4a3이 된다. 만약 '압축된' 문자열의 길이가 기존 문자열의 길이보다 길다면 기존 문자열을 반환해야한다. 문자열은 대소문자 알파벳 (a-z)로만 구성되어있다. 접근법 1. 직관적으로 문자열의 갯수를 세어나가고 현재 문자와 다음 문자과 다를때 현재문자 + 갯수를 문자열에 붙여주면 될 것같다. def Solution(phrase): len_phrase = len(phrase) char_cnt = 0 res = "" for i in range(len_phrase) : char_cnt +=1 if phrase[i] != phrase[i+1]: res += phrase[i]..

문제 문자열을 편집하는 방법에는 세가지가 있다. 문자 삽입, 문자 삭제, 문자 교체. 문자열 두개가 주어졌을때 문자열을 같게 만들기 위한 편집횟수가 1회 이내인지 확인하는 함수를 만들어라. 예제 pale,ple ->true pales,pale ->true pale,bale ->true pale,bake ->false 접근법 1. 모든 문자열 편집 가능 수를 구해서 비교한다 -> 절대안돼 time Complexity 너무 커져 2. 문자 삽입, 삭제, 교체의 특징을 확인하여 구현 - 문자 삽입과 삭제는 두 문자열의 길이차이가 1을 넘지 않아야하며, 긴문자열에서 짧은 문자열과 다른 부분을 발견했을때 한번의 인덱스 이동만 허용하고 나머지 글자는 동일한지 확인해보아야한다. - 문자 교체는 두 문자열의 길이가 같..