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





  문제해석

주어진 이진 트리를 가지고 해당 트리가 거울에 비친 자신과 같은지(가운데를 중심으로 대칭인지) 판별하라.








트리는 모든 노드들이 연결되어있고 순환이 존재하지 않는 그래프이다.

나무(tree)를 거꾸로 그린 모양의 계층구조를 생각해보자. 트리(tree) 자료구조는 뿌리(root node)에서 시작해 가지가 뻗어 나가며 맨 끝에는 잎(leaf node)이 달려 있다. 우리가 잘 아는 트리구조가 있는데 바로 회사의 조직도와 컴퓨터 디렉토리이다.








아래 그림은 이진 트리(binary tree)의 예이다. 예시를 보며 몇가지 기본적인 트리 용어를 알아보자.


* 이진트리(binary tree) : 트리 중에서 각 노드의 자식 노드의 수가 2개 이하인 트리



Node(A,B,C...J) : 트리의 구성요소에 해당하는 요소들


Root Node(A) : 최상위 노드


Parent Node : 어떤 노드의 상위 노드

A는 B와 C의 부모노드이고 B와 C도 각각 D&E, F&Gd의 부모노드이다


Child Node : 어떤 노드의 하위 노드

F와 G는 C의 자식노드이고 H와 I는 E의 자식노드이다


Subtree : 어떤 노드의 부모 노드의 집합

D의 조상은 B,A이고 J의 조상은 G,C,A이다


Descendant of a node : 어떤 노드의 자식노드들의 집합

C의 자손은 F,G,J이고 A의 자손은 자기자신을 제외한 전체 노드들이다


Leaf Node(D,H,I,F,J) : 자식노드가 존재하지 않는 노드


Subtree : 어떤 트리의 안에 있는 작은 트리

트리 T의 서브트리 S는 T의 노드 중 하나와 그의 자손들로 이루어진 트리


Depth of a node : 어떤 노드의 루트노드까지의 조상의 수

루트노드의 depth는 0이고 G의 depth는 2이다


Height of a tree : 해당 트리가 가진 노드들의 depth중 최댓값






다시 문제로 돌아가보자. 트리가 좌우 대칭이려면 루트노드를 중심으로 왼쪽 서브트리를 좌우대칭한 것이 오른쪽 서브트리와 같아야 한다. 그러려면 왼쪽 서브트리의 왼쪽 자식노드와 오른쪽 서브트리의 오른쪽 자식노드의 값이 같아야 하고 왼쪽 서브트리의 오른쪽 자식노드와 오른쪽 서브트리의 왼쪽 자식노드의 값이 같아야 한다.



같은방식으로 자손노드들을 리프노드까지 탐색한다. 코드로 나타내면 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isSymmetric(TreeNode root) {
        
        return isMirror(root,root);
    }
    
    public boolean isMirror(TreeNode t1, TreeNode t2) {
        
        //t1과 t2가 둘다 null이면 true
        if(t1 == null && t2 == null) return true;
        
        //t1,t2중에 하나만 널이면 양쪽이 같지 않으므로 false
        if(t1 == null || t2 == null) return false;
        
        //t1과 t2의 값이 달라도 false
        if(t1.val != t2.val) return false;
        
        return isMirror(t1.left,t2.right) && isMirror(t1.right,t2.left);
    }
}
cs


13번째 줄의 (t1 == null || t2 == null)는 위에서 이미 둘다 null인 경우를 체크했으므로 t1이나 t2가 둘중 하나만 null인 경우를 체크한다.



이 방법의 시간복잡도는 O(n)이고 공간복잡도의 worse case는 트리가 일직선으로 이루어져 Height가 O(n)인 경우이므로 O(n)이다.




문제 출처 - https://leetcode.com/problems/symmetric-tree/



저작자표시 비영리 변경금지

'코딩문제(LeetCode) > Easy' 카테고리의 다른 글

[코딩연습] Move Zeroes 0을 뒤로 밀기  (0) 2019.04.25
[코딩연습] Contains Duplicate 중복 포함 여부  (1) 2019.04.24
[코딩연습] Unique Morse Code Words 고유한 모스부호 가짓수  (0) 2019.04.19
[코딩연습] Largest Number At Least Twice of Others 가장 큰 숫자 찾기  (0) 2019.04.15
[코딩연습] Find the Town Judge 마을판사 찾기  (1) 2019.04.14


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



  문제 해석

국제 모스 부호는 다음과 같이 각 알파벳 문자가 일련의 점과 대시에 매핑되는 표준 인코딩을 정의한다.

"a"는 ".-", "b"는 "-...", "c"는 "-.-." 등등..

편의를 위해서 알파벳 전체 26문자의 표는 아래를 참고한다.

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

주어진 단어들의 리스트에서 각 단어들은 각각의 알파벳의 모스부호를 연결해서 쓰여질 수 있다. 예를 들어 "cba"는 "-.-." + "-..." + ".-"인 "-.-.-....-"가 된다. 이렇게 이어진것을 단어 변환이라고 부른다. words중에서 그런 서로 다른 변환의 가짓수를 리턴하라.


* 원본문제의 모스부호 변환 예시가 살짝 틀렸는데 그냥 무시하면 된다. 어쨌든 입력값 words을 모스부호로 변환시 나오는 가짓수를 리턴하면 된다.



이 문제는 그냥 직관적으로 풀면 된다. 단어를 모스부호로 나타냈을 때 나올 수 있는 경우의수가 몇가지인지 알기 위해서는 먼저 input으로 받은 words를 모스부호 문자표를 이용해서 변환해야 한다. 그 다음 변환된 결과들 중에서 중복을 제거한 후 총 나오는 가짓수가 몇개인지 세면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--",
                            "-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        
        //모스부호화 된 words를 저장할 배열
        String[] encoded = new String[words.length];
        
        //알파벳을 모스부호로 치환함
        for(int i=0 ; i<words.length ; i++){
            for(int j=0 ; j<words[i].length() ; j++){
                encoded[i]=encoded[i]+morse[words[i].charAt(j)-'a'];
            }
        }
        
        //중복값을 제거하기 위해 Set에 담는다
        Set<String> codeSet = new HashSet<>();
        for(int i=0 ; i<encoded.length ; i++){
            if(!codeSet.contains(encoded[i])) codeSet.add(encoded[i]);
        }
        
        return codeSet.size();
    }
}
cs


encoded라는 새로운 배열을 생성해서 words의 단어들을 모스부호화 시켜 저장했다. 그 다음 words를 Set 자료형에 담아 중복값을 제외한다. 마지막으로 Set의 사이즈를 리턴하면 된다. 

12번째줄의 words[i].charAt(j)-'a' 는 알파벳의 아스키코드를 이용한 것이다. 알파벳의 모스부호가 morse배열에 a부터 z까지 순서대로 들어가 있으므로 해당 알파벳-'a'를 하면 그 알파벳이 a부터 몇 번째 뒤에 있는지 알 수 있다. 지난번에 풀었던 Valid Anagram 문제의 두번째 풀이와 같은 원리이다.


2019/04/09 - [프로그래밍문제풀기] - [코딩연습] Valid Anagram 유효한 애너그램인지 체크하기



위 코드의 시간복잡도는 O(S), 공간복잡도는 O(S)이다. 여기서 S는 input인 words배열에 들어있는 단어들의 길이의 합을 말한다.



문제 출처 - https://leetcode.com/problems/unique-morse-code-words/



저작자표시 비영리 변경금지

'코딩문제(LeetCode) > Easy' 카테고리의 다른 글

[코딩연습] Contains Duplicate 중복 포함 여부  (1) 2019.04.24
[코딩연습] Symmetric Tree 트리가 대칭인지 확인  (0) 2019.04.21
[코딩연습] Largest Number At Least Twice of Others 가장 큰 숫자 찾기  (0) 2019.04.15
[코딩연습] Find the Town Judge 마을판사 찾기  (1) 2019.04.14
[코딩연습] Valid Anagram 유효한 애너그램인지 체크하기  (0) 2019.04.09


LeetCode 문제 중 난이도 Easy인 Largest Number At Least Twice of Others이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.



  문제해석

정수배열인 nums는 딱 하나의 가장 큰 값을 가지고 있다.

다른 모든 숫자들보다 두배이상 큰 가장 큰 수가 있다면 인덱스 값을 리턴하라. 그렇지 않으면 -1을 리턴한다.





가장 큰 값이 모든 값보다 두배 이상 큰지 보려면 두번째로 큰 값보다 두배 이상 큰지 확인하면 된다. 배열을 돌면서 가장 큰 값(largest)과 두번째로 큰 값(secondLargest)의 인덱스를 탐색한다.


맨 처음에 0,1을 넣고 nums[2]부터 돌면서 i가 largest보다도 큰 가장 큰 값이면 largest의 값을 secondLargest에 넣고 i의 값을 largest에 넣는다. largest보다는 크지 않지만 secondLargest보다 크면 secondLargest를 i로 바꿔준다. 마지막까지 배열을 탐색한 후 nums[secondLargest]*2≤를 만족하면 largest를 리턴하고 아니면 -1을 리턴한다.

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 dominantIndex(int[] nums) {
        
        if(nums.length==1) return 0;
        
        //비교를 위해 첫 두 배열의 값을 넣어주고 시작
        int largest=0;
        int secondLargest=1;
        if(nums[0]<nums[1]){
            largest=1;
            secondLargest=0;
        }
        
        //nums[i]가 largest보다크면 바꾸고 largest보단안커도 secondLargest보다크면 바꿈
        for(int i=2 ; i<nums.length ; i++){
            if(nums[i]>nums[largest]){
                secondLargest=largest;
                largest=i;
            }else if(nums[i]>nums[secondLargest]) secondLargest=i;
            
        }
 
        //largest가 secondLargest*2 보다 크거나 같으면 인덱스값 반환,아니면 -1
        return nums[largest]>=nums[secondLargest]*2 ? largest : -1 ;
    }
}
cs

마지막 리턴값의 A ? B : C 는 삼항연산자라고 부르고 A가 참이면 B를, A가 거짓이면 C를 반환한다.


배열을 한번 전체탐색하고 추가적인 메모리는 사용하지 않으므로 이 방법의 시간복잡도는 O(n), 공간복잡도는 O(1)이다.


문제 출처 링크 - https://leetcode.com/problems/largest-number-at-least-twice-of-others/


저작자표시 비영리 변경금지

'코딩문제(LeetCode) > Easy' 카테고리의 다른 글

[코딩연습] Symmetric Tree 트리가 대칭인지 확인  (0) 2019.04.21
[코딩연습] Unique Morse Code Words 고유한 모스부호 가짓수  (0) 2019.04.19
[코딩연습] Find the Town Judge 마을판사 찾기  (1) 2019.04.14
[코딩연습] Valid Anagram 유효한 애너그램인지 체크하기  (0) 2019.04.09
JAVA 정규표현식 (Regular expression)  (1) 2019.03.30


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


  문제해석

마을엔 1부터 N으로 표기되는 N명의 사람들이 있다. 이들 중 한사람이 비밀스러운 마을 판사라는 소문이 있다.

만약 마을판사가 존재한다면

1. 마을판사는 아무도 신뢰하지 않는다.

2. 모든사람들(마을판사를 제외한)은 마을판사를 신뢰한다.

3. 위의 1,2 조건을 만족하는 사람은 딱 한명 뿐이다.

입력으로 trust 배열이 주어진다. trust[i]=trust[a,b]는 a가 b를 신뢰한다는 의미이다.

마을판사가 존재한다면 그사람의 번호를 리턴하고 존재하지 않는다면 -1을 리턴하라.

* 1 ≤ N ≤ 1000

* trust.length ≤ 10000

* trust[i] are all different

* trust[i][0] != trust[i][1]

* 1 ≤ trust[i][0], trust[i][1] ≤ N




마을판사가 존재하고 x라고 하자. 모두가 x를 신뢰해야 하므로 ①trust배열 안에 [1,x],[2,x],[3,x]....[n,x]가 전부 있어야 하고 x는 아무도 신뢰하지 않으므로 ②[x,n]은 있으면 안된다.


이 값을 계산하기 위해 tsum[N] 배열을 만들어서 tsum[x-1]에 x를 믿는 사람들의 번호의 합을 저장한다. x가 마을판사이려면 자기자신인 x를 제외한 1~N의 사람들이 전부 x를 신뢰해야 하므로 tsum[x-1][1]은 1~N의 합-x 어야 한다. 그리고 x는 아무도 믿지 않으므로 [x,b]일 때 tsum[x-1]의 값에 -1을 집어넣는다.

이렇게 하면 x를 제외한 모두가 x를 믿는다고 해도 tsum[x-1]의 값은 1~N-x보다 작아진다. -1대신에 아무 음수 또는 N(N+1)/2보다 큰값을 집어넣어도 된다. 코드는 다음과 같다.


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 static int findJudge(int N, int[][] trust) {
        int[] tsum = new int[N];
        int nsum = N*(N+1)/2;
        
        //[a,b]이면 tsum[b-1]에 a를 더함
        for(int i=0 ; i<trust.length ; i++){
            tsum[trust[i][1]-1] = tsum[trust[i][1]-1] + trust[i][0];
            tsum[trust[i][0]-1] = -1;
        }
        
        //tsum[x-1]이 1~N의 합과 같으면 x 리턴
        for(int i=0 ; i<tsum.length ; i++){
            if(tsum[i]+i+1 == nsum){
                return i+1;
            }
        }
        
        //그런 값이 없으면 -1 리턴
        return -1;
    }
}
 
cs


이 방법의 시간복잡도는 O(n) 공간복잡도도 O(n)이다.


문제 출처 - https://leetcode.com/problems/find-the-town-judge

저작자표시 비영리 변경금지

'코딩문제(LeetCode) > Easy' 카테고리의 다른 글

[코딩연습] Unique Morse Code Words 고유한 모스부호 가짓수  (0) 2019.04.19
[코딩연습] Largest Number At Least Twice of Others 가장 큰 숫자 찾기  (0) 2019.04.15
[코딩연습] Valid Anagram 유효한 애너그램인지 체크하기  (0) 2019.04.09
JAVA 정규표현식 (Regular expression)  (1) 2019.03.30
[코딩연습] Hamming Distance 해밍거리 구하기  (0) 2019.03.28


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



  문제해석

s와 t 두개의 문자열을 받아 t가 s의 애너그램(철자순서를 바꾼말)인지 확인하는 함수를 작성하라.

* 문자열은 소문자로만 이루어져있다고 가정한다.







첫번째 방법은 s와 t를 배열에 담아 정렬한 뒤 비교하는 방법이다. 문자열의 길이가 다르다면 당연히 같을수 없으므로 false를 리턴한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isAnagram(String s, String t) {
 
        //두 문자열의 길이가 다르면 false
        if (s.length() != t.length()) return false;
        
        //s와 t를 각각 char배열로 변환
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        
        //정렬한다
        Arrays.sort(str1);
        Arrays.sort(str2);
        
        //철자가 같다면 정렬후 두 배열값이 같아야함
        return Arrays.equals(str1, str2);
        
    }
}
cs

16번째줄의 Arrays.equals(array1,array2)는 배열 안의 값이 같은지 확인하는 메소드로 array1.equals(array2)와는 다르다. 후자는 array1==array2와 같은의미로 실제로 두 배열이 주소값까지 같은 동일한 배열인지 확인하는 메소드이다.





두번째 풀이는 각 스펠링이 나온 개수를 배열에 저장하고 비교하는 것이다.

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
class Solution {
    public boolean isAnagram(String s, String t) {
        
        if (s.length() != t.length()) return false;
        
 
        //a부터 z까지 각각의 알파벳이 나온 횟수를 담기위한 배열 생성
        int[] table = new int[26];
        
        //s의 스펠링들이 각각 몇번 나왔는지 1씩 증가시키면서 table에 저장
        for (int i = 0; i < s.length(); i++) {
            table[s.charAt(i) - 'a']++;
        }
        
        //table에서 t에도 있는애들을 하나씩 감소시킨다
        for (int i = 0; i < t.length(); i++) {
            table[t.charAt(i) - 'a']--;
            if (table[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        
        return true;
    }
}
cs


먼저 a부터 z까지 26개의 알파벳이 나온 횟수를 담기위한 배열을 만든다. 그러고나서 s를 탐색하면서 각 알파벳이 나올때마다 해당 위치의 배열값을 1씩 증가시킨다. 그 다음에 t를 탐색하면서 해당 위치의 배열값을 1씩 감소시킨다. 전체 배열이 0으로 채워지면 true를 리턴한다.


12,17,18번째 줄의 chatAt(i) - 'a'는 알파벳이 아스키코드(0~127)의 값으로 저장되는 것을 이용한 것이다. a~z까지의 알파벳에서 a를 빼주면 0~25까지의 숫자가 나온다.




아스키값 참고



문제 출처 - https://leetcode.com/problems/valid-anagram

저작자표시 비영리 변경금지

'코딩문제(LeetCode) > Easy' 카테고리의 다른 글

[코딩연습] Largest Number At Least Twice of Others 가장 큰 숫자 찾기  (0) 2019.04.15
[코딩연습] Find the Town Judge 마을판사 찾기  (1) 2019.04.14
JAVA 정규표현식 (Regular expression)  (1) 2019.03.30
[코딩연습] Hamming Distance 해밍거리 구하기  (0) 2019.03.28
[코딩연습] Power of Four 4의 거듭제곱인지 판별하기  (0) 2019.03.18

자바 정규표현식(Regular expression)에 대해 알아보자.




  정규표현식이란?

Regular expression, 줄여서 Regex라고도 부른다. 특정한 패턴을 가진 문자열(String)을 표현하는데 사용하는 형식언어이다. 정규표현식을 이용하여 특정 패턴에 맞는 문자열을 찾아 바꾸거나, input값이 유효한지 체크하는 데에 주로 사용한다.



예를 들어 핸드폰번호로 010-3e88-2pe7과 같은 입력값은 말이 되지 않는다. 정규표현식을 이용해 입력값의 패턴이 유효한 패턴인지 validation이 가능하다.






자 그럼 자바에서는 정규표현식을 어떤식으로 사용할까?



s.matches("regex") : s가 regex 패턴과 일치하는지 확인

s.replaceFirst("regex","replacement") : 가장 먼저나온 regex를 replacement로 치환

s.replaceAll("regex","replacement") : regex와 일치하는 부분을 전부 replacement로 치환

s.split("regex") : regex를 기준으로 s를 잘라 배열에 집어넣음




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class HelloWorld {
 
    public static void main(String[] args) {
        
        String s1 = "Becca is genius";
        String s2 = "becca.kim@gmail.com";
        
        if(s1.matches("(?i)b\\D+$")){
            System.out.println("(?i)b\\D+$ 정규표현식 일치");
        }
        
        if(s1.matches("b\\D+$")){
            System.out.println("b\\D+$ 정규표현식 일치");
        }
                
        if(s2.matches("[a-z0-9\\.]+@[a-z0-9]+\\.[a-z]+")){
            System.out.println("정상적인 이메일 주소");
        }
        
        s1=s1.replaceFirst("[c]+", "k");
        System.out.println(s1);
        
    }
}
cs

8번째 줄의 (?i)b\\D+$는 대소문자 구분없이 b로 시작하고 숫자가 아닌 문자들이 반복되다가 끝나는 문자열을 말한다. 만약에 s1 중간에 숫자가 하나라도 있으면 s1.matches("(?i)b\\D+$")는 false가 된다.


12번째 줄의 b\\D+$는 s1의 첫문자가 대문자이기 때문에 출력되지 않는다.


16번째줄의 [a-z0-9\\.]+@[a-z0-9]+\\.[a-z]+는 알파벳,숫자,마침표문자로 이루어진 아이디@알파벳들.알파벳들 패턴을 나타낸다.

* 위의 패턴이 우리가 사용하는 실제 이메일 주소 정규표현식은 아니다. 어떤 사이트는 이메일이 주소에 마침표를 허용하지 않을 수도 있고 _등의 특수문자도 더 사용 가능한 경우도 있다.



코드를 돌려보면 아래와 같은 결과가 나온다. 


정규표현식을 처음 접하면 조금 복잡해 보인다고 생각할 수도 있지만 몇번 직접 해보면 이해가 빠를 것이다. 비밀번호패턴, 주소, 핸드폰번호 등 여러가지 정규표현식을 아래의 사이트에서 연습해보는것을 추천한다.

http://regex101.com

저작자표시 비영리 변경금지

'코딩문제(LeetCode) > Easy' 카테고리의 다른 글

[코딩연습] Find the Town Judge 마을판사 찾기  (1) 2019.04.14
[코딩연습] Valid Anagram 유효한 애너그램인지 체크하기  (0) 2019.04.09
[코딩연습] Hamming Distance 해밍거리 구하기  (0) 2019.03.28
[코딩연습] Power of Four 4의 거듭제곱인지 판별하기  (0) 2019.03.18
쉬프트연산자  (0) 2019.03.18

 

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

 

  문제해석
두 정수 사이의 해밍거리는 상응하는 위치에서 값이 다른 비트의 개수이다.
두 정수 x,y를 입력으로 받아 해밍거리를 구하여라.

* x,y는 0 이상 2^31 이하

 

 

 

 

비트연산자를 이용하면 서로 다른 비트만 1로 표시할 수 있다. 

 

0101 ^ 0100 = 0001

 

100111 ^ 101011 = 001100

 

 

비트연산자란?

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

beccacatcheserrors.tistory.com

 

 

입력 받은 x와 y에 XOR 연산을 하면 x와 y에서 비트값이 다른 위치의 비트를 1로 바꾸어다. 그 결과값에서 1의 개수를 리턴하면 된다. 자바에서 제공해주는 Integer.bitCount를 사용하면 1줄만에 해결이 가능하다.

1
2
3
4
5
public class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x^y);
    }
}
 cs

 

 

하지만 왠지 이 방법은 너무 치사한(?)것 같으니 비트의 개수를 직접 세어 주자.

 

 

 

 

어떤 숫자에서 1을 빼면 마지막 1이 있는 위치부터 끝까지 비트가 바뀐다

 

1001100 - 1 = 1001011

 

그 상태에서 원래의 숫자와 AND(&)연산을 하면 맨 오른쪽의 1이 사라지게 된다.

 

1001100 & 1001011 = 1001000

 

 

 

 

위의 원리를 이용해 코드에 적용해 보자. x^y의 결과값이 0이 될 때까지 오른쪽에서부터 1을 차례로 없애주고 count를 1씩 늘린다. 마지막에는 count 값을 리턴한다.

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int hammingDistance(int x, int y) {
        int xor=x^y, count=0;
        
        while(xor!=0) {
            xor=xor&(xor-1);
            count++;
        }
        return count;
    }
}
 cs

연산 횟수의 최댓값은 Integer의 비트수로 상수로 정해져 있으니 시간복잡도는 O(1)이고 공간복잡도도 O(1)이다.

 

'코딩문제(LeetCode) > Easy' 카테고리의 다른 글

[코딩연습] Valid Anagram 유효한 애너그램인지 체크하기  (0) 2019.04.09
JAVA 정규표현식 (Regular expression)  (1) 2019.03.30
[코딩연습] Power of Four 4의 거듭제곱인지 판별하기  (0) 2019.03.18
쉬프트연산자  (0) 2019.03.18
[코딩연습] Remove Duplicates from Sorted Array 정렬된 배열에서 중복값 제거하기  (0) 2019.03.17



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



  문제해석

부호를 갖는 32비트의 주어진 정수를 가지고 그것이 4의 거듭제곱인지 판별하는 함수를 작성하라.




4의 거듭제곱을 2진수로 나타내보자. 100, 10000, 1000000,······ 첫 비트 1 오른쪽에 짝수개의 0을 가지고 있을 것이다. 4로 나누었을 때 깔끔하게 나누어 떨어지게 되므로 input/4의 값이나 input>>2의 값이 정확히 같을 것이다. 쉬프트연산자에 대해 잘 모른다면 아래 포스팅을 참고하자.


2019/03/18 - [프로그래밍문제풀기] - 쉬프트연산자




input값이 0보다 작은 경우엔 연산을 할 필요도 없다. 0보다 작거나 1일 경우에 예외처리 해 주고 아래의 코드에서는 0보다 작은 경우는 이미 처리했으니 >>산술쉬프트연산자를 쓰든 >>>논리쉬프트연산자를 쓰든 상관이 없다. 만약 함수의 앞부분에서 음수에 대한 예외처리를 해주지 않아도 결과 값에는 문제가 없겠지만 그럴 경우에 >>산술쉬프트연산자를 쓰면 굳이 할 필요 없는 -16/4 = -16>>2따위의 연산을 하게되므로 그 때는 >>>논리쉬프트연산자를 쓰는게 나겠다. (어쨌든 쉬프트연산자는 속도가 매우 빠르기 때문에 성능에는 전혀 상관이 없다!)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isPowerOfFour(int num) {
        if(num<=0) return false;
        if(num==1) return true;
        
        while(num!=1){
            if((num>>2)*4 != num){
                return false;
            }
            num=num>>2;
        }
        return true;
    }
}
cs



Worst Case(01000000 00000000 00000000 00000000)에도 쉬프트연산은 최대 15번으로 정해져 있으므로 시간복잡도는 O(1)이다. 또한 추가적인 메모리를 사용하지 않으므로 공간복잡도도 O(1)이다.




문제 출처 - https://leetcode.com/problems/power-of-four



저작자표시 비영리 변경금지

'코딩문제(LeetCode) > Easy' 카테고리의 다른 글

JAVA 정규표현식 (Regular expression)  (1) 2019.03.30
[코딩연습] Hamming Distance 해밍거리 구하기  (0) 2019.03.28
쉬프트연산자  (0) 2019.03.18
[코딩연습] Remove Duplicates from Sorted Array 정렬된 배열에서 중복값 제거하기  (0) 2019.03.17
[코딩연습] Single Number 하나뿐인 숫자 찾기  (2) 2019.03.16

쉬프트 연산자는 이름에서 볼 수 있듯이 bit를 오른쪽 또는 왼쪽으로 shift하는 연산자이다. 한가지 주의할 점은 비트를 이동할 때에는 한쪽으로 밀려난 비트가 반대편에서 다시 들어오는 것이 아니라 연산자의 종류에 따라 새로운 비트로 채운다. 쉬프트 연산자에는 3가지가 있다.




<<n Left shift 비트를 왼쪽으로 n만큼 이동하고 빈 공간을 0으로 채운다.

예시 : int a=17; a=a<<2; → a=68

전 00000000 00000000 00010001

후 00000000 00000000 01000100




>>n Arithmetic right shift 비트를 오른쪽으로 n만큼 이동하고 빈공간을 부호에 맞게 채운다.

예시 : int b=-325; b=b>>4; → b=-21

11111111 11111111 11111110 10111011

11111111 11111111 11111111 11101011

음수일때는 빈 공간을 1로 채운다.


예시 : int c=1048576; c=c>>5; → c=32768

00000000 00010000 00000000 00000000

00000000 00000000 10000000 00000000

양수일때는 빈 공간을 0으로 채운다.




>>>n Logical right shift 비트를 오른쪽으로 n만큼 이동하고 빈공간을 부호에 상관없이 0으로 채운다.

예시 : int d=-15000; d=d>>>6; → d=67108629

11111111 11111111 11000101 01101000

00000011 11111111 11111111 00010101





쉬프트 연산자는 산술연산자에 비해 속도가 엄청 빠르다. 하지만 프로그래밍을 할 때에는 나 혼자 개발하는 프로그램이 아니라면 속도 뿐만 아니라 코드의 가독성도 중요하다. 특수한 목적의 프로그래밍을 제외하고는 산술연산자를 굳이 속도 때문에 쉬프트연산자로 바꿀 필요는 없다. 쉬프트연산자는 10진 연산보다는 2진 연산에 주로 사용한다.

'코딩문제(LeetCode) > Easy' 카테고리의 다른 글

[코딩연습] Hamming Distance 해밍거리 구하기  (0) 2019.03.28
[코딩연습] Power of Four 4의 거듭제곱인지 판별하기  (0) 2019.03.18
[코딩연습] Remove Duplicates from Sorted Array 정렬된 배열에서 중복값 제거하기  (0) 2019.03.17
[코딩연습] Single Number 하나뿐인 숫자 찾기  (2) 2019.03.16
비트연산자란?  (0) 2019.03.16





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





  문제해석

정렬된 배열인 nums를 입력으로 받아 모든 요소들이 한번씩만 나타나도록 배열을 수정하고 길이를 리턴하여라. 새로운 저장공간을 사용하지 말고 input 배열을 수정하는 것으로 O(1)의 추가 메모리 내에서 해결해라.






이번 문제는 꽤 쉽다! 배열을 탐색하면서 중복값인지 아닌지 체크하고 중복값이 아닌 경우에만 앞에서부터 하나씩 저장해준다. 지금 탐색하고 있는 배열의 인덱스와 저장해야될 곳의 인덱스가 다르므로 저장해야 할 위치는 result라는 변수를 선언해서 기록한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int removeDuplicates(int[] nums) {
        
        //배열의 길이가 0일때의 예외처리
        if(nums.length==0) return 0;
        
        int result=1;
        for(int i=1 ; i<nums.length ; i++){
            //요소가 중복값이 아닐 때에만 가져오고 리턴할 배열의 길이를 늘려줌
            if(nums[i]!=nums[i-1]){
                nums[result]=nums[i];
                result++;
            }
        }
        return result;
    }
}
cs


배열을 처음부터 끝까지 탐색해야 하므로 시간복잡도는 O(n)이고 저장할 때 필요한 변수 하나만 선언하면 되므로 공간복잡도는 O(1)이다.


문제 출처 - https://leetcode.com/problems/remove-duplicates-from-sorted-array

저작자표시 비영리 변경금지

'코딩문제(LeetCode) > Easy' 카테고리의 다른 글

[코딩연습] Power of Four 4의 거듭제곱인지 판별하기  (0) 2019.03.18
쉬프트연산자  (0) 2019.03.18
[코딩연습] Single Number 하나뿐인 숫자 찾기  (2) 2019.03.16
비트연산자란?  (0) 2019.03.16
[코딩연습] Search Insert Position 숫자를 넣을 자리 찾기  (0) 2019.03.14

+ Recent posts

티스토리툴바