Done is better than perfect

Question 중복 원소 없애기 정렬되어 있지 않은 연결 리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라. Solution 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR) 모든 리스트의 요소들을 다 확인해봐야 하기 때문에 리스트의 최대길이를 n이라 했을 때 O(n)이다. 고려사항 리스트 원소의 자료형을 int 타입으로 가정한다. Solution1 (Bruth Force) 가장 간단한 방법이다. 첫 요소부터 순차적으로 탐색하며 같은 원소가 있으면 연결해주는 방식이다. 이 방식은 버퍼를 사용하지 않지만, 공간 복잡도에서 이득이 있다. void solution(ListNode* head) { while(head !=NULL){ ListNode* co..

Question 비트 뒤집기 어떤 정수가 주어졌을 때 여러분은 이 정수의 비트 하나를 0에서 1로 바꿀 수 있다. 이때 1이 연속으로 나올 수 있는 가장 긴 길이를 구하는 코드를 작성하라. ex) input: 1775 ( 11011101111 ) output : 8 제약사항 고려사항 주어진 정수의 자료형 이 무엇인지 ? : int로 가정하고 푼다. Solution 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR) 최소 주어진 정수의 자료형의 가능한 bit수만큼은 탐색해야 한다. Solution1 (Bruth Force) 가장 쉽게 생각할 수 있는 solution은 모든 0에 1을 넣어보고 가장 긴 연속된 1의 개수를 찾는 것이다. 그렇다면 0의 개수만큼 반복해야 하기 때문에 ..

Question COUNT and SAY 시퀀스는 재귀 공식으로 정의된 일련의 숫자 문자열이다. Countandsay (1) = "1" Countandsay (N)는 Countandsay (N-1)의 숫자 문자열을 "말하는"방식으로, 다른 숫자 문자열로 변환된다. 쉽게 말해 Countandsay (n)은 Countandsay (n-1) 을 읽어 반환하는 것인데, 읽는 방식은 아래와 같다. Countandsay (1) = "1" Countandsay (2) = Countandsay (1) 은 1개의 1 = "11" Countandsay (3) = Countandsay (2) 은 2개의 1 = "21" Countandsay (4) = Countandsay (3) 은 1개의 2 , 1개의 1 = "1211" ..

Question 싱글 링크드 리스트의 헤드가 주어지면 홀수번째 노드를 함께 그룹화한 다음 짝수 번째 노드를 그룹화하여 홀수 그룹의 마지막에 짝수 그룹을 연결한 재 정렬된 리스트를 반환하라. 첫 번째 노드는 홀수로 간주되고, 두 번째 노드는 짝수로 간주된다. 짝수 그룹과 홀수 그룹 모두 내부의 상대적인 순서는 입력에서와 같이 유지되어야 한다는 점에 유의한다. O(1) 공간 복잡도와 O(n) 시간 복잡도에서 문제를 풀어야 한다. 제약사항 주어진 리스트의 개수는 최소 0개 최대 10^4개 이다. 노드의 값은 최소 -10^6 최대 10^6이다. Solution 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR) 모든 노들들을 최소 한 번식은 봐야 하기 때문에 O(n)이다. 고려사항 노..

Question 문자열 s가 주어졌을 때, 한 문자가 두 번 이상 등장하지 않는 가장 긴 부분 문자열을 찾아 그 길이를 return 하라. 제약사항 s의 길이는 0 이상 5 * 10^4 이하이다. s는 영문, 숫자 및 심벌과 공백으로 이루어져 있다. Solution 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR) 모든 문자열의 문자들을 최소 한 번식은 봐야 하기 때문에 O(s)이다. 고려사항 제약사 항의 영문 이외의 문자가 들어갈 경우 Solution1 - Brute Force 가장 긴 문자열부터 문자열의 길이를 하나씩 줄여가면서, 중복된 문자가 있는지 판단한다 substr의 길이가 s일 때 1번(s) substr의 길이가 s-1 일때 2번(s-1) substr의 길이가 s..

Question 배열 nums 와 red, white, blue로 이루어진 n개의 객체들이 있을 때, 해당 객체들을 같은 color끼리 인접하게 in-place로 정렬하라. 반드시 sort 라이브러리를 쓰지않고 정렬해야한다. 제약사항 n 은 nums.length() 와 같다 n은 최소 1 ~ 최대 300이다. nums[i] 는 0,1, 2 중 하나이다. Solution 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR) 모든 숫자를 한번 씩 확인해봐야 하기 때문에 n을 배열의 길이라 했을 때, BCR은 O(n) 이다 고려사항 빈 배열일 경우 (제약사항엔 1~300이지만, 고려해본다) Solution1 - Bruth Force 단순한 방법은 그냥 잘 알려진 정렬 라이브러리를 사용..

Question 주어진 Binary Tree를 inorder (중위 순회) 방식으로 탐색하는 문제이다. 자료구조의 Binary Tree의 탐색 부분을 공부할 때 접하게 되는 기본적인 순회 방법 중 하나로 , 재귀적인 방법을 사용하면 간단하게 풀 수 있다. 하지만 문제에서는 iterative방식으로 해결해 볼 것 을 권장하고 있다. 제약사항 노드의 개수는 최소 0개 최대 100개이다 각 노드의 값은 최소 -100 ~ 최대 100이다 Solution 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)) 트리 노드의 개수를 n이라 했을 때 적어도 한번씩은 다 방문해야 하므로 시간 복잡도는 O(n)이다 고려사항 빈 노드가 주어질 때 Solution1 (Recursive) 가장 기본적인..