23.02.21. 풀었던 문제들

리트코드 daily challenge - 540. Single Element in a Sorted Array

 문제 조건이 logn이기 때문에 binary search쪽 알고리즘인 것 같다.에서 시작했다. binary search이기 때문에 절반씩 줄여나가야 할 것 같다. 추가로 문제 조건에서 nums.size()는 홀수이며, 1보다 크거나 같다.

 이어서 base case부터 생각을 했다.

 base case, len == 1인 경우 : 남아있는 element가 답

 base case, len == 3인 경우 : 1개짜리 골라 리턴하면 됨

 

 len == 5인 경우 : 절반으로 나눠야 하기 때문에 2, 3으로 나눈다고 생각해 보자. 그러면 아래와 같은 2가지 경우가 생긴다.

• [1, 2 / 2 / 3, 3]과 같이 가운데 기점으로 왼쪽에 1개짜리 element가 있는 경우
• [2, 2 / 3 / 3, 4]와 같이 가운데 기점으로 오른쪽에 1개짜리 element가 있는 경우

len == 7인 경우 : 마찬가지로 절반으로 나누고, 3, 4로 나눈다고 생각해 보자.

• [2, 2, 3 / 3 / 4, 4, 5]처럼 왼쪽에 1개짜리 element가 있는 경우
• [1, 2, 2 / 3 / 3, 4, 4]처럼 오른쪽에 1개짜리 element가 있는 경우

 개수는 무조건 홀수개인 상황에서, 1개짜리가 들어가있는 쪽을 찾으면 될 것 같다. 이걸 어떻게 찾나... 생각을 거친 후. 탐색하는 범위에서 반으로 나눈 게 홀수개인지, 짝수개인지에 따라 달라진다는 것을 깨달음. 

 

• 가운데가 그 앞 것과 동일 + middle index가 짝수 -> 가운데 뒷쪽거는 버려도 됨 (짝수개의 element 버림) 
  • [x x x] x x
• 가운데가 그 앞 것과 동일 + middle index가 홀수 -> 가운데 뒷쪽거 신경써야 함 (짝수개의 element 버림)
  • x x x x [x x x]
• 가운데가 그 뒷 것과 동일 + middle index가 짝수 -> 가운데 앞쪽거는 버려도 됨 (짝수개의 element 버림)
  • x x [x x x]
• 가운데가 그 뒷 것과 동일 + middle index가 홀수 -> 가운데 앞쪽거 신경써야 함 (짝수개의 element 버림)
  • [x x x] x x x x

 이것을 반복해 나가면 되고, 이것은 len == 3일때도 적용된다. 우리 알고리즘이 항상 홀수개인 list를 탐색한다는 것을 알 수 있는데, 우리는 항상 짝수개의 element를 버리기 때문임. 이걸 구현한 것은 아래와 같다.

 

 예외로, nums[middle]이 앞, 뒤와 모두 다른 경우를 생각하지 못헀다. 이 경우에는 middle이 답인 경우이다. + 가능하면 종료조건을 앞에 두자.

// runtime 31ms, beats 49.25%
// memory 22.3MB, beats 62.74%

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];

        int start = 0; // 시작 index
        int end = nums.size() - 1; // 끝 index
        int middle; // 가운데 index

        while(end != start){ // 길이가 1이 될 때까지 반복
            middle = (start + end) / 2;
            // 실수 : 이 경우를 생각하지 못했음
            if(nums[middle] != nums[middle -1] && nums[middle] != nums[middle + 1]) return nums[middle]; 
            
            else if(nums[middle] == nums[middle -1]){
                if(middle % 2){
                    start = middle + 1;
                }
                else{
                    end = middle;
                }
            }
            else {  // nums[middle] == nums[middle + 1]
                if(middle % 2){
                    end = middle - 1;
                }
                else{
                    start = middle;
                }
            }
        }

        return nums[start];
    }
};

 

 이제 어떻게 더 개선해야 할까...

 

// runtime 16ms, beats 99.39%
// memory 22.3MB, beats 62.74%

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];

        int start = 0; // 시작 index
        int end = nums.size() - 1; // 끝 index
        int middle; // 가운데 index

        while(end != start){ // 길이가 1이 될 때까지 반복
            middle = (start + end) / 2;
            if(nums[middle] != nums[middle -1] && nums[middle] != nums[middle + 1]) return nums[middle]; 
            
            else if(nums[middle] == nums[middle -1]){
                if(middle % 2){
                    start = middle + 1;
                }
                else{
                    end = middle - 2; // middle과 middle-1은 같은 수이므로 middle-2로 갱신
                }
            }
            else {  // nums[middle] == nums[middle + 1]
                if(middle % 2){
                    end = middle - 1;
                }
                else{
                    start = middle + 2; // middle과 middle+1은 같은 수이므로 middle+2로 갱신
                }
            }
        }

        return nums[start];
    }
};

 탐색을 몇 번이라도 더 줄여주면 될 것이다. 확실하게 2개짜리가 붙어 있는 부분을 줄여, 탐색의 크기를 2씩 줄였다. 모든 경우가 이 경우라고 가정하면, 약 50%의 확률로 탐색할 범위가 2씩 준다. 

 

프로그래머스 lv.2 택배상자

 모든 order를 순회하면서, 각 order[i]를 넣을 수 있는지, 없는지 볼 것이다.

 

 첫 동작은 다음과 같다.

 지금까지 확인한 택배상자 번호를 curNumber라고 하자. order[i]보다 curNumber가 크다면 curNumber부터 order[i]까지를 sub에 넣어주어야 한다.

 이렇게 sub에 넣은 이후에는 stack top에 있는 값이 order[i]와 같다면 stack을 pop하고, answer++해준다.

 

 이후의 동작은 order[i]에 따라 달라진다. order[i]가 curNumber보다 크다면 stack에 넣을 수 있고, 그 값을 stack에서 빼기 때문에 answer++이다. 그러나 order[i]가 curNumber보다 작은 경우에는 stack top에 있는 것과 order[i]가 일치하지 않는 경우에는 더 이상 답을 뽑아낼 수 없다. 따라서 여기서 알고리즘 종료.

 

 시간복잡도는 worst case 모든 order를 순회하며, stack에 모든 data가 들어갔다 나오기 때문에 O(n)

 

 실수했던 점은 종료조건을 명시하지 않았던 점. 그리고 등호를 잘못 생각했다. 검토했는데 잘못 생각한 듯.

int solution(vector<int> order) {
    int ordersize = order.size();
    int curNumber = 1;
    int answer = 0;
    stack<int> stk;
    for(int i = 0; i<ordersize; i++){
        while(order[i] >= curNumber){
            stk.push(curNumber);
            curNumber++;
        }
        if(!stk.empty() && order[i] == stk.top()){
            answer++;
            stk.pop();
        }
        else break; // 실수 : 종료 조건 명시하지 않음.
    }
    
    return answer;
}