LeetCode 문제 중 난이도 EasySingle Number이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.



  문제해석

비어있지 않은 정수 배열에서, 하나를 뺀 모든 요소들은 두개씩 들어있다. 하나뿐인 요소를 찾아라.

알고리즘은 선형시간의 복잡도(O(n))를 가져야 한다. 추가적인 메모를 사용하지 않고 가능한가?





가장 먼저 떠오른 알고리즘은 먼저 배열을 정렬 한 뒤, 배열을 처음부터 탐색해 앞이나 뒤 요소와 둘다 같지 않은 요소를 찾는 것이다.예를 들어 [1,1,2,3,3]의 경우 2가 유일한 요소로 앞의 1과도 다르고 뒤의 3과도 다르다. 코드는 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int singleNumber(int[] nums) {

        Arrays.sort(nums);
        
        //배열의 길이가 1이거나, 첫번째요소와 두번째요소가 다르면 첫번째요소가 single one
        if(nums.length==1 || nums[0]!=nums[1]) return nums[0];
        
        //앞과 뒤 요소중 둘다 같은게 없으면 single one이므로 출력
        for(int i = 1; i<nums.length-1 ; i++){
            if(nums[i]!=nums[i-1&& nums[i]!=nums[i+1]) return nums[i];
        }
        
        //배열을 다 돌 때까지 못찾으면 배열의 마지막요소가 single one
        return nums[nums.length-1];
    }
}
cs


이 경우에는 추가적인 메모리 사용은 없지만 Java의 Array.sort 렬을 하는데 최대 O(nlogn) 시간이 들므로 문제의 요구사항인 선형시간 O(n)을 초과한다. 



두번째 방법은 비트연산자를 이용하는 것이다. 비트연산자를 잘 모를 경우 아래 포스팅을 참고하자.


2019/03/16 - [프로그래밍문제풀기] - 비트연산자란?





비트연산자중 ^(XOR)을 사용할 것이다. XOR연산자는 양쪽 비트가 서로 다른 경우에 1을, 같은 경우에는 0을 반환한다.



A ^ 0 = A


A ^ A = 0


A ^ B ^ A = A ^ A ^ B = 0 ^ B = B



따라서 배열의 모든 요소로 XOR 연산을 하면 두 개씩 있는 요소들은 서로 상쇄되어 사라지고 딱 하나만 있는 요소를 찾을 수 있다.


1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int singleNumber(int[] nums) {

        int singleone=0;
        
        for(int i = 0 ; i<nums.length ; i++){
            singleone=singleone^nums[i];
        }

        return singleone;
    }
}
 
cs


위의 코드에서 singleone이라는 정수형을 하나 추가로 사용했지만 이 경우 nums배열이 아무리 커져도 영향을 주지 않기 때문에 공간복잡도는 O(1)이고 추가적인 메모리는 사용하지 않는다고 봐도 된다.




문제 출처 - https://leetcode.com/problems/single-number




비트는 컴퓨터에서 데이터를 나타내는 최소 단위이다. 모든 데이터는 0과 1의 조합으로 구성되는데, 이 0또는 1이 하나의 비트이다. 1개의 비트는 두 가지 상태를 나타낼 수 있으므로 n개의 비트로는 2ⁿ가지의 상태를 나타낼 수 있다.





비트연산자란 비트 패턴이나 개별 비트 조작이 필요한 이진수에 대해 비트 단위의 연산을 실시하기 위해 사용되는 연산자이다. 비트연산자는 산술연산자 + - * / 보다 훨씬 빠르지만 요즘은 컴파일러가 자동으로 비트연산자로 변환해 주기 때문에 코딩하면서 일일히 산술연산자를 비트연산자로 바꿀 필요는 없다. 다만 알아두면 프로그래밍 시에 유용하게 쓰일 일이 많으니 비트연산자는 숙지 하는게 좋겠다. 비트연산자는 대수에서 A + B = B + A 처럼 교환법칙이 성립한다.






&(AND) 양쪽 비트가 모두 1일때만 결과가 1이되고 그렇지않으면 0

예시 : 7&2  → 2 (7=111, 2=10)




|(OR) 두 비트 중 어느 하나라도 1이면 결과가 1이고 모두 0일때만 0

예시 : 4 | 5  → 5 (4=100, 5=101)




^(XOR) 두 비트가 서로 다를때 1 같을때는 0이다

예시 : 3^65(3=11, 6=110)




~ 모든 비트 값을 반대로 만든다

예시 : int num1=17, int num2=~num1; → num2=-18

num1=00000000 00000000 00000000 00010001

num2=11111111 11111111 11111111 11101110





아래 포스팅은 비트연산자를 이용한 프로그래밍 문제 해결의 예시이다.


2019/03/16 - [프로그래밍문제풀기] - [코딩연습] Single Number 하나뿐인 숫자 찾기








LeetCode 문제 중 난이도 EasySearch Insert Position이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.




  문제해석

정렬되어 있는 배열과 목표값을 입력받아 목표값이 있는 위치의 인덱스를 구하여라. 목표값이 배열안에 존재하지 않을때에는 정렬 순서를 고려하여 목표값이 있어야할 위치의 인덱스를 구하여라.

Example 1
Input: [1,3,5,6], 5 ▶ Output: 2

Example 2 :
Input: [1,3,5,6], 2 ▶ Output: 1

Example 3: 
Input: [1,3,5,6], 7 ▶ Output: 4

Example 4:
Input: [1,3,5,6], 0  Output: 0





이 문제의 가장 쉬운 해결법은 배열을 처음부터 탐색하는 것이다. 목표값과 배열을 비교하여 배열의 값이 목표값보다 작을때는 넘어가다가 같거나 커지는 순간 해당 인덱스를 리턴한다. 배열을 전부 다 돌 때까지 리턴하지 않으면 배열에 저장된 모든 값이 목표값보다 작다는 뜻이므로 배열의 길이를 리턴하면 된다.

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int searchInsert(int[] nums, int target) {
        for(int i=0 ; i<nums.length ; i++){
            if(nums[i]>=target){
                return i;
            }
        }
        return nums.length;
    }
}
cs


시간복잡도는 O(n), 공간복잡도는 O(1)로 나쁘지 않아 보이지만 이진탐색을 이용하여 속도를 좀 더 빠르게 개선 해보자.



이진탐색이라고 하니 왠지 엄청 복잡하고 어려울 것 같지만 우리는 이미 실생활에서 이진탐색을 쓰고 있다. 술자리에서 소주병 뚜껑에 있는 숫자를 맞추는 업앤다운 술게임을 생각해보자. 술래는 뚜껑에 써있는 숫자(1부터 50사이)를 사람들이 부르는 값과 비교해서 업인지 다운인지 알려준다. 한 명씩 돌아가면서 숫자를 부르고 한 바퀴 안에 숫자를 맞추면 술래가 술을 마신다. 이 때 숫자를 빨리 맞추고 싶다면 당연히 1부터 하나씩 비교하지 않는다. 맨 처음에 25를 부르면 업이냐 다운이냐에 따라 앞의 24개(1~24) 또는 뒤의 25개(26~50) 숫자들을 바로 제외할 수 있다. 이런식으로 남은 숫자들 중 중앙값을 부르고 반씩 버리면서 후보를 줄여 나간다.




이진탐색이 바로 그런 원리이다. 정렬되어 있는 배열에서 목표값을 찾기 위해 중앙의 값과 목표값을 비교한다. 코드로는 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int searchInsert(int[] nums, int target) {
        int first = 0;
        int last = nums.length-1;
        
        while (first<=last) {
            int mid = (first+last)/2;
            if (nums[mid]==target){
                return mid;
            }else if(nums[mid]<target){
                first=mid+1;
            } else {
                last=mid-1;
            }
        }
        return first;
    }
}
cs


맨 처음에는 배열의 첫 인덱스인 0first이고 마지막 인덱스인 배열의길이-1last일 것이다. 중앙값(mid)을 구해 타겟값이 중간값과 일치하는지, 작거나 큰지 따져서 나머지 반을 버리고 또 중앙값을 찾는다. 이렇게 하면 시간복잡도를 O(log₂n)까지 줄일 수 있다. 마지막에 first가 last보다 크면 first를 리턴하는 부분은 배열에 목표값이 존재하지 않을 경우에 해당한다. 이 부분은 말로 설명하기보다는 직접 숫자를 넣어서 따져보는 것이 이해가 더 쉽다. 맨 위의 Example 2의 경우에 first, last, mid가 어떻게 바뀌는지 따져 보길 바란다.


참고로 int는 소수점이 있는 숫자는 소수점을 버림한다. 예를 들어 (2+5)/2는 3이 나온다.




문제 출처 - https://leetcode.com/problems/search-insert-position


LeetCode 문제 중 난이도 Easy인 Length of Last Word이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.





  문제해석


알파벳 대/소문자 그리고 공백문자로 이루어진 String s에서 마지막 단어의 길이를 구하여라.

마지막단어가 존재하지 않으면 0을 리턴한다. 단어의 정의는 공백없이 이루어진 문자열을 말한다.



Example : "Hello World"가 Input이라면 World의 글자수인 5 출력





간단한 경우부터 생각해보자.

문자열을 뒤에서부터 읽다가 s.charAt(i)에서 공백문자를 발견하면 전체 문자열의 길이에서 i+1을 빼서 공백 뒤의 문자의 개수를 구한다. 만약에 공백이 아예 존재하지 않아 for문이 끝날때까지 리턴이 발생하지 않는다면 하나의 단어로 이루어진 문자열이므로 그냥 문자열의 길이를 반환하면 된다.


1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int lengthOfLastWord(String s) {
 
        for(int i=s.length()-1 ; i>=0 ; i--){
            if(s.charAt(i)==' '){
                return s.length()-i-1;
            }
        }        
        return s.length();
    }
}
cs


* charAt(int index)는 문자열에서 해당 인덱스의 문자를 반환한다. 인덱스는 0부터 시작한다.





만약 문자열의 마지막 문자가 공백문자라면 어떨까? 위의 코드대로라면 "I am a Genius   "의 반환값은 0이 된다. 우리가 얻어야 할 값은 6이다. 이 문제를 해결하기 위해 공백문자를 만났을 경우 그 뒤에 알파벳이 있었는지 확인하고 나서 리턴을 하도록 코드를 바꿔 보자.

"I am a Genius   "라는 문자열을 알파벳을 만나기 전까지 거꾸로 읽다가 s를 만나면 hasChar를 true로 바꾼 뒤 알파벳의 개수가 늘어날 때마다 count를 늘려 준다. 그러다가 또 다시 공백문자를 만나면 그 때 count 값을 반환한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lengthOfLastWord(String s) {
        int count=0;
        
        //알파벳이 있었는지 확인하기위한 값
        boolean hasChar=false;
        
        //뒤에서부터 세서 알파벳이 나오고 또 공백문자 나오면 count리턴
        for(int i=s.length()-1 ; i>=0 ; i--){
            if(s.charAt(i)!=' '){
                hasChar=true;
                count++;
            }else{
                if(hasChar){
                    return count;
                }
            }
        }
        
        return count;
    }
}
cs


for문 내에서 리턴이 발생하는 경우는 hasChar가 true인 상태에서 공백문자를 만났을 때이다. 문자열의 맨 앞까지 전부 읽었는데도 리턴이 발생하지 앖는 경우는 두가지이다. 문자열 전체가 공백문자로 이루어졌거나, 문자열 전체가 한 단어 여서 공백문자가 없을 때이다. 그럴 때는 count를 리턴하면 된다. 전자라면 count가 처음에 선언한 그대로 0일 것이고 후자라면 count가 문자열의 길이와 같게 된다.





Worst Case는 문자열 전체가 공백이거나, 공백이 없는 문자열일 경우 전체 문자열을 읽어야 하므로 시간복잡도는 O(n)이고 추가적인 공간을 사용하지 않으므로 공간복잡도는 O(1)이다.


2019/02/25 - [프로그래밍문제풀기] - 빅오표기법(Big O notation)





다른 해결법도 있다. 문자열을 split()함수를 이용하여 공백문자를 기준으로 잘라 배열에 넣고 배열의 마지막 요소의 길이를 구하면 된다. 전체가 하나의 문자열이거나 전부 공백문자로 이루어진 경우에 대한 예외처리를 해 준다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int lengthOfLastWord(String s) {
 
        //공백문자열이 없다면 전체 문자열의 길이를 반환
        if (!s.contains(" ")) return s.length();
        
        String [] ss = s.split(" ");
 
        //공백문자로만 이루어져있다면 0 반환
        if (ss.length == 0return 0;
        
        //마지막 문자열의 길이 반환
        return ss[ss.length-1].length();
    }
}
cs


두번째 방법은 코드 단 4줄로 구현이 가능하다! 대신 새로운 배열을 위한 추가적인 메모리를 필요로 하므로 공간복잡도가 O(n)으로 늘어나게 된다.



문제 출처 링크 - https://leetcode.com/problems/length-of-last-word



LeetCode 문제 중 난이도 Easy인 Plus One이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

비어있지 않은 배열의 숫자들이 음수가 아닌 정수를 나타낸다고 하자. 그 정수에 1을 더하여라.

가장 큰 수부터 저장되고(앞에서부터 읽으면 된다는 뜻) 배열의 각 요소들은 한 자리의 숫자들을 가지고 있다.
정수는 값이 0일 경우를 제외하고 0으로 시작하지 않는다고 가정한다.

Example 1 : 정수 123에 1을 더하면 124이므로 [1,2,4] 출력
Example 2 : 정수 4321에 1을 더하면 4322이므로 [4,3,2,2] 출력






이 문제를 어떻게 해결할까? 먼저 Example 1과 2의 예시처럼 가장 간단한 경우의 수를 생각해보자.

배열의 맨 마지막 숫자에 +1을 해 주면 간단하게 해결 될 것이다.


1
2
3
4
5
6
7
8
9
class Solution {
    public int[] plusOne(int[] digits) {
        
        int len = digits.length;
        digits[len-1]=digits[len-1]+1;
 
        return digits;
    }
}
                    Colored by Color Scripter


** 배열(뿐만 아니라 어떤 자료형을 사용하든지간에)값이 null인지 확인하는 예외처리는 가장 기본이지만 이 문제에서는 배열이 비어있지 않다고 했으므로 파라미터로 넘어오는 digits 배열이 null이거나 배열의 length가 0인 경우에 대한 예외처리는 생략한다.




배열의 마지막 숫자가 9일 땐 어떨까? 위의 코드대로라면 Input값이 [5,3,9]일 경우 Output으로 [5,4,0]대신[5,3,10]이 나온다. 각 배열의 요소는 한 자리의 숫자로 이루어져야 하므로 위의 코드에서 배열의 값이 10 이상일 경우 자리수를 하나씩 올려주는 carry()함수를 추가하고 for문을 이용해 배열을 뒤에서부터 탐색하여 자리수를 올려준다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] plusOne(int[] digits) {
        
        int len = digits.length;
        digits[len-1]=digits[len-1]+1//배열의 마지막 값에 1을더함
 
        //그 값이 10보다 작으면(자리수가 안바뀌면) 그냥 그대로 리턴
        if(digits[len-1]<10){    
            return digits;
        }
 
        //10이상이면(9보다크면) 하나씩 올림한다
        for(int i=len-1 ; i>0 ; i--){
            if(digits[i]>9){
                carry(i,digits);
            }
        }
 
        return digits;
    }
    
    public void carry(int index,int[] digits){
        digits[index]=0;
        digits[index-1]=digits[index-1]+1;
    }
}


carry(index,digits)는 인덱스와 배열 자체를 파라미터로 받아 배열의 해당 인덱스 값이 10 이상일 경우 그 값을 0으로 만들고 배열의 인덱스-1 값에 +1을 해준다. 이 때 digits[0]이 10인 경우에는 digits[-1]가 존재하지 않으므로 digits[1]인 경우 까지만 체크하고 일단 넘어간다.





자리수를 올려주는 부분은 초등학교 때 배운 받아올림이 있는 덧셈을 생각하면 된다.








이제 거의 다 왔다! 위에서는 배열의 요소가 전부 9인 경우는 고려하지 않았다. 만일 배열의 모든 요소가 9인 경우, for문을 돌고 난 뒤 배열의 상태는 [10,0,······] 일 것이다. digits[0]에서는 더 이상 앞으로 올림해 줄 수가 없으므로 이 경우에는 배열의 크기를 1 늘리고 [1,0,0,······]으로 채워주어야 한다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int[] plusOne(int[] digits) {
        
        int len = digits.length;
        digits[len-1]=digits[len-1]+1//일단 배열의 마지막 값에 1을 더함
 
        //10보다작으면(자리수가 안바뀌면) 그냥 그대로 리턴
        if(digits[len-1]<10){    
            return digits;
        }

        //10이상이면(9보다크면) 하나씩 올림한다
        for(int i=len-1 ; i>0 ; i--){
            if(digits[i]>9){
                carry(i,digits);
            }
        }

        //배열의맨앞숫자가 10이면 배열의 크기를 1 늘리고 1000...으로 채워준다
        if(digits[0]>9){
            int[] newDigits = new int[len+1];
            newDigits[0]=1;
            for(int i=1 ; i<newDigits.length ; i++){
                newDigits[i]=0;
            }
            return newDigits;
        }
        return digits;
    }
    
    public void carry(int index,int[] digits){
        digits[index]=0;
        digits[index-1]=digits[index-1]+1;
    }
}






자 이제 완성된 코드를 돌려 보자!

Worst case는 배열의 모든 요소가 9일 경우 이므로 이 때 시간복잡도는 O(n), 공간복잡도도 O(n)이다.




2019/02/25 - [프로그래밍문제풀기] - 빅오표기법(Big O notation)



문제 출처 링크 - https://leetcode.com/problems/plus-one



프로그래밍 문제를 해결하는 데에는 여러가지 방법이 있다. 어떤 방법이 다른 방법보다 나은지(어떤 방법을 선택할지) 어떻게 알 수 있을까?



알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 시간복잡도(Time complexity)라고 하고 주로 빅오표기법(Big O notation)을 이용해 나타낸다. 입력값이 n개 일 때 걸리는 시간을 비교해 알고리즘의 효율성을 표현하기 위한 방식이다. 이 때 n의 값은 충분히 크다고 가정한다.



n의 값에 따른 알고리즘의 시간복잡도는 다음과 같다.




O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)




이해를 돕기 위해 예시를 보자. 다음 코드는 크기가 n인 정수배열에서 0보다 작은 값이 있으면 true, 없으면 false를 반환한다. 시간복잡도를 계산해보자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean hasNegativeNumber(int array[]){
 
    if(array==null){
        return false;
    } 
 
    for(int i=0 ; i<array.length ; i++){
        if(array[i]<0){
            return true;
        }
    }
    return false;
}
 
cs


배열을 순서대로 탐색하므로 만약 array[0]의 값이 음수라면 시작하자마자 결과가 나오겠지만(best case) 음수가 배열의 맨 마지막에 있다면array[n]까지 탐색해야하므로(worst case) n만큼의 시간이 걸린다. 하지만 아무리 최악의 경우라도 O(n)보다 시간이 더 걸리지는 않는다. 위의 코드의 시간복잡도는 O(n)이다.




두번째로는 정수배열과 목표값을 입력으로 받아 배열 요소의 값의 합이 목표값과 일치하는 인덱스를 찾아 반환하는 코드를 보자.


1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}
cs


이중 for문을 사용하므로 최대 n(n-1)/2만큼의 시간이 걸린다. 우리는 n이 충분히 큰 수라고 가정하기 때문에 가장 큰 항에서 상수는 무시하고 따라서 이 경우 시간복잡도는 O(n²)이다.



Big O notation은 실행시간이 꼭 그만큼 걸린다기 보다는 실행시간의 최댓값은 이정도이기때문에 '아무리 최악의 케이스여도 이정도 속도까지는 보장한다'라고 이해하면 된다.





오늘 소개할 사이트는 LeetCode.com 이다. 국내에도 코딩테스트 연습 사이트는 많지만 영어로 된 LeetCode를 추천한다.

한국에서만 일할 예정이라면 굳이 영어를 하지 않아도 괜찮다 생각 할 수도 있다. 하지만 영어로 구글링을 할 줄 알면 접할 수 있는 정보량에 차이가 있다. 이제 막 개발을 시작해서 초보적인 수준의 공부를 할 때에는 큰 차이가 없을 수도 있지만 언젠가 한국어 자료들만으로는 해결이 어려운 문제들을 접하게 될 것이다. 평소에 영어로 된 프로그래밍 컨텐츠들을 자주 접하고 영문 자료를 읽는데 익숙해 질 수 있도록 하자.




LeetCode를 이용하려면 회원가입을 해야 한다. 무료로 이용할 수 있으니 Create Account를 눌러 가입한다.





Mock 카테고리에 들어가면 모의인터뷰를 할 수 있다. 코딩테스트 뿐만 아니라 인성면접에 대한내용들도 있다. 이건 프리미엄(유료) 멤버에게만 공개되는데 아직 여기까지 할 필요는 없으니 넘어간다.





우리가 볼 것은 Problem카테고리이다. 문제의 난이도는 Easy/Medium/High로 나뉘어져 있으니 원하는 수준에 맞게 문제를 풀면 된다.





문제를 선택하고 원하는 언어를 고르면 자동으로 클래스명,파라미터,리턴값 등을 정해준다.

코드를 다 작성하고 난 후에는 오른쪽 하단의 ▶Run Code를 눌러 돌려볼 수 있다. 입력값을 바꿔 가면서 테스트 해 보고 완료되면 Submit버튼을 눌러 제출한다.





Submit을 하고 나면 내 코드에 대한 평가가 나온다. 같은 코드도 돌릴 때마다 차이가 약간 있다. 여러번 돌려서 시간의 평균 값을 내는게 아니라 한번 돌린 결과로 나오는 듯 하니 크게 신경쓰지는 않아도 된다. 어쨌든 시간이 적게 걸릴수록, 메모리를 적게 쓸수록 좋은 코드다.





Solution탭에서 해결법을 볼 수 있다. 내 코드의 속도가 너무 느리거나 메모리를 많이 썼다면 다른 효율적인 방법이 있는지 읽어본다.





Contest탭에서는 매주 전세계 개발자들이 참여하는 코딩콘테스트가 열리니 참여가능하다.

+ Recent posts