바위타는 두루미

문제 연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로 표현할 수 있다. 각 숫자는 역순으로 배열되어 있는데, 즉 첫번째 자릿수가 리스트의 맨 앞에 위치하도록 배열된다는 뜻이다. 이와같은 방식으로 표현된 숫자 두 개가 있을 때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 함수를 작성하라. 예제 입력 (7->1->6) +(5-> 9-> 2) 출력 ( 2->1-> 9) => 617 + 295 = 912 연관문제 각 자릿수가 정상적으로 배열된다고 가정하고 같은 문제를 풀어보자 예제 입력 (6->1->7) +( 2->9->5) 출력 ( 9->1->2) => 617 + 295 = 912 해결법 기본 문제는 우리가 덧셈을 하듯이 더한 숫자의 1의 자리 숫자로 노드를 만들고 캐리를 넘김..

문제 값 x가 주어졌을때 x보다 작은 노드들을 x보다 크거나 같은 노드들 보다 앞에 오도록 하는 코드를 작성하라. 만약 x가 리스트에 있다면 x는 그보다 작은 원소들보다 뒤에 나오기만 하면 된다. 즉 원소x는 오른쪽 그룹 어딘가에 존재하기만 하면 된다. 왼쪽과 오른쪽 그룹 사이에 있을 필요는 없다. 예제 입력 : 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1 출력 : 3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8 해결법 1. x보다 작은 linked list , x보다 크거나 같은 linked list 를 구성하여 마지막에 연결하기 def Solution(node): small_head, small_tail = None, None large_head, large_tail = No..

문제 단방향 연결리스트가 주어졌을때 뒤에서 k번째 원소를 찾는 알고리즘을 구하여라 해법 1 연결리스트의 길이를 아는경우 -> 길이 - k번째 원소 찾기 해법 2 재귀적으로 해결하기 마지막 원소를 만나면 0으로 설정된 카운터 값을 반환하고, 재귀적으로 호출된 부모 매서드는 그값에 1을 더한다. 카운터 값이 k가 되는 순간 뒤에서 K번째 원소에 도달한 것이다. 하지만 문제가 있다. 대부분의 언어에서는 노드와 카운트 값을 동시에 반환할 수 없다. - 1. 반환하는 것이아니라 출력한다고 가정하면 k번째에 도달한 순간 출력하면된다. - 2. call by reference를 이용하여 문제를 해결한다. node* nthToLast(node* head, int k , int& i ){ if(head == NULL) ..

문제 정렬되어 있지 않은 연결 리스트가 주어졌을때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라 [연관문제] 임시 버퍼를 사용할 수 없다면 어떻게 풀까? 해결법 1. 중복되는 원소를 hash table로 추적해 나가며, 중복원소를 제거 class Node: def __init__(self, dataval=None): self.data = dataval self.next = None def Solution(node): data_set = set() prev = None while node is not None: if node.data in data_set: prev.next = node.next else : set.add(node.data) prev = node node = node.next re..

문제 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 ..