바위타는 두루미

문제 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을 넘지 않아야하며, 긴문자열에서 짧은 문자열과 다른 부분을 발견했을때 한번의 인덱스 이동만 허용하고 나머지 글자는 동일한지 확인해보아야한다. - 문자 교체는 두 문자열의 길이가 같..

문제 주어진 문자열이 회문(Palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며 순열이란 문자열을 재배치하는 것을 의미한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다. 예제 입력 : tact coa 출력 : True 접근법 어느 방향으로 읽어도 같은 문자열이 되기 위해서는 모든 문자가 각각 홀수개 이거나, 단 한개의 문자만 홀수 개여야한다. 방법 1 hash table을 이용하여 각 문자가 몇번 등장했는지 세고, 홀수의 갯수를 확인하기 방법 2 문자열을 읽어나가면서 홀수의 갯수를 세기 def Solution(phrase): alpha_cnt = [0]*26 odd_cnt = 0 for alpha in phrase..

문제 문자열에 들어있는 모든 공백을 '%20'으로 바꾸어 주는 메서드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종 길이가 함께 주어진다고 가정해도 된다. 입력 : 'Mr John Smith',13 출력 : 'Mr%20John%20Smith' 해결법 입력문자열을 한번 읽어서 공백의 갯수를 확인 한 후에, (공백갯수 *3 + 전체 문자열의 길이)를 새로운 문자열의 길이로 생각하고 그 위치부터 원래 문자열의 가장 끝부분부터 읽어나가며 복사하여 새로운 문자열을 구성한다. 뒤에서부터 읽어서 문자인 경우에는 그대로 복사하고 공백인 경우에는 '%20'을 복사하며 문자열을 만들어나가면 된다. 뒤에서 부터 조작하는 이유는 덮어쓰여질 걱정 하지 않고 문자들을..

문제 문자열 두개가 주어졌을때 이 둘이 서로 순열관계야 있는지 확인하는 메서드를 작성하라 1. 정렬하기 두 문자열이 순열관계라면 문자를 정렬한다음 비교해봤을때 같은 문자열이여야한다. def Solution(s1, s2): if len(s1) != len(s2): return False s1.sort() s2.sort() return s1 == s2 Time Complexity O(NlogN + N) 2. 문자열에 포함된 문자의 출연 횟수가 같은지 검사하기 - Ascii코드라면 128개의 문자들에 대한 배열을 선언하고 각 문자들의 갯수를 세서 비교한다. def Solution(s1,s2): if len(s1) != len(s2): return False alpha_cnt = [0]*128 for c in ..

문제 문자열이 주어졌을때 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라. 해결방법 1. Hash를 이용하여 해결하기 def solution(word): alpha_dict = {} for w in word: if alpha_dict.get(w, 0) >0 : return False alpha_dict[w] = 1 return True hash라는 자료구조를 이용하여 해결하면 Time Complexity = O(N) Space Complexity = O(N) 2. 비트벡터를 이용해 해결하기 def solution(word): alcheck = 0 for w in word: if alcheck & (1