[LeetCode Top Interview 150]

[문제 링크]

[Graph] 133. Clone Graph

[문제 설명]

• 무방향 그래프의 전체 클론 반환
• 그래프의 각 노드에는 이웃 노드의 값(int)과 목록List[Node]이 포함되어 있음

class Node {
    public int val;
    public List<Node> neighbors;
}

[테스트 케이스 형식]

• 단순화를 위해 각 노드의 값은 노드의 인덱스와 동일함. 예를 들어 첫 번째 노드는 val == 1, 두 번째 노드는 val == 2 그래프는 인접 목록을 사용하여 테스트 케이스에 표시
• 인접 목록은 그래프를 나타내는데 사용되는 순서가 지장되지 않은 목록의 모음. 각 목록은 그래프에 있는 노드의 이웃 집합
• 주어진 노드는 항상 val = 1이 첫번째 노드가 된다. 복제된 그래프에 대한 참조로 지정된 노드의 복사본을 반환해야 함

[예시1]

Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Otput: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

[예시2]

Input: adjList = [[]] Output: [[]] Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

[예시3]

Input: adjList = [] Output: [] Explanation: This an empty graph, it does not have any nodes.

[제약]

• 그래프의 노드 수가 범위 내에 있다. [0, 100].
• 1 <= Node.val <= 100
• Node.val은 각 노드마다 고유하다.
• 그래프에는 반복되는 간선이나 자가 루프가 없다.
• 그래프는 연결되어 있으며 해당 노드부터 모든 노드를 방문할 수 있다.

[내가 생각한 방법]

사실 이 문제는 '복제'가 가장 중요한 키워드인데 처음에 이 노드를 복제하는 방법에 대해 깊게 생각을 안했던 것 같다. 예시 그림을 토대로 다시 문제를 이해해보면 원본 그래프 A의 정점 노드가 4개이면, 복제 그래프 B의 정점 노드도 4개여야 하고 정점 노드의 간선 연결 관계, 인접한 노드도 동일하게 복제가 되어야 한다. 원본 그래프 A이면 안되고, 원본 그래프를 복제한 복제 그래프 B이어야 한다. 방문 여부를 추적하는 visited는 어차피 원본 그래프에도, 복제한 그래프에도 필요하므로 어차피 현재 노드를 체킹하면 함께 추적이 가능할 것 같았다.

[의사 코드]

복제노드 매핑 맵 선언;
노드 방문 stack 선언;
방문 여부 체크 visited 선언;

스택에 node 추가;

반복문(stack이 빌 때까지) {

    현재 노드 = stack에서 꺼내온 값;

    현재 노드가 방문했는지 여부 확인
    방문x 경우, 방문했다고 추가하여 기록하기;

    복제 노드 맵에 현재 노드가 포함되어있는지 확인
    포함x 경우, 현재 노드의 복제본을 추가하기, 이때 현재 노드의 값으로 새로운 노드 생성;

    현재 노드의 모든 이웃 노드 순회
    복제 노드 맵에 이웃 노드가 포함되어있는지 확인
    포함x 경우, 현재 이웃 노드의 복제본을 추가하기, 이때 현재 이웃 노드의 값으로 새로운 노드 생성;

    현재 노드 복제본과 이웃 노드 복제본의 관계 연결 (간선 복제);
    이웃 노드를 stack에 추가하여 다음 방문 노드로 설정;

}

반복문 끝나고, 모든 노드와 간선 연결 관계를 복제한 후에
시작 노드의 복제본을 반환 (복제 그래프의 시작 지점이기 때문);

}

[완성 코드]

시간복잡도: O(V + E), V = 정점 수, E = 간선 수

class Solution {
    public Node cloneGraph(Node node) {

        if (node == null) return null;

        Map<Node, Node> cloneGraph = new HashMap<>();
        Stack<Node> stack = new Stack<>();
        Set<Node> visited = new HashSet<>();

        stack.add(node);

        while (!stack.isEmpty()) {
            Node current = stack.pop();

            if (!visited.contains(current)) {
                visited.add(current);

                if (!cloneGraph.containsKey(current)) {
                    cloneGraph.put(current, new Node(current.val));
                }

                for (Node neighbor : current.neighbors) {
                    if (!cloneGraph.containsKey(neighbor)) {
                        cloneGraph.put(neighbor, new Node(neighbor.val));
                    }

                    cloneGraph.get(current).neighbors.add(cloneGraph.get(neighbor));
                    stack.push(neighbor);
                }
            }
        }

        return cloneGraph.get(node);

    }
}

1) node가 null인 경우는 null 반환 (빈 그래프인 경우 복제할 필요가 없으니까)

2) 원래 노드와 해당 노드의 복제본을 매핑하는 clonedNode를 HashMap으로 선언 3) 그래프 노드를 방문하기 위한 stack 선언 4) visited는 노드의 방문 여부를 추적하는 HashSet으로 선언

5) 시작 노드 node를 stack에 추가하고
6) stack이 빌 때까지 계속 반복 7) stack에서 노드를 하나 꺼내서 current 변수에 할당해줌. 현재 처리 중인 노드를 의미

8) 만약 visited에 현재 노드인 current가 없는 경우에는 처음 방문하는 경우이니까, visited에 current 현재 노드를 추가해서 방문되었음을 표시

9) clonedNode 맵에 현재 노드 current가 없는 경우 (해당하는 노드를 처음 복제하는 경우 확인) 10) clonedNode 맵에 현재 노드 current의 복제본을 추가함. 현재 노드의 값을 사용해서 새로운 노드를 생성해줌

11) 현재 노드 current의 모든 이웃 노드에 대한 반복문 실행 12) clonedNode 맵에 이웃노드 neighbor가 없는 경우 (해당하는 이웃 노드를 처음 복제하는 경우 확인) 13) clonedNode 맵에 이웃노드 neighbor의 복제본을 추가함. 현재 이웃 노드의 값을 사용해서 새로운 노드를 생성해줌

14) 현재 노드 current의 복제본과 이웃 노드 neighbor의 복제본을 연결함. 그래프의 간선 복제 15) 이웃 노드 neighbor를 stack에 추가하여 다음에 방문할 노드로 설정함
위 과정들을 계속 반복해서 그래프의 모든 노드와의 간선 연결 관계를 복제하고 모든 노드와 연결 관계의 복제가 끝나면, 시작 노드 node의 복제본을 반환함 (복제 그래프의 시작 지점이기 때문)

[회고]

항상 강의 볼 땐 흥미로운데 직접 코드로 작성하고 구현할 땐 막막한지..ㅎㅎ 노드 클래스로 DFS를 구현하려니까 어려웠다. 정말 기본적인 원리도 자주 들여다봐야 할 것 같고 꾸준하게 하는 것이 중요할 것 같다는 생각이 드는 요즘이다.

[LeetCode Top Interview 150]

[문제 링크]

[Trie] 208. Implement Trie (Prefix Tree)

[문제 설명]

• trie ("try"로 발음) or prefix tree 는 문자열 데이터셋에서 키를 효율적으로 저장하고 검색하는데 사용되는 트리 데이터 구조
• Trie 클래스 구현
  • Trie() : 개체를 초기화
  • void insert(String word) : 문자열 word를 Trie에 삽입
  • booelan search(String word) : 문자열이 word트라이에 있는지(즉, 이전에 삽입되었는지) 확인하여 있다면 true 반환, 그렇지 않다면 false 반환
  • bollean startsWith(String prefix) : 이전에 삽입된 문자열에 prefix 접두사가 있으면 true 반환, 그렇지 않으면 false 반환

[예시1]

Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, null, true, false, true, null, true]
Explanation Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True

[제약]

• 1 <= word.length, prefix.length <= 2000
• word와 prefix는 영문 소문자로만 구성
• 최대 호출 횟수는 3 * 104 (insert, search and startsWith)

[코드를 작성하기 전에]

일단 수업 내용을 이해하고, 복습하는 차원에서 천천히 코드를 작성해보았다. Trie를 사용하는 가장 중요한 이유는 문자열 검색에 최적화된 자료구조이기 때문이다. 완전한 단어 검색이라면 해시 테이블을 사용하는 것이 더 효율적이라고 한다. (시간 복잡도가 O(1)) 그러나, 트라이 같은 경우 사전 순 정렬이 가능하고, 시간 복잡도는 해시 테이블보다는 조금 느리다.
[시간 복잡도] 접두어 탐색 부분 : 상수 시간 O(p) / 재귀적 탐색 부분 : O(n)
[공간 복잡도]

• 재귀의 깊이는 트라이의 최대 높이나 깊이에 비례
• 트라이의 깊이는 문자열의 최대 길이로 제한되며, 이 최대 깊이를 d라고 할 때 재귀 호출로 인해 공간 복잡도는 O(d)

[작성 코드]

1) Node 클래스

    class Node {

        public Map<Character, Node> children;
        public boolean isEndOfWord;

        public Node() {
            this.children = new HashMap<>();
            this.isEndOfWord = false;
        }
    }

• 문자를 자식 노드로 가지는 children 객체
• 현재 노드가 단어의 끝인지 나타내는 boolean 타입 isEndOfWord 변수

2) Trie 클래스

    private Node root;

    public Trie() {
        this.root = new Node();
    }

• Tire 객체는 새로운 Root 노드 root를 생성
• 이 Root 노드가 모든 문자열의 시작점을 의미한다.

3) insert 메서드

  public void insert(String word) {
      insert(this.root, word);
    }

• Trie에 문자열 word를 삽입하는 메서드 insert
• root 노드부터 시작하여 문자열의 각 문자(Char)를 순회하면서 Trie를 구성한다.

4) insert 메서드 (재귀)

  public void insert(Node node, String word) {

    if (word.length() == 0) {
      node.isEndOfWord = true;
      return;
    }

    final char c = word.charAt(0);
    Node child = node.children.get(c);

    if (child == null) {
      child = new Node();
      node.children.put(c, child);
    }

      insert(child, word.substring(1));
    }

• 재귀 탐색
• 해당 문자에 대한 자식 노드가 없는 경우, 새로운 노드를 생성하고 children 객체에 추가한다.
• 문자열 word의 길이가 0인 경우 해당 노드를 단어의 끝(isEndOfWord)을 true로 표시

5) search 메서드

  public boolean search(String word) {
      return search(this.root, word);
  }

• Trie에 문자열 word를 검색하는 메서드 search
• root 노드부터 시작하여 문자열의 각 문자(Char)를 순회하면서 Trie를 검색

6) search 메서드 (재귀)

  private boolean search(final Node node, final String word) {

    if (word.length() == 0) {
      return node.isEndOfWord;
    }

    char c = word.charAt(0);
    Node child = node.children.get(c);

    if (child == null) {
      return false;
    }

      return search(child, word.substring(1));
    }

• 해당 문자에 대한 자식 노드가 없는 경우, Trie에 해당 문자열이 존재하지 않는 것이므로 false 반환
• 그렇지 않으면, 마지막 노드의 isEndOfWord 값을 반환하여 해당 문자열이 Trie에 있는지 여부 확인

7) startsWith 메서드

    public boolean startsWith(String prefix) {
        return startsWith(this.root, prefix);
    }

• Trie에 접두사 prefix가 있는지 확인하는 메서드 startsWith
• root 노드부터 시작하여 접두사의 각 문자(Char)를 순회하면서 Trie를 검색

8) startsWith 메서드 (재귀)

    public boolean startsWith(String prefix) {
      Node currentNode = this.root;

      for (char c: prefix.toCharArray()) {
        Node child = currentNode.children.get(c);

        if (child == null) return false;

        currentNode = child;
       }
        return true;
      }

• 접두사의 모든 문자가 Trie에 존재한다면 true, 없다면 false 반환

9) 전체 코드

class Trie {
    class Node {

        public Map<Character, Node> children;
        public boolean isEndOfWord;

        public Node() {
            this.children = new HashMap<>();
            this.isEndOfWord = false;
        }
    }


    private Node root;

    public Trie() {
        this.root = new Node();
    }

    public void insert(String word) {
            insert(this.root, word);
        }

        public void insert(Node node, String word) {

            if (word.length() == 0) {
                node.isEndOfWord = true;
                return;
            }

            final char c = word.charAt(0);
            Node child = node.children.get(c);

            if (child == null) {
                child = new Node();
                node.children.put(c, child);
            }

            insert(child, word.substring(1));
        }


    public boolean search(String word) {
            return search(this.root, word);
        }

        private boolean search(final Node node, final String word) {

            if (word.length() == 0) {
            return node.isEndOfWord;
            }

            char c = word.charAt(0);
            Node child = node.children.get(c);

            if (child == null) {
                return false;
            }

            return search(child, word.substring(1));
        }

    public boolean startsWith(String prefix) {
        return startsWith(this.root, prefix);
    }

    private boolean startsWith(final Node node, final String prefix) {
            Node currentNode = this.root;

            for (char c: prefix.toCharArray()) {
                Node child = currentNode.children.get(c);

                if (child == null) return false;

                currentNode = child;
            }
            return true;
        }
}

[회고]

Trie 이론이나 동작 원리 부분은 굉장히 흥미롭고 재밌었는데, 실제로 구현하려니까 어려웠다.. 자료구조, 알고리즘.. 갈 길이 먼 것 같다…

기존의 코드로 테스트를 실행할 경우 분명히 테스트도 통과했다고 뜨고, 상태 코드도 200을 반환하는데 Body의 값이 텅 비어있는 경우가 발생했다.

그렇다고 오류가 발생한 것도 아니었는데 문제는 MockMVC 중 Json Response 검증하는 JsonPath()를 사용할 때이다.

MockHttpServletResponse:
           Status = 200
    Error message = null
          Headers = [Vary:"Origin", "Access-Control-Request-Method", "Access-Control-Request-Headers", X-Content-Type-Options:"nosniff", X-XSS-Protection:"1; mode=block", Cache-Control:"no-cache, no-store, max-age=0, must-revalidate", Pragma:"no-cache", Expires:"0", X-Frame-Options:"DENY"]
     Content type = null
             Body = 
    Forwarded URL = null
   Redirected URL = null
          Cookies = []

사실 나는 나는 jsonPath()를 통해 응답 Response 중 message의 값이 일치하는지를 추가로 검증하고 싶었는데

.andExpect(MockMvcResultMatchers.jsonPath("$.message").value("로그인에 성공하였습니다."));

이 코드를 추가하고, 테스트를 다시 실행하면 이와 같은 에러를 만나게 된다.

java.lang.AssertionError: No value at JSON path "$.message"

    at org.springframework.test.util.JsonPathExpectationsHelper.evaluateJsonPath(JsonPathExpectationsHelper.java:304)
    at org.springframework.test.util.JsonPathExpectationsHelper.assertValue(JsonPathExpectationsHelper.java:99)
    at org.springframework.test.web.servlet.result.JsonPathResultMatchers.lambda$value$2(JsonPathResultMatchers.java:111)
    at org.springframework.test.web.servlet.MockMvc$1.andExpect(MockMvc.java:214)
    at com.zipkimi.user.controller.UserLoginControllerTest.loginSuccessTest(UserLoginControllerTest.java:137)
    at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:77)
    at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.base/java.lang.reflect.Method.invoke(Method.java:568)
    at ... (생략)

그래서 다시 찾아본 결과

기존의 when절 메서드에서 수정이 필요했다!

when(userLoginService.login(request)).thenReturn(successResponse);

• userLoginService의 login 메서드 호출
• request 모의 객체를 매개변수로 넘겨주고
• successResponse라는 응답을 반환

이러한 흐름의 코드이다.

해결 방법 이 코드의 login 메서드에 전달하는 인자를 any()로 변경하는 것이다.

when(userLoginService.login(any(UserLoginRequest.class))).thenReturn(successResponse);

어떠한 객체도 처리할 수 있도록 any()를 통해, 어떤 요청이 들어가든 successResponse를 반환해줄 것이다.

TokenResponse successResponse = TokenResponse.builder().message("로그인에 성공하였습니다.").build();

수정 후 다시 테스트를 실행해보면 다음과 같이 통과하는 것을 확인할 수 있다.

MockHttpServletResponse:
           Status = 200
    Error message = null
          Headers = [Vary:"Origin", "Access-Control-Request-Method", "Access-Control-Request-Headers", Content-Type:"application/json;charset=UTF-8", X-Content-Type-Options:"nosniff", X-XSS-Protection:"1; mode=block", Cache-Control:"no-cache, no-store, max-age=0, must-revalidate", Pragma:"no-cache", Expires:"0", X-Frame-Options:"DENY"]
     Content type = application/json;charset=UTF-8
             Body = {"message":"로그인에 성공하였습니다."}
    Forwarded URL = null
   Redirected URL = null
          Cookies = []

원인은 테스트에서 의도한 대로 이 부분의 객체가 같은 것으로 인식되지 않고 서로 다른 두 개의 객체로 인식을 해서인듯 하다.

when(userLoginService.login(request)).thenReturn(successResponse);

출처 : https://stackoverflow.com/questions/62560356/spring-boot-mockmvctest-mockhttpservletresponse-always-returns-empty-body

출처 : https://stackoverflow.com/questions/65157415/mockmvc-jsonpath-response-has-empty-body

[LeetCode Top Interview 150]

[문제 링크]

[Binary Search Tree (BST)] 530. Minimum Absolute Difference in BST

[문제 설명]

Binary Search Tree (BST)의 root가 주어졌을 때, 트리에 있는 두 개의 다른 노드 간의 최소 절대 차이를 반환하여라

[예시1]

Input: root = [4,2,6,1,3] Output: 1

[예시2]

Input: root = [1,0,48,null,null,12,49] Output: 1

[제약]

The number of nodes in the tree is in the range [2, 104]. 0 <= Node.val <= 105

[내가 생각해본 방법]

이진 탐색 트리(BST)는 트리를 구성하는 노드의 자식이 최대 두 개인 트리를 의미한다. 사실 아직 이해가 잘 안가는 부분들이 많아서.. BST의 특징을 다시 정리하고, 문제 해결 방법과 다른 사람들의 풀이를 찾아보고 이해하려고 노력했다.
BST의 특별한 규칙은 왼쪽 하위 노드들은 root 노드보다 값이 작고, 오른쪽 하위 노드들은 root 노드보다 값이 크거나 같다는 것이다.
그렇다면 왼쪽 하위 노드 중에서 가장 큰 값이 root 노드의 이전 값에 해당될 것이고, 오른쪽 하위 노드 중에서 가장 작은 값이 root 노드의 다음 값에 해당될 것이다.
root 노드의 이전 값 : 왼쪽 하위 노드 중 가장 큰 값 root 노드의 다음 값 : 오른쪽 하위 노드 중에서 가장 작은 값
이 특징을 잘 이해하고 문제에 접근하는 것이 관건이라고 생각했다.
최대값과 최소값 구하기 root 노드부터 특정 노드의 오른쪽 노드가 없다면, 해당 노드가 해당 트리의 최대가 된다. 반대로 root 노드부터 특정 노드의 왼쪽 노드가 없다면 해당 노드가 해당 트리의 최소가 된다.

[의사 코드]

    최소값 차이 = Integer.최대값;
    이전 노드 = null; 

    최종 결과 (트리노드 root) {
        최소값 차이 찾는 재귀 함수(root);
        return 최소값;
    }

    void 최소값 차이 찾는 재귀 함수(트리노드 root)
        if(root가 존재한다면)
            최소값 차이 찾는 재귀 함수(왼쪽 서브 트리 순회);
        if(이전 노드가 존재한다면)
            최소값 = 최소값 비교(최소값, 절대값(현재 노드값 - 이전 노드값));
            이전 노드 = root;
            최소값 차이 찾는 재귀 함수(오른쪽 서브 트리 순회);
        return ;

[작성 코드]

class Solution {

    int minDiff = Integer.MAX_VALUE;
    TreeNode prev = null;

    public int getMinimumDifference(TreeNode root) {
        find(root);
        return minDiff;
    }

    public void find(TreeNode root) {
        if (root != null) {
            find(root.left);
            if (prev != null)
                minDiff = Math.min(minDiff, Math.abs(root.val - prev.val));
            prev = root;
            find(root.right);
        }
        return;
    }
}

[LeetCode Top Interview 150]

[문제 링크]

[Binary Search] 153. Find Minimum in Rotated Sorted Array

[문제 설명]

오름차순으로 정렬된 길이의 배열이 회전 정렬된다고 가정한다. 예를 들어 nums = [0,1,2,4,5,6,7]

• [4,5,6,7,0,1,2] 4번 회전한 경우
• [0,1,2,4,5,6,7] 7번 회전한 경우 고유 요소 nums 배열의 정렬된 회전 배열이 주어지면, 배열의 최소 요소를 반환한다. 시간 복잡도는 O(logN)을 가진다.

Example 1 Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2: Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3: Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

[처음에 내가 생각해 본 방법]

이전에 풀었던 Peak 요소 찾기랑 비슷하다. 이진 탐색 알고리즘을 활용하여 푸는 문제이고, 162번 문제와 다른 점은 최소값을 찾아야한다는 것 정도? 저번 문제를 먼저 풀어서 상대적으로 덜 어려운 느낌이었다..! 대신 최소값 대신 회전을 몇 번 했는지 횟수를 구하거나 하는 다른 조건이 추가되었다면 더 어려웠을 것 같다. 어떤 원리일까 더 생각을 해봤는데 이진 탐색의 경우에는 배열의 중간값을 기준으로 예시 배열 중 [3,4,5,1,2] 같은 경우 [3,4,5][1,2]와 같이 부분 배열로 나뉘게 되는데 이땐 정렬이 되어있는 상태여서 조금 더 수월하게 최소값을 찾을 수 있는 것 같다..! 주어진 배열의 중간 값을 먼저 찾고, 먼저 중간값과 마지막값의 대소에 따라 점점 범위를 조정해나가는 식으로.. 살짝 다르지만 원리는 비슷하게 생각해보았다. 점점 범위가 좁혀져서 start == end의 값이 같아지는 경우, 그 때가 바로 찾아야하는 최솟값의 인덱스이므로 같으면 반복문이 종료된다.

[의사 코드]

    //인덱스는 0부터 시작하므로 
    // (가장 왼쪽의 시작값과 가장 오른쪽의 마지막값 구하기)
    시작값=0, 마지막=배열 길이-1; 

    while(시작값<마지막값)

        //중간값 구하기
        중간값 = 시작값 + (마지막값 - 시작값) / 2;

          // 만약 현재 중간값이 마지막 값보다 작다면?
        if 배열[중간] 인덱스 값 < 배열[마지막] 인덱스 값
            마지막값=중간값;
        else
            시작값=중간값+1;

     return 배열[시작값];

[실제 구현 코드]

class Solution {
    public int findMin(int[] nums) {

        int start = 0, end = nums.length-1;

        while(start < end){

            int mid = start + (end - start) / 2;

            if(nums[mid] < nums[end]){
                end = mid;
            }else {
                start = mid+1;
            }

        }

        return nums[start];
    }
}

nums = [3,4,5,1,2]

1) start = 0; end = 배열의 길이-1이니까 4 2) 0<4이므로 반복문 실행 3) mid = 2; 4) nums[2] = 5, nums[4]=2; 5) 5>2이므로, start = 3; (end = 4;) 6) 3<4이므로 반복문 실행 7) mid = 3; 8) nums[3] = 1, nums[4]=2; 9) 1<2이므로, end = 3; 10) stat =3 / end = 3으로 두 값이 같으므로 반복문 종료, 찾은 인덱스 3 값 return (배열의 3번째 값인 1 리턴);

[똑같이 고려해봐야 할 사항]

이번 문제도 비슷하게 중간 값을 구할 때 문제가 생길 수 있어서 (만약에 (start+end) 값이 int 값의 범위(-2,147,483,648 ~ 2,147,483,647)보다 크다면, 음수 값으로 오버플로우 되어 2로 나누면 mid 값이 최종적으로 음수가 되는 문제)

int mid = start + (end - start) / 2

이와 같이 중간값을 구하도록 작성해보았다.

[LeetCode Top Interview 150]

[문제 링크]

[Binary Search] 162. Find Peak Element

[문제 설명]

Peak 요소는 양 옆의 인접 요소보다 큰 요소를 뜻한다. (가장 꼭대기 요소) 0 인덱스부터 주어지는 nums 배열에서 Peak 요소를 찾고, 해당 인덱스를 반환하여라. 배열에 여러 Peak가 있는 경우 Peak 중 하나의 인덱스를 반환한다. 시간 복잡도는 O(logN)을 가진다.

Example 1 Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2.

Example 2: Input: nums = [1,2,1,3,5,6,4] Output: 5 Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

[처음에 내가 생각해 본 방법]

제목에서 알 수 있듯 이진 탐색 알고리즘을 활용하여 푸는 문제였다. 주어진 배열의 중간 값을 먼저 찾고, 중간 값과 찾아야 하는 값의 대소에 따라 점점 범위를 조정해나가는 식으로 생각해보았다. start 값이 커지고, end 값이 작아지면서 점점 범위가 좁혀져서 start == end의 값이 같아지는 경우, 그 때가 바로 찾는 도출 값이므로 같으면 반복문이 종료된다.

[이해를 위해 찾아본 시각자료들]

출처1 : https://yjym33.tistory.com/24 출처2 : https://roytravel.tistory.com/331

[의사 코드]

    //인덱스는 0부터 시작하므로 
    // (가장 왼쪽의 시작값과 가장 오른쪽의 마지막값 구하기)
    시작값=0, 마지막=배열 길이-1; 

    while(시작값<마지막값)

        //중간값 구하기
        중간값 = (시작값+마지막값)/2;

          // 만약 현재 중간값이 오른쪽보다 작다면?
        if 배열[중간] 인덱스 값 < 배열[중간 오른쪽] 인덱스 값
            시작값=중간값+1;
        else
            마지막값=중간값;

     return 시작값;

[실제 구현 코드]

class Solution {
    public int findPeakElement(int[] nums) {

        int start=0, end=nums.length-1;

        while(start<end){

            int mid = (start + end) / 2; 

            if(nums[mid] < nums[mid+1]){
                start = mid+1;
            }
            else{
                end=mid;
            }
        } 
        return start;
    }
}

nums = [1,2,3,1]

1) start = 0; end = 배열의 길이-1이니까 3 2) 0<3이므로 반복문 실행 3) mid = 1; 4) nums[1] = 2, nums[2]=3; 5) 2<3이므로, start = 2; (end = 3;) 6) 2<3이므로 반복문 실해 7) mid = 2; 8) nums[2] = 3, nums[3]=1; 9) 3>1이므로, end = 2; 10) stat =2 / end = 2으로 두 값이 같으므로 반복문 종료, 찾은 값 2 return;

[고려해봐야 할 사항]

사실.. 중간 값을 구할 때 쉽게 찾으려고 간단한 식을 사용했는데, 문제를 풀고 나서 찾아보니까 만약에 (start+end) 값이 int 값의 범위(-2,147,483,648 ~ 2,147,483,647)보다 크다면, 음수 값으로 오버플로우 되어 2로 나누면 mid 값이 최종적으로 음수가 되는 문제가 생길 수도 있다고 한다.

int mid = (start + end) / 2; 

그래서 만약 (start+end) 값이 int 값의 범위를 넘어가는 경우에는 아래와 같이 중간 값을 구하는 것이 좋다고 한다.

int mid = start + (end - start) / 2

[LeetCode Top Interview 150]

[문제 링크]

[Stack] 150. Evaluate Reverse Polish Notation

[문제 설명]

역 폴란드 표기법(=후위 표기법) tokens의 표현식을 나타내는 문자열 배열이 주어진다. 이 표현의 값을 구하여라(계산). 표현식의 값을 나타내는 integer를 반환한다.
참고사항

• 유효한 연산자는 '+', '-', '*'및 입니다 '/'.
• 각 피연산자는 정수이거나 다른 표현식일 수 있습니다.
• 두 정수 사이의 나눗셈은 항상 0을 향해 잘립니다 .
• 0으로 나누는 일은 없을 것입니다.
• 입력은 역방향 폴란드어 표기법으로 유효한 산술 표현식을 나타냅니다.
• 답과 모든 중간 계산은 32비트 정수로 표현될 수 있습니다.

Example 1: Input: tokens = ["2","1","+","3","*"] Output: 9 Explanation: ((2 + 1) * 3) = 9

Example 2: Input: tokens = ["4","13","5","/","+"] Output: 6 Explanation: (4 + (13 / 5)) = 6

Example 3: Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22

[처음에 내가 생각해 본 방법]

처음에는 문자열 배열 tokens의 값들이 모두 stack에 담겨야 한다고 생각하고, 배열 3개를 만들어서 for문으로 tokens의 값들을 반복문을 돌리면서 그 안에 반복문과 조건문을 통해서.. 이런 식으로 접근을 했었는데 문제를 풀다보니까 꼭 그럴 필요가 없겠다는 생각이 들었다. 조건에 사칙연산이 꼭 stack에 들어가야 한다는 조건이 없었고, 출력 결과로 연산의 결과를 도출하면 되는 것이니까 말이다. 처음에 작성한 코드는 그래서 복잡하고, 실행했을 때 컴파일 오류가 뜨거나, 통과되지 못했다.

[시행 착오 코드1]

class Solution {
    public int evalRPN(String[] tokens) {

        ArrayList<String> a = new ArrayList();
        ArrayList<String> b = new ArrayList();
        ArrayList<String> c = new ArrayList();

        String operA = "";
        String operC = "";
        int result = 0;

        for(int i = 0; i < tokens.length; i++){

            if(tokens[i].contains("+") || tokens[i].contains("-") 
                || tokens[i].contains("*") || tokens[i].contains("/")){

                // tokens 값 중 사칙연산을 배열에 추가
                if(b.isEmpty()){
                    b.add(tokens[i]);
                    System.out.println("b" + b);
                }else {
                    ;
                }
            }
               if(c.isEmpty()){
                    c.add(tokens[i]);
                    System.out.println("c" + c);
                }else if(a.isEmpty()){
                    a.add(tokens[i]);
                    System.out.println("a" + a);
                }else{
                    ;
                } 

                if(b.size() == 1 || c.size() == 1 || a.size() == 1){

                    int A = 0;
                    int C = 0;

                    if(b.size() == 1){
                        if(b.get(0).contains("+")){
                            C = Integer.parseInt(c.get(0));
                            A = Integer.parseInt(a.get(0));
                            result = C+A;
                            b.remove(b.size()-1);
                            c.remove(operC);
                            a.remove(operA);
                        }else if(b.get(0).contains("-")){
                            C = Integer.parseInt(c.get(0));
                            A = Integer.parseInt(a.get(0));
                            result = C-A;
                            b.remove(b.size()-1);
                            c.remove(operC);
                            a.remove(operA);
                        }else if(b.get(0).contains("*")){
                            C = Integer.parseInt(c.get(0));
                            A = Integer.parseInt(a.get(0));
                            result = C*A;
                            b.remove(b.size()-1);
                            c.remove(operC);
                            a.remove(operA);
                        }else if(b.get(0).contains("/")){
                            C = Integer.parseInt(c.get(0));
                            A = Integer.parseInt(a.get(0));
                            result = C/A;
                            b.remove(b.size()-1);
                            c.remove(operC);
                            a.remove(operA);
                        }else{
                            c.remove(operC);
                            a.remove(operA);  
                        }
                    }
                }
        }

        return result;


    }
}

[그렇다면 어떻게? 처음부터 접근을 다시 해보자]

내가 문제를 잘못 이해했었구나, 인지하고 그때부터 접근 방법을 다시 고민하기 시작했다. tokens에 포함된 사칙연산에 대한 조건문이 필수적으로 있어야겠다는 생각. Stack의 속성? 특수한 성격을 활용해서 풀어야겠다는 생각.. 등이 정리되면서 어느 정도 이렇게 풀면 되겠구나 싶은 감이 잡히면서 Stack을 활용해서 다시 풀어봐야겠다고 생각했다. 그래서 접근부터 다르게 다시 작성해보았다. 몇 번의 과정을 거쳐 탄생한 제출 코드는 다음과 같다.

[최종 제출 코드]

class Solution {
    public int evalRPN(String[] tokens) {

        Stack<Integer> stack = new Stack();
        String operator = "+-*/" ;
        for(String t : tokens){

            if(operator.contains(t) && !stack.isEmpty()){

                int a = stack.pop();
                int b = stack.pop();
                int result = 0;

                if(t.equals("+")){
                    result = b+a;
                }else if(t.equals("-")){
                    result = b-a;
                }else if(t.equals("*")){
                    result = b*a;
                }else {
                    result = b/a;
                }
                stack.push(result);
            }else{
                stack.push(Integer.parseInt(t));
            }
        }
        return stack.pop();

        }
}

1) Stack 선언 2) operator 연산자들을 따로 변수로 선언 3) tokens 문자열 배열을 for문을 통해 반복문 돌리면서 stack에 추가하는데 4) 만약, operator에 tokens 값이 포함이 되어있고 && stack이 비어있지 않다면, stack에서 pop() 함수를 통해 현재 stack 중에 가장 마지막에 삽입된 요소를 꺼내서 차례로 a,b 변수에 담아줌. 그리고 결과를 담을 result 변수 선언 및 초기화 5) 만약 tokens 배열의 값이 연산자 중 "+"이면, b+a 값을 result 변수에 할당 / 이런 식으로 각 연산자들에 대한 조건문을 분기해줌 *여기서 b 변수를 먼저 써주는 이유 : tokens = ["2","1","+","3",""] 값일 때 stack = [2, 1] 이 삽입되고, top에 있던 1이 a / 맨 처음 담긴 2는 b가 됨. (a=1, b=2) / 연산자는 "+"이므로, 2+1 = 3이 된다. ** 6) 연산자에 대한 조건문이 끝나면, result 값을 다시 stack에 push 해줌 (2+1 연산값 3을 stack에 삽입함) 7) 그럼, 이전에 tokens 배열에 이미 존재하고 있던 숫자 3과, 새롭게 stack에 삽입된 3에 대한 연산이 또 이뤄짐. 이번엔 연산자가 "x"이므로 3x3=9 8) 연산자에 대한 조건문이 끝나면, result 값을 다시 stack에 push 해줌 (3*3 연산값 9를 stack에 삽입함) 9) 반복문이 다 돌고 반환하는 return 값은 stack.pop(); => 결국 최종 마지막 값은 9이 반환된다. 10) 만약, operator에 tokens 값이 포함이 되어있지 않고 && stack이 비어있다면, String타입의 숫자를 int타입으로 변환하여 stack에 삽입해줌.

[LeetCode Top Interview 150]

[문제 링크]

[Stack] 155. Min Stack

[문제 설명]

push, pop, top, minimum element 검색을 지원하는 stack을 설계하여라.

• MinStack() : stack 개체를 초기화
• void push(int val) : 요소를 val stack에 푸시
• void pop() : stack 맨 위에 있는 요소를 제거
• int top() : stack의 최상위 요소를 가져옴
• int getMin() : stack에서 최소 요소를 검색

Example 1:
Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
Output [null,null,null,null,-3,null,0,-2]
Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

[내가 생각해 본 방법]

직접 Stack을 정의하는 것도 방법이겠지만, 수업 시간에 배운 ArrayList를 활용하는 방법으로 문제를 풀어보면 좋을 것 같다는 생각을 했다. 2개의 ArrayList를 선언해서 풀면 효과적으로 풀어볼 수 있을 것 같았다.

[시행 착오 코드1]

class MinStack {

    ArrayList<Integer> stack;
    ArrayList<Integer> minStack;

    public MinStack() {
        stack = new ArrayList<>();
        minStack = new ArrayList<>();
    }

    public void push(int val) {

        stack.add(val);
        if(minStack.isEmpty()){
            minStack.add(val);
        }
    }

    public void pop() {
        stack.remove(stack.size());
        minStack.remove(stack.size());
    }

    public int top() {
        return stack.get(stack.size());

    }

    public int getMin() {
        return minStack.get(minStack.size());
    }
}

1) stack과 minStack을 선언하고 2) MinStack() : 생성자에서 각각 초기화해준다. 3) void push(int val) : stack에 매개변수 val 값을 추가하고, 만약에 minStack에 값이 없다면 minStack에도 값을 추가해준다. 4) void pop() : stack의 최상단(마지막) 값을 제거하고, minStack의 최상단(마지막) 값도 제거한다. 5) int top() : stack의 최상단(마지막) 값을 가져온다. 6) int getMin() : minStack의 최상단(마지막) 값을 가져온다.

처음 작성했던 코드인데, 최상단(마지막) top 값을 구하기 위해서는 인덱스가 0부터 시작하므로, size에서 -1을 해줘야 한다는 것을 간과하고 있었다. 그리고 pop() 메서드에서도 minStack의 top 값을 제거해줘야 하는데, stack의 값을 제거하고 있었다. 그리하여 다시 수정한 코드

**[최종 제출 코드] : 추가 개선 **

추가적으로 해야할 부분들

• 시간 복잡도, 공간 복잡도 개선하기
• 다른 사람들이 풀이한 다양한 코드 확인 해보기

class MinStack {

    ArrayList<Integer> stack;
    ArrayList<Integer> minStack;

    public MinStack() {
        stack = new ArrayList<>();
        minStack = new ArrayList<>();
    }

    public void push(int val) {

        stack.add(val); //stack에 값 추가
        if(minStack.isEmpty()){ //minStack이 비어있다면,
            minStack.add(val);  //minStack에 val 요소 값 추가
        }else   //minStack에 이미 값이 있다면,
            minStack.add(Math.min(minStack.get(minStack.size()-1),val));  
            //Math 함수를 사용하여 이미 존재하는 minStack의 top의 값을 꺼내고, val 요소와 비교하여, 최소값을 minStack에 넣어줌
    }

    public void pop() {
        stack.remove(stack.size()-1);   //stack의 top 값 제거
        minStack.remove(minStack.size()-1); //minStack의 top 값 제거
    }

    public int top() {
        return stack.get(stack.size()-1); //stack의 top 값 가져옴
    }

    public int getMin() {
        return minStack.get(minStack.size()-1); //minStack의 top 값 가져옴
    }
}

[LeetCode Top Interview 150]

[문제 링크]

[Two Pointers] 125. Valid Palindrome

[문제 설명]

모든 대문자를 소문자로 변환하고 영숫자가 아닌 문자를 모두 제거한 후 앞뒤로 동일하게 읽는 경우 구문은 회문 영숫자 문자에는 문자와 숫자가 포함 주어진 문자열이 회문이면 True를 반환하고 , 그렇지 않으면 False 반환 여기서 회문이란 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters)을 뜻한다.

[예시1]

Input: s = "A man, a plan, a canal: Panama"
 출력: true
 설명: "amanaplanacanalpanama"는 회문입니다.

[예시2]

입력: s = "race a car"
 출력: false
 설명: "raceacar"는 회문이 아닙니다.

[예시3]

입력: s = " "
 출력: true
 설명: s는 영숫자가 아닌 문자를 제거한 후의 빈 문자열 ""입니다. 
빈 문자열은 앞뒤로 동일하게 읽으므로 회문입니다.

[제약]

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters. (s는 인쇄 가능한 ASCII 문자로만 구성)

[어떻게 풀지 고민해보기]

먼저 필요한 부분 정리해보기
1) 모든 대문자를 소문자로 변환하는 작업 → 대문자에서 소문자로 변환해주는 함수가 필요할 것 2) 영숫자가 아닌 문자를 모두 제거하는 작업 → 정규식이 필요할 것이다. 3) 소문자+영숫자 아닌 문자 제거한 문자열이 회문인지 검증하는 작업
1번과 2번에 대한 접근 방법은 문제를 처음 본 순간 감이 잡혔지만, 3번을 구체적으로 어떻게 풀어 나갈 지가 이 문제를 해결하는 데 있어서 가장 중요한 요소인 것 같았다.

[내가 생각해 본 방법들]

방법1 1번) 첫 문자와 마지막 문자를 비교 2번) 첫 문자+1과 마지막 문자-1을 비교
… 끝과 끝, 그 다음과 다음… 서로 대칭되는 문자열을 반복적으로 비교해서 회문이면 true, 아니면 false?
방법2 문자열을 절반으로 자름 변수 left에는 첫글자, 변수 right에는 마지막글자 이런 식으로 하나씩 단어를 쪼개 담아서 비교하는 방법..은 뭔가 배열에까지 접근해야 할 것 같은 느낌이 들고 복잡해질 것 같았다.
방법3 문자열이므로.. 글자수 개수(길이)를 가지고, 2로 나뉘면 → 짝수 / 아니면 홀수로 나눠서 뭔가 조건을 판단하여 처리하기?

내가 접근해볼 수 있는 방법 중에 방법 1이 해볼 만 한 것 같아서 도전해봤다. 아래는 시행 착오 코드들부터 최종 Accepted된 제출 코드까지이다.

[시행 착오 코드1]

class Solution {

    public boolean isPalindrome(String s) {

        // 대문자를 소문자로 변환
        s = s.toLowerCase();
        System.out.println("s toLowerCase = " + s);

        // 영숫자가 아닌 문자를 모두 제거
        String match = "[^\uAC00-\uD7A30-9a-zA-Z]";
        s = s.replaceAll(match, "");
        System.out.println("s replaceAll = " + s);

        int j = 1;

        // 문자열의 첫 글자
        char first = s.charAt(0);
        // 문자열의 마지막 글자
        char last = s.charAt(s.length() - j);

        String palindrome = "";

        for (int i = 0; i < s.length(); ) {
            if (first == last) {

                i++;
                j++;

                first = s.charAt(i);
                last = s.charAt(s.length() - j);

                palindrome = "palindrome";
            } else {
                palindrome = "isNotpalindrome";
            }
        }

        return palindrome == "palindrome";

    }
}

1) 모든 대문자를 소문자로 변환하기 위하여 Java String 관련 함수 중, toLowerCase() 함수를 사용하였다. 2) 영문자가 아닌 문자를 모두 제거하기 위하여 정규식을 사용하였다. 3) charAt 함수를 통해 문자열의 첫 글자와 마지막 글자를 구하고, for 반복문을 통해 두 글자가 같은지 비교해주었다.

• 사실 정규식과 charAt 함수는 구글 검색을 참고했다.

[시행 착오 코드2] - 그나마 근접하게 다가갔다고 생각한 코드1

class Solution {

    public boolean isPalindrome(String s) {

        // 1. 대문자를 소문자로 변환
        s = s.toLowerCase();

        // 2. 영숫자가 아닌 문자를 모두 제거
        String regex = "[^A-Za-z0-9]";
        s = s.replaceAll(regex, "");
        System.out.println("s = " + s);

        String palindrome = "";
        int palindromeYesCnt = 0;
        int palindromeNoCnt = 0;

        for (int i = 0, j = 1; i < s.length() & j < s.length(); ) {

            // 문자열의 첫 글자 (0부터 시작)
            char first = s.charAt(i);
            // 문자열의 마지막 글자 (문자열 길이 - 1)
            char last = s.charAt(s.length() - j);

            // 문자열의 첫 글자 == 문자열의 마지막 글자
            // 문자열의 두번째 글자 == 문자열의 마지막에서 첫번째 글자 (끝에서 두번째..)
            // for 반복문에 따라 first와 last 문자가 같은 경우
            if (first == last) {
                //flag를 yes로 정의
                palindrome = "yes";
                //yes flag의 개수
                palindromeYesCnt = palindrome.length();

            } else if (first != last) {
                //flag를 no로 정의
                palindrome = "no";
                //no flag의 개수
                palindromeNoCnt = palindrome.length();

            }
            j++; //j 증가
            i++; //i 증가
        }

        // palindromeYesCnt가 0 초과, palindromeNoCnt가 0일때 true를 반환
        // 아닌 경우 false 반환
        if(palindromeYesCnt > 0 && palindromeNoCnt == 0){
                return true;
        }else {
            return false;
        }
    }

}

[시행 착오 코드3] - 그나마 근접하게 다가갔다고 생각한 코드2

class Solution {

    public boolean isPalindrome(String s) {

        // 1. 대문자를 소문자로 변환
        s = s.toLowerCase();

        // 2. 영숫자가 아닌 문자를 모두 제거
        String regex = "[^A-Za-z0-9]";
        s = s.replaceAll(regex, "");
        System.out.println("s = " + s);

        String palindrome = "";
        int palindromeYesCnt = 0;
        int palindromeNoCnt = 0;

        for (int i = 0, j = 1; i < s.length() & j < s.length(); ) {

            // 문자열의 첫 글자 (0부터 시작)
            char first = s.charAt(i);
            // 문자열의 마지막 글자 (문자열 길이 - 1)
            char last = s.charAt(s.length() - j);

            // 문자열의 첫 글자 == 문자열의 마지막 글자
            // 문자열의 두번째 글자 == 문자열의 마지막에서 첫번째 글자 (끝에서 두번째..)
            // for 반복문에 따라 first와 last 문자가 같은 경우
            if (first == last) {
                //flag를 yes로 정의
                palindrome = "yes";
                //yes flag의 개수
                palindromeYesCnt = palindrome.length();

            } else if (first != last) {
                //flag를 no로 정의
                palindrome = "no";
                //no flag의 개수
                palindromeNoCnt = palindrome.length();

            }
            j++; //j 증가
            i++; //i 증가
        }

        // palindromeYesCnt가 0 초과, palindromeNoCnt가 0일때 true를 반환
        // 아닌 경우 false 반환
        if(palindromeYesCnt > 0 && palindromeNoCnt == 0){
        return true;
                // s가 "" 문자열일 때 || s의 길이가 1일 때
        }else if(s == "" || s.length() == 1){
                return true;
        }else {
            return false;
        }
    }

}

테스트 케이스에 palindrome sentence examples을 추가해서 돌릴 땐 Accepted가 낫지만..

palindrome sentence examples "Mr. Owl ate my metal worm", "Do geese see God?" "Was it a car or a cat I saw?"

Submit 제출하고 나면 Output Limit Exceeded 발생 — 예상보다 많은 출력이 발생할 경우 / 무한 루프가 돌 때 발생하는 에러라고 한다.

이전에 작성했던 코드들을 테스트 할 때, for문에서 변수 i나 j가 증가되지 않는 등의 문제가 발생했던 것을 생각해보면 반복문에서 무한 루프가 도는가보다.. 하고 유추했다.

그래서 가장 중점적으로 개선했던 부분은 for 반복문이었다. 뭔가 이중 반복문을 사용하지 않아도 될 것 같아서 섞어서 썼던 것이 화근이 된 것 같아서 이중 반복문으로 코드를 수정하였다.

[최종 완성 코드] : 추가 개선 / 주석 정리

• 소요 시간 : 약 5시간 20분
• 추가적으로 해야할 부분들
  • 시간 복잡도, 공간 복잡도 개선하기
  • 다른 사람들이 풀이한 다양한 코드 확인 해보기

class Solution {

    public boolean isPalindrome(String s) {

        s = s.toLowerCase();
        s = s.replaceAll("[^A-Za-z0-9]", "");

        String palindrome = "";
        int palindromeYesCnt = 0;
        int palindromeNoCnt = 0;

        for (int i = 0; i < s.length(); i++) {

            for (int j = i + 1; j < s.length(); j++) {
                char first = s.charAt(i);
                char last = s.charAt(s.length() - j);
                if (first == last) {
                    palindrome = "yes";
                    palindromeYesCnt = palindrome.length();
                } else if (first != last) {
                    palindrome = "no";
                    palindromeNoCnt = palindrome.length();
                }
                i++;
            }
        }

        if (palindromeYesCnt > 0 && palindromeNoCnt == 0) {
            return true;
        } else if(s == "" || s.length() == 1){
                return true;
        } else {
            return false;
        }
    }

}

[LeetCode Top Interview 150]

[문제 링크]

[Array / String] 26. Remove Duplicates from Sorted Array

[문제 설명]

오름차순으로 정렬된 정수 배열이 주어지면, 각 요소가 한 번씩만 나타나도록 배열에서 중복 값을 제자리에서 제거 순서는 동일하게 유지되어야 한다.
단, nums의 첫 번째 요소가 처음 nums에 있었던 순서대로 포함해야 한다.

[예시1]

입력: nums = [1,1,2]
 출력: 2, nums = [1,2,_]
 설명: 함수는 k = 2를 반환해야 하며 nums의 처음 두 요소는 각각 1과 2입니다.
반환된 k 외에 무엇을 남겨두는지는 중요하지 않습니다(따라서 밑줄로 표시됩니다). 

[예시2]

입력: 숫자 = [0,0,1,1,1,2,2,3,3,4]
 출력: 5, 숫자 = [0,1,2,3,4,_,_,_,_, _]
 설명: 함수는 k = 5를 반환해야 하며, nums의 처음 5개 요소는 각각 0, 1, 2, 3, 4입니다.
반환된 k 외에 무엇을 남겨두는지는 중요하지 않습니다(따라서 밑줄로 표시됩니다).

[제약]

• 1 <= nums.length <= 3 * 104
• 100 <= nums[i] <= 100
• nums 내림차순으로 정렬되지 않음.

[어떻게 풀지 고민해보기]

사실 문제 자체를 이해하는데 꽤 오랜 시간이 소요됐다. 중복 값을 완전히 다 제거하고 깨끗하게 배열을 출력해야 되는 거라고 생각했었는데 예시를 보니까 그게 아니었던 것이다. 그래서 다시 생각을 해봤다.

[접근 방법?]

먼저, 배열이 오름차순으로 정렬이 되어있으니까.. 예를 들어서 nums 배열의 값이 [0, 1, 1, 2, 2, 2, 3] 일 경우에 각 배열의 인덱스를 비교하여 중복된 값인지 확인해봐야겠다고 생각했다. nums[0]과 nus[1] (배열의 인덱스 0번, 1번)의 값을 비교하고, nums[1]과 nums[2]의 값을 비교하고.. 이런 식으로 말이다.
0과 1은 중복되지 않으니까 패스 1과 1은 중복이 발생하므로 어떤 처리가 필요 1과 2는 중복되지 않으니까 패스.. 이런 느낌으로 풀어가야 하지 않을까? 싶었다. if문과 for문을 먼저 사용해보자

[최종 제출 코드]

class Solution {
    public int removeDuplicates(int[] nums) {
        int r=1;
        for(int i=1; i<nums.length; i++){ 
              if(nums[i-1] != nums[i]){
                nums[r]=nums[i];
                r++;
            }
        }
        return r;
    }
}

[풀이] 초기 배열 nums = [0, 1, 1, 2, 2, 2, 3]

i=1 / r= 1 | [0, 1, 1, 2, 2, 2, 3] | true / r=2 i=2 / r= 2 | [0, 1, 1, 2, 2, 2, 3] | false / r=2 i=3 / r= 2 | [0, 1, 1, 2, 2, 2, 3] -> [0, 1, 2, 2, 2, 2, 3] | true / r=3 i=4 / r= 3 | [0, 1, 2, 2, 2, 2, 3] | false / r=3 i=5 / r= 3 | [0, 1, 2, 2, 2, 2, 3] | false / r=3 i=6 / r= 3 | [0, 1, 2, 2, 2, 2, 3] -> [0, 1, 2, 3, 2, 2, 3] | true / r=4
최종적으로 r은 4 리턴 / 중복이 제거된 최종 배열 [0, 1, 2, 3, 2, 2, 3] 최종 배열에서 길이 4만큼 출력이 된다. [0, 1, 2, 3]

  <form role="form" th:action="@{/total/add}" th:object="${boardForm}" method="post">

<!-- moviesForm과 booksForm 객체 생성 -->
<input type="hidden" th:field="*{moviesForm}" />
<input type="hidden" th:field="*{booksForm}" />

th:object를 boardForm으로 명시하고 hidden input 박스로 moviesForm, booksForm 객체를 따로 생성해줬었는데 계속 해서 오류가 발생했다.

typeMismatch 에러 등등

혹시 th:object 속성을 두 개씩 줄 수는 없나? 하고 찾아보던 중에 stack overflow 글을 발견했다.

https://stackoverflow.com/questions/16122257/how-to-pass-two-objects-to-use-in-a-form-using-thymeleaf

[수정 후]

  <form role="form" th:action="@{/total/add}" method="post">

th:object 속성을 명시하지 않고, input 태그마다 어떤 객체인지 명시를 잘 해주면 된다는 것!!

th:field="*{boardForm.type}"
th:field="*{moviesForm.type}"
th:field="*{booksForm.type}"

덕분에 에러 지옥에서 벗어날 수 있었다.

"Error creating bean with name 'jwtTokenProvider': Injection of autowired dependencies failed; nested exception is java.lang.IllegalArgumentException: Could not resolve placeholder 'jwt.secret.key' in value "${jwt.secret.key}""

이 에러가 나서 애를 먹었다.

뭐가 문제일까 계속 살펴보고 찾아보던 와중에

docker-compose 세팅을 하면서 application.yml에 profile 설정한 것이 문제임을 알아냈다.

on-profile의 dev를 삭제하고 다시 실행하니 오류 없이 실행되는 것을 확인할 수 있었다.

참고 : https://shanepark.tistory.com/351

기존 ErrorResponse 필드의 errors에 애노테이션을 추가해준다.

@JsonInclude(Include.NON_NULL)

• errors 필드가 null인 경우 해당 필드를 JSON에 포함시키지 않도록 설정

private List<FieldError> errors;

@JsonInclude(Include.NON_NULL) 
// errors가 null인 경우 포함하지 않음
    private List<FieldError> errors;

그리고 객체 생성하는 부분에 '.errors(null)' 부분을 추가해준다.

     ErrorResponse response = ErrorResponse.builder()
                .code("test")
                .message(e.getMessage())
                .status(HttpStatus.INTERNAL_SERVER_ERROR.value())
                .build();

     ErrorResponse response = ErrorResponse.builder()
                .code("test")
                .message(e.getMessage())
                .status(HttpStatus.INTERNAL_SERVER_ERROR.value())
                .errors(null)
                .build();

변경 : th:value="${board.type == 'Book' ? '책' : '영화'}"

• application.yml

server:
  servlet:
    session:
      persistent: false

true : 세션 유지 false : 세션 종료

• application.properties

server.servlet.session.persistent=true

로그인 후

톰캣 재시작 후

이전까지만 해도 톰캣 서버를 아무리 재시작하더라도 세션이 거의 유지되어 있었는데 application properties 설정 정보를 수정 후 톰캣 서버를 재실행하면, 세션이 종료되는 것을 확인할 수 있다.

참고 : https://stackoverflow.com/questions/28477199/enable-session-persistence-with-spring-boot-and-embedded-tomcat

• Submit 버튼을 누르면 웹 브라우저가 요청 HTTP 메시지를 생성함
• HTTP 메시지를 만들어서 서버로 전송
• 웹 애플리케이션 서버를 처음부터 끝까지 구현해야 할 경우, HTTP 요청 메시지를 분해해야 함.

POST /save HTTP/1.1 Host: localhost:8080 Content-Type: application/x-www-form-urlencoded username=kim&age=20

• 서버 TCP/IP 연결 대기, 소켓 연결 • HTTP 요청 메시지를 파싱해서 읽기 • POST 방식, /save URL 인지 • Content-Type 확인 • HTTP 메시지 바디 내용 피싱

• username, age 데이터를 사용할 수 있게 파싱

• 저장 프로세스 실행 • 비즈니스 로직 실행

• 데이터베이스에 저장 요청

• HTTP 응답 메시지 생성 시작

• HTTP 시작 라인 생성
• Header 생성
• 메시지 바디에 HTML 생성에서 입력

• TCP/IP에 응답 전달, 소켓 종료

서버에서 개발자가 처리해야하는 작업들이 너무 많음. 비효율적.

-> 서블릿의 등장

서블릿을 지원하는 WAS를 사용하면, 비즈니스 로직 실행 외에 모든 기능들을 자동화 해줌.

** 서블릿 **

@WebServlet(name = "helloServlet", urlPatterns = "/hello")
public class HelloServlet extends HttpServlet {
    @Override 
    protected void service(HttpServletRequest request, HttpServletResponse response) { 
        //비지니스 로직 
    } 
}

• HttpServlet 상속 필수
• 파라미터 2개 : HttpServletRequest, HttpServletResponse

• HTTP 요청 정보를 편리하게 사용할 수 있도록 만들어줌

• 객체를 사용하면 된다.

• urlPatterns(“/hello”)의 URL이 호출되면 서블릿 코드가 실행
• HTTP 요청 정보를 편리하게 사용할 수 있는 HttpServletRequest
• HTTP 응답 정보를 편리하게 사용할 수 있는 HttpServletResponse

1) 웹 브라우저에서 localhost:8080/hello - HTTP 요청 2) WAS 서버에서 HTTP 요청 메시지를 기반으로 request, response 객체 생성 3) request, response 객체를 파라미터로 넘기면서 helloServlet 서블릿 객체 호출 4) 끝나고 리턴하면, response 객체 정보를 바탕으로 HTTP 응답 메시지 생성 5) 웹브라우저에 응답 전달 6) 웹브라우저가 HTML을 렌더링해서 보여줌

• 개발자는 Request 객체에서 HTTP 요청 정보를 편리하게 꺼내서 사용
• 개발자는 Response 객체에 HTTP 응답 정보를 편리하게 입력
• WAS는 Response 객체에 담겨있는 내용으로 HTTP 응답 정보를 생성

** 서블릿 컨테이너 **

• 서블릿 객체를 직접 생성하는 개념이 아님

• WAS 안에 서블릿 컨테이너가 있는데, 서블릿 객체를 서블릿 컨테이너가 자동으로 생성, 호출, 관리(생명주기)해줌

• 서블릿 여러개도 가능

• 톰캣처럼 서블릿을 지원하는 WAS를 서블릿 컨테이너라고 함

• 서블릿 컨테이너는 서블릿 객체를 생성, 초기화, 호출, 종료하는 생명주기 관리

• 서블릿 객체는 싱글톤으로 관리

  • 고객의 요청이 올 때 마다 계속 객체를 생성하는 것은 비효율
  • 최초 로딩 시점에 서블릿 객체를 미리 만들어두고 재활용
  • 모든 고객 요청은 동일한 서블릿 객체 인스턴스에 접근
  • 공유 변수 사용 주의
  • 서블릿 컨테이너 종료시 함께 종료

• JSP도 서블릿으로 변환 되어서 사용

• 동시 요청을 위한 멀티 쓰레드 처리 지원

** 최초 로딩 시점에 서블릿 객체, 싱글톤으로 하나

*24시간 작동하는 서버 - 3가지 선택지 *

1) 집에서 PC를 24시간 가동 2) 호스팅 서비스(Cafe24, 코리아호스팅 등) 이용 3) 클라우드 서비스(AWS, AZURE, GCP 등) 이용

비용적 측면 : 1번, 2번이 저렴 but. 특정 시간에만 트래픽이 몰리는 경우 -> 유동적으로 사양을 늘릴 수 있는 클라우드가 유리

** 클라우드 서비스란? **

• 인터넷(클라우드)을 통해 서버, 스토리지(파일 저장소), 데이터베이스, 네트워크, 소프트웨어, 모니터링 등의 컴퓨팅 서비스를 제공하는 것
• 단순 물리 장비 대여가 아님
• 예를 들어, AWS의 EC2는 서버 장비를 대여하는 것이지만, 실제로는 그 안의 로그 관리, 모니터링, 하드웨어 교체, 네트워크 관리 등을 기본적으로 지원 -> 개발자가 직접 할 일을 지원해줌.

** 클라우드의 형태 **

1) Infrastructure as a Service (IaaS, 아이아스, 이에스)

• 기존 물리 장비를 미들웨어와 함께 묶어둔 추상화 서비스
• 가상머신, 스토리지, 네트워크, 운영체제 등의 IT 인프라 대여 서비스
• AWS의 EC2, S3 등

2) Platform as a Service (PaaS, 파스)

• IaaS에서 한 번 더 추상화한 서비스
• 한 번 더 추상화 했기 때문에 많은 기능이 자동화
• AWS의 Beanstalk(빈스톡), Heroku(헤로쿠) 등

3) Software as a Service (Saas, 사스)

• 소프트웨어 서비스
• 구글 드라이브, 드랍박스, 와탭 등

** AWS 클라우드의 장점 **

• 첫 가입 시 1년간 대부분 서비스가 무료, 단 서비스마다 제한은 있음
• 기본적으로 지원하는 기능(모니터링, 로그관리, 백업, 복구, 클러스터링 등등)이 많아 개인 혹은 소규모일 때 개발에 더 집중할 수 있음
• 많은 기업이 AWS로 이전 중이기 때문에, 이직할 때 AWS 사용 경험은 도움이 됨. 국내에서는 AWS 점유율이 압도적임. (쿠팡, 우아한형제들, 리멤버 등 대부분 클라우드 사용 회사에서 대부분 AWS 사용)
• 사용자가 많아 국내 자료 및 커뮤니티가 활성화 되어 있음.

출처 : 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 (저자:이동욱)

1) GET - 쿼리 파라미터

• /url?username=hello&age=20
• 메시지 바디 없이, URL의 쿼리 파라미터에 데이터를 포함해서 전달
• 예) 검색, 필터, 페이징등에서 많이 사용하는 방식

2) POST - HTML Form

• content-type: application/x-www-form-urlencoded
• 메시지 바디에 쿼리 파리미터 형식으로 전달 username=hello&age=20
• 예) 회원 가입, 상품 주문, HTML Form 사용

3) HTTP message body에 데이터를 직접 담아서 요청

• HTTP API에서 주로 사용, JSON, XML, TEXT
• 데이터 형식은 주로 JSON 사용
• POST, PUT, PATCH

먼저 domain 패키지에 BaseEntity 클래스를 생성한 뒤 차례대로 등록자, 등록일자, 수정자, 수정일자 컬럼을 변수로 선언했다.

그리고 @MappedSuperclass 어노테이션을 통해 공통 Entity를 선언하고, 이후에 다른 도메인 엔티티 클래스들은 이를 상속 받아 사용할 수 있다.

** BaseEntity 클래스 **

package com.dorandoran.domain;

import lombok.Getter;
import org.springframework.data.annotation.CreatedBy;
import org.springframework.data.annotation.CreatedDate;
import org.springframework.data.annotation.LastModifiedBy;
import org.springframework.data.annotation.LastModifiedDate;
import org.springframework.data.jpa.domain.support.AuditingEntityListener;

import javax.persistence.Column;
import javax.persistence.EntityListeners;
import javax.persistence.MappedSuperclass;
import java.time.LocalDateTime;

@MappedSuperclass
@EntityListeners(AuditingEntityListener.class)
@Getter
public class BaseEntity {

    @CreatedBy
    @Column(updatable = false)
    private String created;

    @CreatedDate
    private LocalDateTime createdDate;

    @LastModifiedBy
    private String updated;

    @LastModifiedDate
    private LocalDateTime updatedDate;
}

** Member 클래스 **

package com.dorandoran.domain;

import lombok.Getter;
import lombok.Setter;

import javax.persistence.*;
import java.util.ArrayList;
import java.util.List;

@Entity
@Getter @Setter
public class Member extends BaseEntity {

    @Id @GeneratedValue
    @Column(name = "member_id")
    private Long id;

    private String name;
    private String nickname;
    private String email;
    private String password;

    // Member<->Board
    @OneToMany(mappedBy = "member")
    private List<Board> board = new ArrayList<>();

    // Member<->Comment
    @OneToMany(mappedBy = "member")
    private List<Comment> comment = new ArrayList<>();
}

복습 및 기록용 - 강의노트 정리

섹션 1. 프로젝트 환경설정

[#1. 프로젝트 생성]

[#2. 라이브러리 살펴보기]

[#3. View 환경 설정]

[#4. JPA와 DB 설정, 동작확인]