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




  문제해석


스택의 오퍼레이션을 이용하여 큐의 다음 오퍼레이션들을 구현하라.

push(x) -- 큐의 마지막에 x를 삽입

pop() -- 큐의 맨앞의 요소를 제거

peek() -- 맨앞의 요소를 가져옴

empty() -- 큐가 비었는지 여부를 리턴


스택(Stack)은 LIFO(Last-In, First-Out), 큐(Queue)는 FIFO(First-In, First-Out)의 구조를 가졌다. 스택과 큐를 잘 모른다면 아래 포스팅을 참고한다. 


스택&큐 Stack and Queue



스택으로 큐를 구현하려면, ① 넣을때부터 FIFO로 넣던지 ② 넣을때는 LIFO로 넣고 꺼낼때 FIFO로 꺼내면 된다.


① FIFO처럼 저장하는 방법은 마지막으로 넣는 요소를 스택의 가장 아래(bottom)에 저장하는 것이다. 그러면 스택에서 꺼낼때, 먼저 저장된 요소가 먼저 꺼내진다(FIFO). 코드로 나타내면 아래와 같다.


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
34
35
36
class MyQueue {
 
    Stack<Integer> myqueue = new Stack<Integer>();
 
    public MyQueue() {
        
    }
 
    public void push(int x) {
        Stack<Integer> temp = new Stack<Integer>();
 
        //myqueue에 있는 요소들을 temp으로 옮겨담는다
        while(!myqueue.isEmpty()){
            temp.push(myqueue.pop());
        }
        //temp의 맨 위에 x를 삽입한다
        temp.push(x);
        
        //myqueue에 다시 옮겨담는다(가장 마지막에 넣은 x가 temp의 가장 아래로 가게됨)
        while(!temp.isEmpty()){
            myqueue.push(temp.pop());
        }
    }
    
    public int pop() {
        return myqueue.pop();
    }
 
    public int peek() {
        return myqueue.peek();
    }
    
    public boolean empty() {
        return myqueue.isEmpty();
    }
}
cs


 넣을때는 LIFO로 넣고 꺼낼때 FIFO처럼 꺼내는 방법은 저장할때는 그냥 스택의 맨 위(top)에 저장한다. 꺼낼때에는 스택의 맨 마지막에 있는 요소를 불러온다. 코드로 나타내면 아래와 같다.

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class MyQueue {
 
    Stack<Integer> myqueue = new Stack<Integer>();
    
    public MyQueue() {
        
    }
    
    public void push(int x) {
        myqueue.push(x);
        
    }
 
    public int pop() {
        Stack<Integer> temp = new Stack<Integer>();
        
        //myqueue의 요소들을 전부 temp에 옮겨담는다
        while(!myqueue.isEmpty()){
            temp.push(myqueue.pop());
        }
        
        //temp의 가장 위에있는 요소를 꺼낸다
        int top = temp.pop();
        
        //원래대로 myqueue에 옮겨담는다
        while(!temp.isEmpty()){
            myqueue.push(temp.pop());
        }
        return top;
    }
    
    public int peek() {
        Stack<Integer> temp = new Stack<Integer>();
        
        while(!myqueue.isEmpty()){
            temp.push(myqueue.pop());
        }
        
        int top = temp.peek();
        
        while(!temp.isEmpty()){
            myqueue.push(temp.pop());
        }
        return top;
    }
    
    public boolean empty() {
        return myqueue.isEmpty();
    }
}
cs



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





  문제해석

'('와 ')'로 이루어진 문자열 S에 최소로 괄호기호를 더해서 결과값이 유효하게 만든다.

유효한 괄호 문자열이란

- 빈 문자열 이거나,

- A와 B가 각각 유효한 괄호 문자열일때 AB를 연결한 형태이거나,

- A가 유효한 문자열일때 (A)의 형태인것


유효한 괄호문자열로 만들기 위해서 추가해주어야 할 최소한의 괄호기호의 개수를 구하여라.






스택(Stack) 자료구조를 이용해서 문제를 해결해보자. 스택은 FILO(First In Last Out)의 특징을 가진 자료구조이다. 책을 겹겹이 쌓는것을 상상해보자. 맨 위에 책을 올려놓거나 맨 위에 있는 책을 치울 수 있다. 아래에 있는 책을 꺼내려면 먼저 그 위의 책들을 전부 치워야 한다.





push(value) : value를 스택의 마지막 데이터 위치에 삽입

pop() : 스택 마지막 삽입된 데이터 제거

peek() : 스택 마지막 삽입된 데이터 값 확인





문제에서 괄호가 제대로 열리고 닫히려면

1 괄호를 연만큼 닫아주어야 한다. → '('와 ')'의 갯수가 같아야 함

2 먼저 열어준 뒤에 닫아주어야 한다. → '))(('은 유효한 괄호문자열이 아님



문자열 S를 탐색하면서 i번째 문자가 '('이면 스택에 넣어주자. i번째 문자가 ')'인 경우 스택에 들어있는 '('문자를 제거해준다. 스택이 비어있어서 제거할 '('가 없다면 answer+1을 해주자. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minAddToMakeValid(String S) {
        
        Stack<Character> stack = new Stack<>();
        int answer=0;
        
        for(int i=0 ; i<S.length() ; i++){
            if(S.charAt(i)=='('){
                stack.push(S.charAt(i));
            }else if(stack.empty()){
                result++;
            }else{
                stack.pop();
            }
        }
        
        return answer + stack.size();
    }
}
cs


answer는 필요한 '('의 개수이고 stack에 들어있는 '('만큼 ')'도 필요하다. 따라서 answer+stack.size()가 유효한 괄호문자열을 만들기 위해 필요한 '('와 ')'의 개수이다. 이 방법의 시간복잡도는 O(n), 공간복잡도는 O(n)이다.


문제출처 - https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/



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



  문제해석


주어진 first와 second를 이용해 "first second third" 형태의 텍스트로 first바로 다음에 second가 오고 바로 뒤에 third가 오는 경우를 고려하여라.

각각의 경우에 third를 answer에 추가하고 answer를 리턴하라.






1 처음엔 text 내third가 몇개인지 알 수 없으므로 크기가 고정된 배열 대신 리스트를 이용하자.

2 text에 있는 단어들을 문자열 배열 words에 넣어준다.

3 words[i]가 first이고 words[i+1]이면 words[i+2]를 answer에 추가한다.

4 마지막으로 answer를 배열로 변환하여 리턴한다.


코드로 나타내면 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String[] findOcurrences(String text, String first, String second) {
        
        List<String> answer = new ArrayList<>();
        
        String[] words = text.split(" ");
        for(int i=0 ; i<words.length-2 ; i++){
            if(words[i].equals(first) && words[i+1].equals(second)){
                answer.add(words[i+2]);
            }
        }
        return answer.toArray(new String[0]);
    }
}
cs


위 코드의 시간복잡도는 O(n), 공간복잡도는 O(n)이다.


문제출처 - https://leetcode.com/problems/occurrences-after-bigram/



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



  문제해석

2진 행렬 A를 입력으로 받아 수평으로 뒤집은 다음 숫자를 반대로 바꾸고 결과를 반환하라. 

수평으로 뒤집는것은 각 줄의 이미지가 뒤집히는 것이다. 예를들어 [1,1,0]을 수평으로 뒤집으면 [0,1,1]이 된다.

반대로 바꾸는것은 0은 1로, 1은 0으로 변환하는것이다. 예를들어 [0,1,1]은 [1,0,0]이 된다.







설명이 복잡해 보일때에는 Example을 보자. 우리가 해야 할 일은 입력 배열을 좌우로 뒤집은 뒤 0은 1로, 1은 0으로 바꿔서 반환해주기만 하면 된다.


위의 예시의 첫번째 행을 보자. A[0][2]을 temp에 넣고 A[0][2]에는 A[0][0]의 값과 1의 XOR 연산값(0을 1로, 1을 0으로)을 넣어주자. 위의 예시에서는 가운데 열인 A[0][1]은 temp에 넣을 필요 없이 A[0][1]^1만 해주면 되지만 열이 짝수인 경우에는 temp에 넣고 값을 서로 바꾸어주어야 한다. 반복문으로 전체 행에 연산해준다. XOR연산을 잘 모른다면 아래 비트연산자 포스팅을 참고한다.

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




1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        
        for(int i=0 ; i<A.length; i++){
            for(int j=0 ; j<(A[0].length+1)/2 ; j++){
                int temp = A[i][A[0].length-j-1];
                A[i][A[0].length-j-1= A[i][j]^1;
                A[i][j] = temp^1;
            }
        }
        return A;
    }
}
cs


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


문제 출처 - https://leetcode.com/problems/flipping-an-image/





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



  문제해석


레몬에이드 가판대에서 각 레몬에이드의 가격은 $5이다.

레몬에이드를 사기 위해 줄에 선 손님들은 순서대로 한명씩 주문한다. 각각의 손님들은 $5, $10, $20 셋 중에 하나의 지폐를 내고 레몬에이드를 하나씩 주문한다. 정확하게 거스름돈을 돌려주어서 순수한 거래는 손님이 $5씩 지불한게 되어야 한다.

처음에 잔돈 없이 시작해서 모든 손님들에게 정확한 거스름돈을 돌려줄 수 있는 경우에만 true를 리턴하라.







가지고 있는 지폐 수를 체크하기 위해서 5달러 지폐의 수는 five, 10달러 지폐의 수는 ten이라는 변수에 넣는다. 20달러는 거스름돈으로 나갈 일이 없으므로 체크할 필요 없다. 5달러 지폐를 받으면 five+1, 10달러지폐를 받으면 ten+1을 해준다.


20달러 지폐를 받은 경우에는 두가지로 나눌 수 있다. 거스름돈을 10+5 합쳐서 줄 수도 있고 만약에 10달러가 없으면 5+5+5로 줄 수도 있다. 가지고 있는 5달러와 10달러 지폐가 음수가 되는 때가 있다면 거스름돈을 정확하게 돌려줄 수 없는 것이다.


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 boolean lemonadeChange(int[] bills) {
        int five=0, ten=0;
        
        for(int b : bills) {
            if(b==5){
                five++;
            }else if(b==10) {
                ten++;
                five--;
            }else if(b==20 && ten==0) {
                five-=3;
            }else{
                ten--;
                five--;
            }
            
            if(five<0 || ten<0return false;
        }
        
        return true;
    }
}
cs


한가지 유의할 점은 if(five<0 || ten<0) return false는 for문 안에 있어야 한다. 그렇지 않으면 지폐수가 음수였다가 다음 손님들에게 지폐를 받는, 실제로 존재할 수 없는 경우에도 true를 리턴한다.


이 코드의 시간복잡도는 O(n), 공간복잡도는 O(1)이다.



문제 출처 - https://leetcode.com/problems/lemonade-change/






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



  문제해석


학생의 출석기록을 의미하는 String을 입력으로 받는다. 출석기록은 3가지 문자로만 이루어져 있다


A : 결석

L : 지각

P : 출석


결석이 한번을 넘거나 연속으로 두번 넘게 지각하는 경우가 없어야만 상을 받는다. 해당 학생이 상을 받을 수 있는지 없는지 리턴하라.



이 문제는 정규식을 이용해 1줄의 코드로 풀 수 있다. 정규식에 대해 잘 모른다면 아래 포스팅을 참고하자. {n}은 n번 반복이라는 뜻이다.


2019/03/30 - [프로그래밍문제풀기] - JAVA 정규표현식 (Regular expression)



1
2
3
4
5
6
class Solution {
    public boolean checkRecord(String s) {
        
        return !s.matches(".*A.*A.*|.*L{3}.*");
    }
}
cs






두번째 방법은 배열을 탐색하면서 A가 1번을 넘는지, L이 2번 넘게 연속인지 확인하는 것이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean checkRecord(String s) {
        
        int absent=0;
        int continuousLate=0;
        
        for(char c : s.toCharArray()) {
            
            if(c=='A') absent++;
            
            if(c=='L') continuousLate++else continuousLate=0;
            
            if( absent>1 || continuousLate>2 ) return false;
            
        }
        return true;
    }
}
cs




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




  문제해석

유효한 괄호 문자열은 비어있는 (""), "(" + A + ")", 또는 A + B이다. 여기서 A와 B는 유효한 괄호 문자열이며, +는 문자열의 연결을 나타낸다. 예를 들어 "", "()", "(())()", "(()(()))"는 모두 유효한 괄호 문자열이다.

유효한 괄호 문자열 S가 비어 있지 않고, A와 B가 비어 있지 않은 유효한 괄호 문자열을 사용하여 S = A+B로 분할할 수 있는 방법이 없으면 원시적이라고 한다.

주어진 유효한 괄호 문자열 S의 원시분해를  S = P_1 + P_2 + ... + P_k라 하자. (P_i는 원시적인 유효한 괄호 문자열)

S의 원시 분해에서 가장 바깥쪽 괄호를 제거한 모든 원시 문자열을 반환해라.







가장 바깥쪽 괄호인지 체크하기 위해서 open이라는 변수를 사용한다. i번째 인덱스가 여는괄호이면 +1, 닫는괄호이면 -1을 해준다. open이 양수면 괄호가 열린상태이다.


open이 0일때의 여는괄호와 1일때의 닫는괄호가 가장 바깥쪽 괄호일 것이다. 가장 바깥쪽 괄호를 제거하기 위해서 open이 0일때 여는괄호와 open이 1일때 닫는괄호가 아닌 문자들만 sb에 덧붙인다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String removeOuterParentheses(String S) {
        
        StringBuilder sb = new StringBuilder();
        int open = 0;
        
        for(int i = 0 ; i<S.length() ; i++){
            if(S.charAt(i) == '(' ){
                if(open != 0) sb.append(S.charAt(i));
                open++;
            }else{
                if(open != 1) sb.append(S.charAt(i));
                open--;
            }    
        }
        return sb.toString();
    }
}
cs


이 풀이의 시간복잡도는 O(n)이고 공간복잡도도 O(n)이다.






문제출처 - https://leetcode.com/problems/remove-outermost-parentheses/





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




  문제해석


총 n개의 동전을 가지고 k번째 줄에는 k개의 동전이 오도록 계단모양으로 배열해보자.

주어진 n으로 만들 수 있는 온전한 계단의 최대 라인수를 찾아라.

n은 음수가 아닌 정수로 부호가 있는 32비트 정수의 범위내에 있다.






k번째까지 계단모양을 채우려면 동전의 갯수가 1+2+3+...+k개 필요하다. 1부터 k까지의 숫자의 합은 k(k+1)/2이다. 그러면 n≥k(k+1)/2을 만족하는 k를 찾아야 한다. 중학생 때 배운 완전제곱식을 이용하여 k에 관한 형태로 바꾸어준다.






결과적으로 k는 2n+0.25의 제곱근에서 0.5를 뺀 값보다 작거나 같을 것이다. 구하려는 값은 해당 부등식을 만족하는 자연수 k의 최댓값이므로 좌변의 식에서 소수점을 버림하면 자연수 k의 최댓값을 구할 수 있다. 입력값 n은 정수만 담을 수 있는 int 자료형이므로 소수점 계산을 하기 위해 double 자료형을 이용한다. 코드로 작성하면 다음과 같다.


1
2
3
4
5
6
7
8
9
class Solution {
    public int arrangeCoins(int n) {
        
        if(n<2return n;
        
        double result = (Math.sqrt(2*n+0.25))-0.5;
        return (int)result;
    }
}
cs


double 자료형이 익숙하지 않다면 삐멜소프트웨어 엔지니어 - 자바 변수와 자료형(float,double) 포스트를 참고하자.





잘 돌아갈 것 같지만 문제가 하나 있다. 문제에서 n은 32-bit signed integer라고 하였다. 이게 무슨 말이냐 하면 32비트 중 가장 첫번째 비트는 부호비트로 쓰인다는 것이다. 32-bit signed integer로 나타낼 수 있는 범위는 -2,147,483,648 ~ 2,147,483,647이다. 삐멜소프트웨어 엔지니어 - 자바 변수와 자료형(byte,short,int,long)




input으로 받는 n에 2를 곱한 값이 2^31 이상이면 맨앞의 sign bit가 1이 되어 음수로 바뀐다. 이 문제를 해결하기 위해 long자료형을 이용하자. 아래는 이해를 돕기 위한 코드고 실제로 사용할 때에는 L만 붙여주면 자동으로 long자료형으로 바뀐다.


1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int arrangeCoins(int n) {
        
        if(n<2return n;
        long twoN = 2*(long)n;
        
        double result = (double)(Math.sqrt(twoN+0.25))-0.5;
        return (int)result;
    }
    
}
cs







문제 해결 완료!


1
2
3
4
5
6
7
8
9
class Solution {
    public int arrangeCoins(int n) {
        
        if(n<2return n;
        
        double result = (double)(Math.sqrt(2L*n+0.25))-0.5;
        return (int)result;
    }
}
cs


시간복잡도는 O(1), 공간복잡도는 O(1)이다.





문제출처 - https://leetcode.com/problems/arranging-coins/




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



  문제해석


주어진 배열 nums의 모든 0 값들을 뒤쪽으로 이동시키면서 0이 아닌 값의 순서는 그대로 유지하는 함수를 작성해라.

* nums의 복사본인 새로운 배열을 생성하지 않고 nums배열에서 작업한다

* 전체 연산의 수를 최소화한다




첫번째 방법은 가장 처음으로 0이 나오는 값의 인덱스를 구한다. 그리고 0의 인덱스값 뒤에 오는 요소들 중 처음으로 나오는 0이 아닌 숫자를 0의 인덱스에 넣고 숫자가 있던 자리는 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
class Solution {
    public void moveZeroes(int[] nums) {
        
        int indexOfZero=-1;
        
        //맨처음 0을 찾아서 index값 가져옴
        for(int i=0 ; i<nums.length ; i++){
            if(nums[i]==0){
                indexOfZero=i;
                break;
            }
        }
        
        //0이 없으면 그대로 리턴
        if(indexOfZero==-1return;
        
        //0이 있는곳으로 뒤에서 0이 아닌수를 가져오고 index를 하나 늘린다(반복)
        for(int i=zeroIndex ; i<nums.length ; i++){
            if(nums[i]==0continue;
                nums[indexOfZero]=nums[i];
                nums[i]=0;
                indexOfZero++;
        }
    }
}
cs

시간복잡도는 O(n), 공간복잡도는 O(1)이다. 이 방법은 경우에 따라 불필요한 추가연산을 하게 되는 경우가 있다. 아래 예시를 보자.


만일 nums가 [1, 0, 2, 4, 5, 0]라고 가정해보자. 그럼 연산순서는 아래와 같을 것이다.

[1, 0, 2, 4, 5, 0] -> [1, 2, 0, 4, 5, 0] -> [1, 2, 4, 0, 5, 0] -> [1, 2, 4, 5, 0, 0]

nums[2]에 0을 넣었다가 다시 4로 바꾸고 nums[3]도 0을 넣었다가 다시 5로 바꾼다.





두번째 방법은 배열을 탐색하면서 0이 아닌 숫자들을 앞에서부터 순서대로 집어넣고 그 뒤를 0으로 채우는 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void moveZeroes(int[] nums) {
        
        int index=0;
        
        //0이 아닌 숫자를 찾아서 앞에서부터 하나씩 채운다
        for(int i=0 ; i<nums.length ; i++){
            if(nums[i]!=0){
                nums[index]=nums[i];
                index++;
            }
        }
        
        //index뒤를 전부 0으로 바꾼다
        while(index<nums.length){
            nums[index]=0;
            index++;
        }
    }
}
cs

이렇게 하면 특정 위치의 값을 두번씩 바꾸는 일은 없겠지만 0의 갯수가 많을수록 0을 채워넣는 연산이 중복되는 경우가 생긴다(0을 또다시 0으로 채우는 경우). 이 방법도 동일하게 시간복잡도는 O(n), 공간복잡도는 O(1)이다.


문제출처 - https://leetcode.com/problems/move-zeroes/




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



  문제해석


정수 배열을 입력값으로 받아 해당 배열이 중복값을 포함하고 있는지 판별하라.

아무 값이나 배열 내에서 두번 이상 나타나는 값이 있다면 true를 리턴하고 모든 요소가 유일하다면 false를 리턴해라.







첫번째 방법은 배열을 정렬한 후 앞뒤 값을 비교하는 것이다. 이전에 포스팅한 Single Number 문제의 첫번째 풀이법과 원리가 같다.


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




1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean containsDuplicate(int[] nums) {
        
        Arrays.sort(nums);
        
        for(int i=0 ; i<nums.length-1 ; i++){
            //앞뒤 값이 같은게 나오면 true리턴
            if(nums[i] == nums[i+1]) return true;
        }
        
        //for문을 빠져나와 전체 배열을 다 돌때까지 중복이 없으면 false리턴
        return false;
    }
}
cs


정렬하는데 드는 시간 O(nlogn), 탐색하는데 드는 시간 O(n)으로 시간복잡도는 O(nlogn)이고 추가적인 메모리 사용이 없으므로 공간복잡도는 O(1)이다.





두번째 방법은 Set 자료구조를 이용하는 것이다. Set은 중복된 데이터를 허용하지 않는 집합이다. 만약 nums에 중복된 값이 있다면 nums의 길이와 numset의 사이즈가 다를 것이다.

ex) nums = [3,7,7,8,6] 일 경우 nums.length=5, numSet.size()=4


1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean containsDuplicate(int[] nums) {
        
        Set<Integer> numSet = new HashSet<>();
        
        for(int i=0 ; i<nums.length ; i++){
            numSet.add(nums[i]);
        }
        
        //배열의 길이와 배열의 요소를 모아놓은 집합의 크기가 다르면 true, 같으면 false 리턴
        return nums.length != numSet.size();
    }
}
cs



이 방법은 배열을 한번만 탐색하므로 시간복잡도는 O(n)이지만 numSet이라는 추가적인 공간을 사용하므로 공간복잡도는 O(n)이다.





문제 출처 - https://leetcode.com/problems/contains-duplicate/



+ Recent posts