Leetcode 100

작성양식

### 
#### 1. 문제
[문제 URL]()
#### 2. 나의 풀이
##### 시도 1
``` java
\```
#### 3. 다른 사람의 풀이
```java
\```
#### 4. 생각해보기

---

909. Snakes and Ladders

1. 문제

문제 URL 뱀이나 사다리를 타고 이동하는 문제로 보너스 이동은 한 번만 가능하고 마지막 칸까지 이동이 목표입니다.

• 보드 구성: n x n 정수 행렬 보드를 받습니다. 각 셀은 바토스토페돈(Boustrophedon) 스타일로 1부터 n^2까지 번호가 매겨져 있습니다.
• 시작과 종료: 보드의 1번 칸에서 시작하여 n^2번 칸에서 게임이 끝납니다.
• 움직임 규칙:
  • 각 움직임마다 주사위 굴리기를 시뮬레이션하여 1부터 6까지의 수 중 하나를 선택합니다.
  • 선택된 수에 따라 목적지 칸을 결정하고, 해당 칸에 뱀이나 사다리가 있다면 해당 위치로 이동합니다.
  • 뱀이나 사다리는 한 번만 탈 수 있습니다.
• 목표:
  • n^2번 칸에 도달하는 데 필요한 최소 움직임 횟수를 구하는 것입니다.
  • 만약 도달할 수 없다면 -1을 반환해야 합니다.

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation: 
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.

2. 나의 풀이

시도 1

바토스토페돈(Boustrophedon) 스타일이란, 한 줄이 왼쪽에서 오른쪽으로 흐른 후 다음 줄이 오른쪽에서 왼쪽으로 흐르는 방식을 설명할 때 사용됩니다. 즉, 이 문제의 의도가 BFS임을 알 수 있습니다.

• 문제에서 보면 그림에서 6위에 숫자가 7인 것처럼 숫자들이 이어져있는 것을 볼 수 있습니다. 이 점에 유의해야 합니다.
• 주사위를 최소로 던져서 가야하기 때문에 무조건 사다리를 탈 수 있도록 고민해야 합니다.

여기서, 문제에 따라 -1의 결과만 나올 수 있는 경우, 보드가 너무 작아 주사위 1번이면 도착하는 경우를 제거합니다. 그리고 board에서 보면 이동하게 되는 곳에 이동되는 지점(목적지)의 숫자가 적혀있기 때문에 오히려 2차 배열이 헷갈려서 1차 배열 newBoard로 변환하는 sumBoard를 만들었습니다.

class Solution {
    int length=0, result=0;

    public int snakesAndLadders(int[][] board) {
        length = board.length;
        if(length==0) return -1;
        for(int[] arr:board){
            if(arr.length!=length) return -1;
        }

        if(length<3) return 1;

        int[] newBoard = sumBoard(board);
        boolean[] visited = new boolean[length*length];
        bfs(newBoard, visited);
        return result;
    }

    public int[] sumBoard(int[][] board) {
        int newBoard = new int[length*length];
        int cnt=0;
        for(int i=length-1; i>=0; i--){
            if(i%2==0){
                for(int j=0; j<length; j++){
                    newBoard[cnt] = board[i][j];
                }
            }else{
                for(int j=length-1; j>=0; j--){
                    newBoard[cnt] = board[i][j];
                }
            }
            cnt++;
        }
        return newBoard;
    }
}

그럼 다음 단계에서 bfs(newBoard, visited); 메서드를 생성해 도착여부를 체크해야 합니다. BFS 안의 세부 코드를 작성하지 못했는데 몇 가지 예상 시나리오를 작성해봤습니다. 코드를 작성하진 못했지만 생각해봤을 때, 3번의 경우가 가장 적합해 보였습니다.

1. 반복문을 돌면서 사다리로 제일 멀리 갈 수 있는 경우를 찾습니다. 그리고 사다리의 시작점까지 가장 빠르게 도착할 수 있는 경우의 수와 사다리 도착지점에서 가장 빠르게 도달할 수 있는 주사위 횟수를 계산해 더합니다.
2. 사다리가 없는 경우 6으로 계속 가능게 빠르므로 위에 result 값을 유지하지만, 뱀이 있는지 확인한다. 뱀이 있다면 5만큼 이동하여 갈 수 있는 최소 주사위 횟수를 계산합니다.
3. 사다리와 뱀의 위치 값을 배열로 받습니다.
   • 그리고 다 이용하는 경우, 일부만 사용하는 경우, 모두 6으로 이동한 경우 등의 가짓수를 고려해봅니다.
   • 뱀으로 깎이는 수와 사다리로 혜택을 보는 수가 같다면 이용하는 의미가 있을지 고민해봐야 합니다. 그럼 뱀을 피해야만 합니다.
   • 하지만 예시처럼 뱀을 이용하더라도 사다리를 2개 탈 수 있다면 뱀이 효과적일 수도 있습니다.

public void bfs(int[] newBoard, boolean[] visited) {
    result = (length*length)%6>0? (length*length)/6+1 : (length*length)/6;
    int location=0, cnt=0;
    while(location<length*length){
        // 예상 시나리오가 구현될 부분 
    } 
    result = Math.min(result, cnt);
}

3. 다른 사람의 풀이

• 실제 게임 플레이에서는 2D 좌표가 필요하지 않으므로 1차원 배열로 변환합니다.
• 게임보드를 순회하기 위해 BFS (Breadth-First Search)를 사용하며, 큐에 시작 위치를 추가하여 시작합니다.
• BFS를 사용해 모든 가능한 경로를 탐색하며, 주사위를 굴려 나올 수 있는 6가지 결과를 고려합니다. 뱀이나 사다리를 만나면 해당 위치로 이동합니다.
• 종료 지점에 도달하면 그 때까지의 이동 횟수를 반환하고, 도달할 수 없는 경우 -1을 반환합니다.

class Solution {
    public int snakesAndLadders(int[][] board) {
        final int n = board.length;
        final int endSquare = n * n;
        
        short[] brd = new short[endSquare + 1];
        int brdIdx = 1;
        for (int row = n - 1; row >= 0; row--) {
            for (int col = 0; col < n; col++)  brd[brdIdx++] = (short)board[row][col];
            if (--row < 0)  break;
            for (int col = n - 1; col >= 0; col--)  brd[brdIdx++] = (short)board[row][col];
        }
        
        final int bfsQueueLen = Math.min(n * n, 8 * n);
        short[] bfsQueue = new short[bfsQueueLen];
        int bfsQueueRead = 0;
        int bfsQueueWrite = 0;
        bfsQueue[bfsQueueWrite++] = 1;  // Initialize BFS queue to start at square #1

        byte[] count = new byte[endSquare + 1];
        count[1] = 1;                   // Mark the starting location as already visited.

        while (bfsQueueRead != bfsQueueWrite) {
            int currSquare = bfsQueue[bfsQueueRead++];
            bfsQueueRead %= bfsQueueLen;
            if (currSquare + 6 >= endSquare)  return count[currSquare];
            int maxOpenMove = 0;
            for (int move = 6; move >= 1; move--) {
                int nextSquare = currSquare + move;
                if (brd[nextSquare] >= 0) {
                    if ((nextSquare = brd[nextSquare]) == endSquare)  return count[currSquare];
                }
                else {
                    if (move < maxOpenMove)  // If we already moved to an open square 1 to 6
                        continue;
                    maxOpenMove = move;
                }
                if (count[nextSquare] == 0) {
                    count[nextSquare] = (byte)(count[currSquare] + 1);
                    bfsQueue[bfsQueueWrite++] = (short)nextSquare;
                    if ((bfsQueueWrite %= bfsQueueLen) == bfsQueueRead)  return 0; // Queue overflow
                }
            }
        }
        return -1;
    }
}

4. 생각해보기

뱀과 사다리 게임의 전통적인 보드는 2차원 평면에 나타나 있습니다. 그러나 이 문제를 프로그래밍적으로 접근할 때, 특히 그래프 탐색 문제로 생각할 때, 1차원 배열로 바꾸어 생각하는 것이 더 간편할 수 있습니다.
BFS 문제 익숙해지도록 더 풀어봐야겠습니다.

---

133. Clone Graph

1. 문제

문제 URL

• 이 문제는 주어진 연결된 (connected) 무방향 그래프를 deep copy하는 문제입니다.
• 각 노드는 그 값을 나타내는 int 형과 이웃 노드의 리스트인 List<Node>를 포함합니다. 이 문제는 DFS와 BFS를 통해 deep copy를 구현할 수 있습니다.

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[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. 나의 풀이

시도 1

DFS로 풀이했는데 모든 노드를 새로 만들었다고 생각했지만 실제로 You must return a copy of all the nodes in the original graph와 같이 모든 노드를 클론하지 못한 것을 알 수 있었습니다.

• 문제를 다시 봤는데 연결된 무방향 노드라는 점을 다시 생각해보기로 했습니다.

class Solution {
    public Node cloneGraph(Node node) {
        if(node==null) return null;
        if(node.neighbors.size()==0) return new Node(1);

        Node newNode = new Node(node.val);
        boolean[] visited = new boolean[100];
        dfs(node, newNode, visited);
        return newNode;
    }

    public void dfs(Node node, Node newNode, boolean[] visited) {
        List<Node> newNeighbors =  newNode.neighbors;
        visited[node.val] = true;
        for (Node n : node.neighbors) {
            if (!visited[n.val]) {
                newNeighbors.add(new Node(n.val));
                newNode.neighbors = newNeighbors;
                dfs(n, new Node(n.val), visited);
            }
        }
    }
}

시도 2

연결된 무방향 노드이기 때문에 boolean보다 map이 더 깔끔한 풀이가 될 수 있습니다. 중복된 값을 갖는 노드가 없기 때문에 그 값은 키로 사용이 가능합니다. map에 키 값이 없다면 즉 방문하지 않은 상태이기 때문에 for 문으로 원 노드의 neighbor들을 하나씩 cloneNode에 추가해줍니다.

public class Solution {
  HashMap<Integer, Node> map = new HashMap<>();

  public Node cloneGraph(Node node) {
    if (node == null) return null;
    if(node.neighbors.size()==0) return new Node(1);
    return dfs(node);
  }

  private Node dfs(Node node) {
    if (map.containsKey(node.val)) {
      return map.get(node.val);
    }

    Node cloneNode = new Node(node.val, new ArrayList<Node>());
    map.put(node.val, cloneNode);

    for (Node neighbor : node.neighbors) {
      cloneNode.neighbors.add(dfs(neighbor));
    }

    return cloneNode;
  }
}

3. 다른 사람의 풀이

pinned되어 있는 풀이를 보게 되어 가지고 왔습니다. 주어진 노드를 기준으로 DFS를 사용하여 그래프를 탐색하면서 노드를 복사합니다.

• 방문한 노드를 체크하여 이미 복사한 노드인 경우에는 해당 노드를 반환하고, 아직 복사하지 않은 노드인 경우에는 새로운 노드를 생성하여 이웃 노드들을 재귀적으로 복사합니다.
• 이 때, 방문한 노드를 체크하기 위해 Node[] 배열을 사용합니다.
• 이 배열은 초기에는 모든 요소가 null로 초기화되며, 각 노드의 val 값을 인덱스로 사용하여 해당 노드가 이미 복사되었는지 여부를 체크합니다.
• 이렇게 구현된 cloneGraph 함수는 주어진 그래프를 deep copy한 결과를 반환합니다.

class Solution {
    public void dfs(Node node , Node copy , Node[] visited){
        visited[copy.val] = copy;// store the current node at it's val index which will tell us that this node is now visited
        
//         now traverse for the adjacent nodes of root node
        for(Node n : node.neighbors){
//             check whether that node is visited or not
//              if it is not visited, there must be null
            if(visited[n.val] == null){
//                 so now if it not visited, create a new node
                Node newNode = new Node(n.val);
//                 add this node as the neighbor of the prev copied node
                copy.neighbors.add(newNode);
//                 make dfs call for this unvisited node to discover whether it's adjacent nodes are explored or not
                dfs(n , newNode , visited);
            }else{
//                 if that node is already visited, retrieve that node from visited array and add it as the adjacent node of prev copied node
//                 THIS IS THE POINT WHY WE USED NODE[] INSTEAD OF BOOLEAN[] ARRAY
                copy.neighbors.add(visited[n.val]);
            }
        }
        
    }
    public Node cloneGraph(Node node) {
        if(node == null) return null; // if the actual node is empty there is nothing to copy, so return null
        Node copy = new Node(node.val); // create a new node , with same value as the root node(given node)
        Node[] visited = new Node[101]; // in this question we will create an array of Node(not boolean) why ? , because i have to add all the adjacent nodes of particular vertex, whether it's visited or not, so in the Node[] initially null is stored, if that node is visited, we will store the respective node at the index, and can retrieve that easily.
        Arrays.fill(visited , null); // initially store null at all places
        dfs(node , copy , visited); // make a dfs call for traversing all the vertices of the root node
        return copy; // in the end return the copy node
    }
}

4. 생각해보기

DFS와 BFS의 구현 코드에 대해 다시 집고 넘어가기 위해 ChatGPT로 구현해봤습니다. DFS는 재귀 함수를 사용하여 구현했고, BFS는 큐를 이용해 구현합니다.

DFS 구현

public void dfs(Node node, boolean[] visited) {
    visited[node.val] = true;
    for (Node neighbor : node.neighbors) {
        if (!visited[neighbor.val]) {
            dfs(neighbor, visited);
        }
    }
}

BFS 구현
BFS에서는 현재 노드의 이웃 노드들을 큐에 추가한 후에, 큐에서 하나씩 노드를 꺼내어 방문하는 과정을 반복합니다. 이렇게 큐를 사용하면, 먼저 추가된 이웃 노드부터 차례대로 방문하게 되므로 너비 우선 탐색이 가능해집니다.

public void bfs(Node node, boolean[] visited) {
    Queue<Node> queue = new LinkedList<>();
    queue.offer(node);
    visited[node.val] = true;
    while (!queue.isEmpty()) {
        Node curr = queue.poll();
        for (Node neighbor : curr.neighbors) {
            if (!visited[neighbor.val]) {
                queue.offer(neighbor);
                visited[neighbor.val] = true;
            }
        }
    }
}

---

211. Design Add and Search Words Data Structure

1. 문제

문제 URL

• 단어를 추가하고 이전에 추가된 단어와 일치하는지 확인하는 데이터 구조를 설계하는 문제입니다.

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

class WordDictionary {

    public WordDictionary() {
        
    }
    
    public void addWord(String word) {
        
    }
    
    public boolean search(String word) {
        
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

2. 나의 풀이

시도 1

208번 문제와 동일하게 먼저 Trie 구조를 구현했습니다.

• [".ad"],["b.."] 부분을 고민해야 했는데 .에는 어떤 문자가 들어오더라도 가능해야 했습니다.

class WordDictionary {
    WordDictionary[] arr;
    boolean isChar;

    public WordDictionary() {
        arr = new WordDictionary[26];
        isChar = false;
    }
    
    public void addWord(String word) {
        if(root==null) root=new WordDictionary();
        WordDictionary temp=root;
        for(char c:word.toCharArray()){
            int ind=c-'a';
            if(temp.child[ind]==null) temp.child[ind]=new WordDictionary();
            temp=temp.child[ind];
        }
        temp.isLast=true;
    }
    
    public boolean search(String word) {
      if(root==null) root=new WordDictionary();
      WordDictionary temp=root;
      for(char c : word.toCharArray()){
          int idx = c-'a';
          if(temp.children[idx] == null){
             return false;
          }
          temp = temp.children[idx];
      }
      return temp.isWord == true;        
    }
}

3. 다른 사람의 풀이

WordDictionary 클래스는 Trie 자료구조를 사용하여 단어를 저장합니다. addWord 메서드는 단어를 Trie에 추가하고, search 메서드는 주어진 단어가 Trie에 있는지 검색합니다.
이 코드에서는 ‘.’ 문자를 와일드카드로 사용할 수 있습니다. ‘.’ 문자는 어떤 문자든지 대체될 수 있습니다. 이 기능은 checkWord 메서드에서 구현됩니다.

class WordDictionary {
    boolean isLast;
    WordDictionary [] child;
    public WordDictionary() {
        this.isLast=false;
        this.child=new WordDictionary[26];
    }
    WordDictionary root;
    public void addWord(String word) {
        if(root==null) root=new WordDictionary();
        WordDictionary temp=root;
        for(char c:word.toCharArray()){
            int ind=c-'a';
            if(temp.child[ind]==null) temp.child[ind]=new WordDictionary();
            temp=temp.child[ind];
        }
        temp.isLast=true;
    }
    
    public boolean search(String word) {
        return checkWord(word,0,root);
    }
    public boolean checkWord(String word,int ind,WordDictionary temp){
        if(ind>=word.length()) return temp.isLast;
        if(temp==null) return false;
        char c=word.charAt(ind);
        if(c!='.'){
             if(temp.child[c-'a']!=null) return checkWord(word,ind+1,temp.child[c-'a']);
             else return false;
        }
        else{
            boolean b=false;
            for(int i=0;i<26;i++){
                if(temp.child[i]!=null) b= b || checkWord(word,ind+1,temp.child[i]);
            }
            return b;
        }
    }
}

4. 생각해보기

기본적인 Trie 구현에서의 search와 이 문제에서 search 조건의 차이를 다시 확인할 필요가 있습니다.

---

208. Implement Trie

1. 문제

문제 URL

• Trie는 문제입니다.
  • Trie() : Trie 객체를 초기화합니다.
  • void insert(String word) : 문자열 word를 trie에 삽입합니다.
  • boolean search(String word) : 문자열 word가 trie에 있는 경우 true를 반환하고 그렇지 않은 경우 false를 반환합니다.
  • boolean startsWith(String prefix) : 접두사 prefix를 가진 이전에 삽입된 문자열이 있는 경우 true를 반환하고 그렇지 않은 경우 false를 반환합니다.

2. 나의 풀이

시도 1

Map을 이용하여 자식 노드를 저장하고 있기 때문에, 메모리 사용량이 많아지고 검색 속도가 느려질 수 있습니다. 따라서 배열을 이용하여 자식 노드를 저장하는 방법이 더 효율적일 수 있습니다.

class TrieNode{
  Map<Character, TrieNode> nodes = new HashMap<>();
  boolean isLast;
  
  Map<Character, TrieNode> getNodes(){
    return this.nodes;
  }
  
  boolean isLast(){
    return this.isLast;
  }
  
  void setIsLas(boolean isLast){
    this.isLast = isLast;
  }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            TrieNode node = curr.getChild(c);
            if (node == null) {
                node = new TrieNode();
                curr.setChild(c, node);
            }
            curr = node;
        }
        curr.setEndOfWord(true);
    }
    
    public boolean search(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            TrieNode node = curr.getChild(c);
            if (node == null) {
                return false;
            }
            curr = node;
        }
        return curr.isEndOfWord();
    }
    
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for (char c : prefix.toCharArray()) {
            TrieNode node = curr.getChild(c);
            if (node == null) {
                return false;
            }
            curr = node;
        }
        return true;
    }
}

3. 다른 사람의 풀이

Trie 클래스는 Node 클래스를 이용하여 Trie 자료 구조를 구현합니다. Node 클래스는 문자열을 저장하고 있는 문자열의 끝을 나타내는 isWord 변수와 26개의 자식 노드(children 배열)를 가지고 있습니다.

• Trie 클래스는 기본 생성자에서 root 노드를 생성하고,
• insert 메소드에서는 주어진 문자열을 Trie에 삽입합니다. 이때, 문자열을 한 글자씩 순회하며 해당 글자의 자식 노드가 존재하지 않으면 새로운 노드를 생성합니다.
• search 메소드는 Trie에 해당 문자열이 존재하는지 검색합니다. 이때, 문자열을 한 글자씩 순회하며 해당 글자의 자식 노드가 존재하지 않으면 false를 반환합니다. 마지막 글자까지 순회한 후 isWord 변수가 true인 경우에만 true를 반환합니다.
• startsWith 메소드는 Trie에 해당 prefix로 시작하는 문자열이 존재하는지 검색합니다. 이때, prefix를 한 글자씩 순회하며 해당 글자의 자식 노드가 존재하지 않으면 false를 반환합니다. 마지막 글자까지 순회한 후 true를 반환합니다.

class Node{
    Node children[] = new Node[26];
    boolean isWord = false;
}


class Trie {
  Node root;

    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        Node temp = root;
        for(char c : word.toCharArray()){
            int idx = c-'a';
            if(temp.children[idx] == null){
                temp.children[idx] = new Node();
            }
            temp = temp.children[idx];
        }
        temp.isWord = true;
    }
    
    public boolean search(String word) {
      Node temp = root;
        for(char c : word.toCharArray()){
            int idx = c-'a';
            if(temp.children[idx] == null){
               return false;
            }
            temp = temp.children[idx];
        }
        return temp.isWord == true;        
    }
    
    public boolean startsWith(String prefix) {
         Node temp = root;
        for(char c : prefix.toCharArray()){
            int idx = c-'a';
            if(temp.children[idx] == null){
                return false;
            }
            temp = temp.children[idx];
        }
        return true;
    }
}

4. 생각해보기

Trie 구조는 문자열 검색에 사용되는 트리 자료구조입니다. 각 노드는 문자를 저장하고, 부모 노드와 자식 노드 사이에는 문자열의 접두어 관계가 있습니다. 이 구조의 가장 큰 특징은 검색 시간이 문자열의 길이와 무관하다는 것입니다. 또한, 문자열 검색 외에도 자동 완성 기능 등에도 이용됩니다.

---

637. Average of Levels in Binary Tree

1. 문제

문제 URL

• 이진 트리의 루트가 주어지면, 각 레벨의 노드의 평균 값을 배열 형태로 반환합니다. 실제 답과 10^-5 이내의 정확도로 일치하는 답안이 허용됩니다.

2. 나의 풀이

시도 1

이진 트리라는 점에서 각 레벨의 노드 값을 더해서 같은 노드를 갖으면 그 수로 나누어주는 방식을 생각해봤습니다.

• 하지만 이 풀이에서는 같은 노드라는 것을 제대로 확인하지 않은 채 계산이 되는 것을 볼 수 있습니다.
• 문제: [3,9,20,null,null,15,7]
• 결과: [6.00000,11.75000,10.80000,10.80000,10.80000]
• 정답: [3.00000,14.50000,11.00000]

class Solution {
    List<Double> list = new ArrayList<>();
    int valSum=0, cntSum=0;
    public List<Double> averageOfLevels(TreeNode root) {
        getAverage(root, 0);
        return list;
    }
    public void getAverage(TreeNode root, int h) {
        if(root==null) return;
        valSum+=root.val;
        cntSum++;
        getAverage(root.left, h++);
        getAverage(root.right, h++);
        list.add((double)valSum/cntSum);
    }
}

시도 2

마지막에 평균값을 list에 넣는 과정에서 가장 오른쪽 노드일 때 수행하도록 조건문을 걸었습니다. 그리고 계산에 사용된 변수를 초기화합니다.

• 이렇게 해도 같은 층 여부를 제대로 확인하지 못하는 걸 볼 수 있습니다.

public void getAverage(TreeNode root, int h) {
    if(root==null) return;
    valSum+=root.val;
    cntSum++;
    if(root.right==null){
        list.add((double)valSum/cntSum);
        valSum=0;
        cntSum=0;
    }
    getAverage(root.left, h++);
    getAverage(root.right, h++);
}

3. 다른 사람의 풀이

Queue를 이용한 풀이가 새로워서 작성하게 되었습니다.

• 빈 리스트 ans를 초기화하고, 빈 트리인 경우 빈 리스트를 반환합니다.
• 큐 q를 사용하여 BFS를 수행하고, 루트 노드를 큐에 추가합니다.
• BFS를 수행하는 동안 현재 레벨에 있는 모든 노드의 값을 합산하고 그 개수를 세어 평균을 계산합니다.
• 각 레벨의 평균 값을 ans 리스트에 추가합니다.
• BFS가 끝나면 ans 리스트를 반환합니다.

시간복잡도와 공간복잡도

• 시간복잡도: O(n)
• 공간복잡도: O(n)

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();
        if(root==null){
            return ans;
        }
       Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int n=q.size();
           double avg=0l;
            for(int i=0;i<n;i++){
                 TreeNode curr=q.poll();
                avg=avg+(double)curr.val;
                if(curr.left!=null){q.add(curr.left);}
                if(curr.right!=null){q.add(curr.right);}
            }
            avg=avg/n;
            ans.add(avg);
        }
       return ans; 
    }
}

4. 생각해보기

queue.offer(node)는 node라는 요소를 큐에 추가하려는 것을 의미합니다. 만약 큐가 가득 차 있지 않다면 true를 반환하고, 가득 차 있다면 false를 반환합니다. 이를 통해 큐에 요소를 안전하게 추가할 수 있습니다.

---

199. Binary Tree Right Side View

1. 문제

문제 URL

• 이진 트리의 오른쪽에서 시작하여 트리를 보면서 맨 오른쪽에 있는 노드(각 레벨에서 가장 오른쪽에 있는 노드)들의 값을 위에서 아래로 순서대로 반환해야 합니다.

2. 나의 풀이

시도 1

문제를 보고 가장 먼저 든 생각은 우선 각 노드 층에서 가장 오른쪽 값을 list에 저장하고 리턴하면 되지 않을까라는 생각이었습니다. 그런데 무작정 풀었을 때 왼쪽 노드에서 오른쪽 보다 긴 경우의 위치를 찾아서 반환하는 것이 생각보다 복잡해서 문제에서 제시한 이진 트리를 더 이용해야겠다는 생각이 들었습니다.

class Solution {
    int h=0;
    List<Integer> list = new ArrayList<>();
    public hList<Integer> rightSideView(TreeNode root) {
        deepth(root);
        getRight(root);
        if(h==list.size()) return list;
        else{
            
        }
    }

    public void deepth(TreeNode root){
        if(root==null) return; 
        deepth(root.left);
        h++;
        deepth(root.right);
    }

    public void getRight(TreeNode root){
        if(root==null) return; 
        list.add(root.val);
        deepth(root.right);
    }
}

시도 2

이진 트리를 이용한 방법으로 시도했지만 실패한 풀이입니다.

• 여기서 보면, 노드의 높이 h를 이용했는데, rightSideView(root.right);를 다 돌고나서 h++;가 진행되기 때문에 왼쪽과 오른쪽 노드 층의 차이가 생기게 됩니다.
• 따라서 분리해서 노드의 층을 유지하는 방법을 이용해야 합니다.

class Solution {
    int h=0;
    List<Integer> list = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        if(root==null) return null;
        if(h==list.size()) list.add(root.val);

        rightSideView(root.right);
        h++;
        rightSideView(root.left);

        return list;
    }
}

3. 다른 사람의 풀이

여기서 주의깊게 본 부분은 rightView에서 재귀를 돌 때 오른쪽 노드부터 실행하는 것을 알 수 있습니다. 이전에 최소값 또는 k번째로 작은 수를 구하기 위해 중회순회를 사용하던 방식과 반대로 이용할 수 있다는 것을 알 수 있습니다.

public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }
    
    public void rightView(TreeNode curr, List<Integer> result, int currDepth){
        if(curr == null){
            return;
        }
        if(currDepth == result.size()){
            result.add(curr.val);
        }
        
        rightView(curr.right, result, currDepth + 1);
        rightView(curr.left, result, currDepth + 1);
    }
}

4. 생각해보기

어렵게 생각하지 않고 기존에 아는 내용을 어떻게 하면 활용해서 풀이할 수 있을까 고민하는 방법을 익히는 것이 중요합니다. 이 문제에서 오른쪽 뷰로 살펴보는 문제였지만 예를 들어 왼쪽 뷰로 동일한 문제를 풀이하게 된다면 코드를 다음과 같이 작성할 수 있을 것입니다.

public class Solution {
    public List<Integer> leftSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }
    
    public void leftView(TreeNode curr, List<Integer> result, int currDepth){
        if(curr == null){
            return;
        }
        if(currDepth == result.size()){
            result.add(curr.val);
        }

        leftView(curr.left, result, currDepth + 1);
        leftView(curr.right, result, currDepth + 1);
    }
}

---

230. Kth Smallest Element in a BST

1. 문제

문제 URL

• 이진 탐색 트리 (BST)의 루트와 정수 k가 주어졌을 때, 이진 트리의 모든 노드 값 중에서 k번째로 작은 값을 찾을 수 있습니다.

2. 나의 풀이

시도 1

BST의 모든 노드 값을 오름차순으로 방문하는 중위 순회를 사용하여 k번째로 작은 값을 찾을 수 있습니다.

• 530. Minimum Absolute Difference in BST 문제를 푼 이후라서 쉽게 접근할 수 있었습니다.

class Solution {
    List<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        if(root==null){
            Collections.sort(list);
            if(list.size()<k) return 0;
            else return list.get(k-1);
        } 
        list.add(root.val);
        kthSmallest(root.left, k);
        kthSmallest(root.right, k);

        Collections.sort(list);
        if(list.size()<k) return 0;
        else return list.get(k-1);
    }
}

이것도 통과 코드이긴 하지만 더 깔끔하게 중복 코드를 정리해보기로 했습니다.

class Solution {
    List<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        if(root==null){
            return getAnswer(list, k);  
        } 
        list.add(root.val);
        kthSmallest(root.left, k);
        kthSmallest(root.right, k);
        return getAnswer(list, k);        
    }

    public int getAnswer(List<Integer> list, int k) {
        Collections.sort(list);
        if(list.size()<k) return 0;
        else return list.get(k-1);

    }
}

제가 푼 풀이의 시간복잡도와 공간복잡도는 다음과 같습니다.

• 시간복잡도: O(n log n)
• 공간복잡도: O(n)

3. 다른 사람의 풀이

이 풀이는 시간복잡도면에서 손해를 봤지만 번번히 sort처리를 해주는 제 코드와는 달리 마지막에서만 return으로 k번째로 작은 값을 가지고 오는 것을 볼 수 있습니다. 바로 이진 탐색 트리라는 자료구조의 특성을 가지고 있기 때문입니다.

• 시간복잡도: O(n)
• 공간복잡도: O(n)

class Solution {
    List<Integer> list=new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        if(root==null)return 0;
        help(root,k);
        return list.get(k-1);
    }
    public void help(TreeNode root,int k)
    {
        if(root==null)return;
        help(root.left,k);
        list.add(root.val);
        if(list.size()==k)return;
        help(root.right,k);
    }
}

4. 생각해보기

이진 탐색 트리라는 자료구조의 특성을 가지고 있다는 점을 고려해서 제 코드(시도 2)의 부분을 수정해보겠습니다. 이전 코드의 문제점은 다음과 같습니다.

• 주어진 코드에서는 중복 노드 값을 포함하여 모든 노드 값을 리스트에 추가하고 있으므로 올바른 중위 순회가 아닙니다.
• 모든 노드 값을 중복으로 리스트에 추가하고 나중에 정렬하여 k번째 값을 찾으려는 것은 비효율적입니다.

아래와 같은 코드를 사용하면, count로 수를 조정할 수 있으며, 모든 노드를 검색하고 정렬하지 않아도 중간에 정지할 수 있습니다. 이진탐색트리 문제에서 이런 스타일로의 구현방법을 익혀둘 필요가 있습니다.

public class Solution {
    int result;
    int count;

    public int kthSmallest(TreeNode root, int k) {
        count = 0;
        inOrderTraversal(root, k);
        return result;
    }

    private void inOrderTraversal(TreeNode node, int k) {
        if (node == null) return;
        
        inOrderTraversal(node.left, k);
        count++;
        
        if (count == k) {
            result = node.val;
            return;
        }
        
        inOrderTraversal(node.right, k);
    }
}

---

530. Minimum Absolute Difference in BST

1. 문제

문제 URL

• 주어진 이진 탐색 트리(BST)의 서로 다른 두 노드 값 중 최소 절대 차이를 반환하는 문제입니다. 즉, BST에서 가장 가까운 값의 차이를 찾는 문제입니다.
• 예를 들어, [1,null,5,3] root가 입력된다면, 그 최소 절대 차이는 2가 됩니다.

2. 나의 풀이

시도 1

• 문제를 처음에 잘못 알고 접근해서 실패했습니다.
  • 순서대로 val가 왼쪽에서 오른쪽으로 들어가기 때문에 가장 왼쪽 노드와 가장 오른쪽 노드의 차이만 고려하면 된다고 생각했습니다.
  • 하지만, [5,4,7] root에서 최소 절대 차이는 1로 인접 노드 값의 차이를 구하는 문제입니다. 높이가 아니라..!!

class Solution {
    int left=0, right=0;
    public int getMinimumDifference(TreeNode root) {
        TreeNode lroot = root;
        TreeNode rroot = root;
        while(lroot.left!=null){
            lroot = lroot.left;
            left++;
        }
        while(rroot.right!=null){
            rroot = rroot.right;
            right++;
        }
        return Math.abs(left-right);
    }
}

시도 2

그럼 다시 인접 노드 값의 차이를 구하는 방식으로 풀이해봤습니다. 이렇게 재귀적 풀이를 하면 되지 않을까 하는 생각에서 만들어봤는데 시간초과가 발생했습니다.

• 중위 순회 방법이지만 중간값을 리턴하기 때문에 최종적으로 최소 차이 값이 아닌 값이 나왔습니다.
• [0,null,2236,1277,2776,519] 값에서 원하는 정답은 519였다는 점입니다.
  • 즉, 519는 위의 노드 값 1277과의 차이 외에도 0과의 차이도 계산되어야 한다는게 핵심입니다.
  • 일단 시도 2에서 2가지 문제가 있음을 알게 되었습니다.
    • root.val-prev에서 절대값 처리가 필요없습니다. 중위순회이기 때문입니다.
    • 그리고 초기값 설정이 잘못되어 있습니다. 이진 탐색 트리에서 모든 노드의 값이 -10000 이상이라는 제약 조건이 주어졌을 때, prev 값을 -10000으로 설정하면 이진 탐색 트리의 루트 노드를 방문하기 전에도 이전 노드와 현재 노드 간의 차이를 구할 수 있습니다.

class Solution {
  int min=10000, prev=0;
  public int getMinimumDifference(TreeNode root) {
    if(root==null) return min;
    getMinimumDifference(root.left);
    if(prev!=0) min=Math.min(min, Math.abs(root.val-prev));
    prev=root.val;
    getMinimumDifference(root.right);

    return min;
  }
}

시도 3

위에 고민한 내용들을 반영한 통과 코드입니다.

• 시간복잡도: O(n)
• 공간복잡도: O(n)

class Solution {
  int prev = -100000, min = 100000;
  public int getMinimumDifference(TreeNode root) {
    if(root==null) return min;
    getMinimumDifference(root.left);
    min=Math.min(min, root.val-prev);
    prev=root.val;
    getMinimumDifference(root.right);
    return min;
  }
}

3. 다른 사람의 풀이

void inOrderTraversal 메소드로 반환 값은 없지만 min 값을 찾을 수 있게 하는 방식입니다.

• 중위 순회를 사용하면 BST의 노드를 오름차순으로 방문하므로 인접한 두 노드 간의 차이를 계산할 수 있습니다.
• 중위 순회를 사용하지 않고 다른 방식으로 트리를 순회하면 정렬된 순서대로 노드를 방문할 수 없으므로 최소 차이를 계산하기 어려워집니다.

class Solution {
    int min = Integer.MAX_VALUE;
    TreeNode prev = null;
    
    public int getMinimumDifference(TreeNode root) {
        inOrderTraversal(root);
        return min;
    }

    private void inOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        inOrderTraversal(node.left);

        if (prev != null) {
            min = Math.min(min, Math.abs(node.val - prev.val));
        }
        prev = node;

        inOrderTraversal(node.right);
    }
}

4. 생각해보기

이진 탐색 트리(BST)에 대하여 다시 정리해보면 다음 특징들을 가지고 있습니다.

• 모든 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.
• 왼쪽 서브트리의 모든 노드의 값은 부모 노드의 값보다 작습니다.
• 오른쪽 서브트리의 모든 노드의 값은 부모 노드의 값보다 큽니다.

---

33. Search in Rotated Sorted Array

1. 문제

문제 URL

2. 나의 풀이

시도 1

이 문제 역시 시간복잡도를 O(log n)로 고려해야 하는 방식이라 다음 해결방법은 적합하지 않습니다.

• 시간복잡도: O(n)
• 공간복잡도: O(n)

class Solution {
    public int search(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        for(int i:nums){
            list.add(i);
        }
        int index = list.indexOf(target);
        if(index==-1) return -1;
        else return index;
    }
}

시도 2

이진검색을 이용한 방법으로 다시 시도했습니다. left가 right보다 작거나 같은 동안 반복합니다.

• 중간 인덱스 계산: mid 변수에 left와 right의 중간 값인 (left + right) / 2를 할당합니다.
• 중간 값과 타겟 값 비교: nums[mid]가 target과 같으면 mid를 반환합니다.
  • 중간 값이 왼쪽 부분 배열에 속할 때:
    • 타겟이 왼쪽 부분 배열에 속하면, right 값을 mid - 1로 업데이트하여 오른쪽을 좁힙니다.
    • 그렇지 않으면, left 값을 mid + 1로 업데이트하여 왼쪽을 좁힙니다.
  • 중간 값이 오른쪽 부분 배열에 속할 때:
    • 타겟이 오른쪽 부분 배열에 속하면, left 값을 mid + 1로 업데이트하여 왼쪽을 좁힙니다.
    • 그렇지 않으면, right 값을 mid - 1로 업데이트하여 오른쪽을 좁힙니다.
• 탐색 실패: 반복문을 빠져나오면, 타겟 값을 찾지 못한 것이므로 -1을 반환합니다.

시간복잡도와 공간복잡도

• 시간복잡도: O(log n)
• 공간복잡도: O(n)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target <= nums[right] && target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

3. 다른 사람의 풀이

이진검색을 이용한 풀이는 제 풀이와 거의 유사했어서 다른 풀이를 찾아봤습니다. 이 문제 역시 시간복잡도를 O(log n)로 고려해야 하는 방식이라 다음 해결방법은 적합하지 않습니다. 하지만 시간복잡도를 고려하지 않는 선에서 사실 target만 찾으면 되기 때문에 이렇게 모두 비교한 풀이도 있었습니다.

• 시간복잡도: O(n)
• 공간복잡도: O(n)

class Solution {
  public int search(int[] nums, int target) {
    int n = nums.length ;
    for( int i = 0 ; i< n ; i++){
      if( nums[i]==target ){
        return i ;
      }
    }
    return -1;
  }
}

4. 생각해보기

일반적으로 이진 탐색은 정렬된 배열에서 사용되며, 정렬되지 않은 배열에서 사용하는 것은 적절하지 않습니다. 하지만, 이 문제에서는 주어진 배열이 회전된 상태이기 때문에, 배열의 일부분이 정렬되어 있고, 나머지 부분이 회전된 상태입니다. 이러한 상황에서도 이진 탐색을 사용할 수 있습니다.

시도 2 풀이에서는 회전된 부분 배열을 찾기 위해 nums[mid] >= nums[left]와 같은 조건문을 사용하였습니다. 이 조건문은 중간 값이 왼쪽 부분 배열에 속하는지 오른쪽 부분 배열에 속하는지를 판별합니다. 이러한 방식으로 이진 탐색을 이용하여 회전된 배열에서도 원하는 값을 찾을 수 있습니다.

---

153. Find Minimum in Rotated Sorted Array

1. 문제

문제 URL

• 문제에서 rotated라고 해서 헷갈릴수도 있지만 결국에서 주어진 배열 nums에서 가장 작은 요소의 인덱스를 반환하는 문제입니다.
• 가장 큰 요소를 구하는 162번 문제 참고

2. 나의 풀이

시도 1

이렇게 풀면 아주 간단하지만 시간복잡도를 O(log n)로 고려해야 하는 조건이 있음에 주의해야 합니다.

• 시간복잡도: O(n)
• 공간복잡도: O(1)

class Solution {
    public int findMin(int[] nums) {
        for(int i=0; i<nums.length-1; i++){
            if(nums[i]>nums[i+1]) return nums[i+1];
        }
        return nums[0];
    }
}

시도 2

이진검색을 이용한 방법으로 다시 시도했습니다.

• left와 right 변수를 사용하여 배열의 왼쪽과 오른쪽 끝점을 나타내고, mid 변수를 사용하여 중간 지점을 나타냅니다.
• while문에서는 left와 right가 같아질 때까지 반복하며, mid 지점의 값이 mid+1 지점의 값보다 큰 경우 mid+1 지점의 값을 반환하고, mid 지점의 값이 mid-1 지점의 값보다 큰 경우 mid 지점의 값을 반환합니다.
• 그리고 mid 지점의 값이 배열의 첫 번째 요소보다 큰 경우 left를 mid+1로 업데이트하고, 그렇지 않은 경우 right를 mid-1로 업데이트합니다.
• 결국 left 변수가 가리키는 위치가 회전된 배열에서 가장 작은 요소의 위치가 됩니다.

시간복잡도와 공간복잡도

• 시간복잡도: O(n)
• 공간복잡도: O(n)

class Solution {
  public int findMin(int[] nums) {
    int n = nums.length;
    if(n==1) return nums[0];

    int left = 0, right = n-1;
    if(nums[right]>nums[0]) return nums[0];

    while(left<right){
      int mid = left + (right-left)/2;
      if(nums[mid]>nums[mid+1]) return nums[mid+1];
      if(nums[mid-1]>nums[mid]) return nums[mid];
      if(nums[mid]>nums[0]){
        left = mid+1;
      } else {
        right = mid-1;
      }
    }
    return nums[left];
  }
}

3. 다른 사람의 풀이

같은 방법이지만 변수나 풀이가 더 깔끔하고 보기 좋아서 Solutions에 있는 풀이를 가지고 왔습니다.

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
}

4. 생각해보기

이진 검색을 사용하여 회전된 정렬된 배열에서 가장 작은 요소를 찾았습니다. 이진 검색을 사용할 때는 배열의 중간 값을 찾는 방법과, 이 값을 찾은 후에 어느 부분을 대상으로 검색을 진행할지를 결정하는 방법을 정확히 이해해야 합니다.

---

162. Find Peak Element

1. 문제

문제 URL

• Peek 요소의 인덱스를 반환하는 문제입니다.
• 문제에서는 O(log n)의 시간복잡도를 사용하라고 했음으로 모든 요소를 확인하는 방식보다 효율적인 알고리즘을 사용해야 합니다.

2. 나의 풀이

시도 1

평소대로 간단하게 Arrays.sort(nums); 정렬 후 List를 이용해 가장 큰 요소의 인덱스 값을 구하는 방식으로 풀이했습니다.

• 시간복잡도가 문제에서 제시한 크기보다 큽니다.
• 시간복잡도: O(n log n)
• 공간복잡도: O(n)

class Solution {
    public int findPeakElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for(int i:nums){
            list.add(i);
        }
        Arrays.sort(nums);
        int answer = list.indexOf(nums[nums.length-1]);
        return answer;
    }
}

시도 2

문제의 의도대로 시간복잡도를 줄이기 위해서는 이진탐색(Binary Search) 방식을 사용할 수 있습니다. 하지만 이렇게 풀이했을 때는 시간초과가 발생했습니다.

class Solution {
   public int findPeakElement(int[] nums) {
      int left=0, right=nums.length-1;
      int middle=(nums[left]+nums[right])/2;
      while(left<right){
         if(nums[middle-1]<nums[middle] && nums[middle+1]<nums[middle]) return middle;
         if(nums[middle-1]<nums[middle]) left=middle+1;
         else right=middle-1;
      }
      return left; 
   }
}

3. 다른 사람의 풀이

리턴값이 0이 나올 수 밖에 없는 값과 순서대로 정렬되어 있어 마지막 요소가 peak인 경우를 먼저 제외합니다. 그리고 while문으로 이진탐색을 수행합니다. 중간값 양옆의 값보다 중간값이 큰 경우는 중간값을 retrun합니다.

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if(n == 1 || nums[0] > nums[1]) return 0;
        if(nums[n - 1] > nums[n - 2]) return n - 1;
        int l = 0;
        int r = n - 1;
        while(l <= r)
        {
            int m = (l + r)/2;
            int minus = m == 0 ? Integer.MIN_VALUE : nums[m-1];
            int plusUltra = m == n - 1 ? Integer.MIN_VALUE : nums[m+1];
            if(minus < nums[m] && plusUltra < nums[m]) return m;
            if(minus < nums[m]) l = m + 1;
            else r = m - 1;
        }
        return l;
    }
}

---

148. Sort List

1. 문제

문제 URL

• 주어진 ListNode를 오름차순으로 정렬해서 ListNode로 리턴하는 문제입니다.
• ListNode는 val와 ListNode로 구성되어 있습니다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

2. 나의 풀이

시도 1

주어진 ListNode의 값들을 찾아 순서대로 List로 정렬하고 이 값들을 가지고 새로운 ListNode를 생성하는 과정으로 풀이했습니다.

• 하지만 문제의 Follow up에서는 공간복잡도가 O(1)인 방법으로 푸는 방식은 실패했습니다.
• 시간복잡도: O(n log n)
• 공간복잡도: O(n)

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null) return head;
        
        List<Integer> list = new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head = head.next;
        }
        Collections.sort(list);
        Collections.reverse(list);

        ListNode answer = new ListNode();
        for(int i=0; i<list.size(); i++){
            if(i==0) answer = new ListNode(list.get(i));
            else answer = new ListNode(list.get(i), answer);
        }
        return answer;
    }
}

3. 다른 사람의 풀이

공간복잡도가 O(1)가 나오는 풀이입니다. 연결 리스트를 병합 정렬로 정렬하는 함수입니다.

• dummy로 값이 0이고, next 노드가 주어진 head인 노드를 생성합니다.
• 그리고 노드 배열형태인 sublists, sublist_tail을 만들고, 하위 리스트(sublist)의 크기를 1, 2, 4, 8, … 등으로 증가시키면서, 연결 리스트를 분할하고 병합합니다.
• 추가적인 배열을 사용하지 않고, 주어진 연결 리스트 내에서 정렬을 수행하므로, 공간 복잡도는 O(n)입니다.
  • sublists와 sublists_tail은 추가적인 배열입니다.
  • 하지만 이 배열들의 크기는 상수값인 2로 고정되어 있으며, 입력 리스트의 크기와는 무관합니다.
  • 따라서 입력 리스트의 크기에 비례하는 공간을 추가로 사용하지 않고, 상수 크기의 공간만을 사용하므로, 공간 복잡도는 O(1)이 됩니다.

public ListNode sortList(ListNode head) {
  ListNode dummy = new ListNode(0);
  dummy.next = head;

  ListNode [] sublists = new ListNode[2];
  ListNode [] sublists_tail = new ListNode[2];

  // Grab sublists of size 1, then 2, then 4, etc, until fully merged
  for (int steps = 1;; steps *= 2) {
    // Record the progress of the current pass into a single semi sorted list by updating
    // the next of the previous node (or the dummy on the first loop)
    ListNode prev = dummy;

    // Keep track of how much is left to process on this pass of the list
    ListNode remaining = prev.next;

    int num_loops = 0;
    for (; null != remaining; ++num_loops) {
      // Split 2 sublists of steps length from the front
      for (int i = 0; i < 2; ++i) {
        sublists[i] = remaining;
        sublists_tail[i] = null;
        for (int j = 0; null != remaining && j < steps; ++j) {
          sublists_tail[i] = remaining;
          remaining = remaining.next;
        }
        // Ensure the subslist (if one was made) is terminated
        if (null != sublists_tail[i]) {
          sublists_tail[i].next = null;
        }
      }

      // We have two sublists of (upto) length step that are sorted, merge them onto the end into a single list of (upto) step * 2
      while (null != sublists[0] && null != sublists[1]) {
        if (null == sublists[1] || sublists[0].val <= sublists[1].val) {
          prev.next = sublists[0];
          sublists[0] = sublists[0].next;
        } else {
          prev.next = sublists[1];
          sublists[1] = sublists[1].next;
        }
        prev = prev.next;
      }   

      // One list has been finished, attach what ever is left of the other to the end
      if (null != sublists[0]) {
        prev.next = sublists[0];
        prev = sublists_tail[0];
      } else {
        prev.next = sublists[1];
        prev = sublists_tail[1];
      }
    }

    // If the entire list was full processed in a single loop, it means we've completely sorted the list and are done
    if (1 >= num_loops) {
      return dummy.next;
    }
  }
}

다른 풀이는 연결 리스트의 요소를 배열에 저장한 다음 배열을 정렬하고 정렬된 배열의 값을 연결 리스트에 업데이트했습니다. Arrays.sort(arr);로 정렬하는 방식이 제 풀이와 유사했습니다.

• 시간복잡도: O(n log n)
• 공간복잡도: O(n)

class Solution {
    public ListNode sortList(ListNode head) {
        int count = 0;
        ListNode temp = head;
        while(temp!=null){
            count++;
            temp = temp.next;
        }
        int[] arr = new int[count];
        temp = head;
        count = 0;
        while(temp!=null){
            arr[count++] = temp.val;
            temp = temp.next;
        }
        Arrays.sort(arr);
        temp = head;
        count = 0;
        while(temp!=null){
            temp.val = arr[count++];
            temp = temp.next;
        }
        return head;
    }
}

4. 생각해보기

추가적인 배열을 사용하지 않고, 주어진 연결 리스트 내에서 정렬을 수행해 공간복잡도를 작게 만들 수 있다는 것을 알게 되었습니다. 상수 크기의 공간만을 사용하는 경우, 입력 크기가 어떻게 변하더라도 추가적인 메모리 사용량이 일정하게 유지됩니다.

---

242. Valid Anagram

1. 문제

문제 URL

• 이 문제는 주어지는 두 개의 문자열이 Anagram인지를 확인하는 문제입니다.
• 여기서 Anagram이란 문자열 내의 문자를 다르게 배치해서 새로운 문자열을 만드는 것으로 주어진 문자열을 모두 사용해야 합니다.

2. 나의 풀이

시도 1

HashMap을 이용한 풀이입니다.

• "hhbywxfzydbppjxnbhezsxepfexkzofxyqdvcgdvgnjbvih...와 같이 긴 테스트 케이스 41번에서 실패했습니다.
  • s_map과 t_map은 동일하게 요소가 들어간 것을 확인했으나 일부 테스트케이스 return 값이 틀렸습니다.
  • if(s.length()!=t.length()) return false; 여기 부분이 false를 반환하면서 생긴 문제였습니다.

시간복잡도와 공간복잡도

• 시간복잡도: O(n)
• 공간복잡도: O(n)

class Solution {
  public boolean isAnagram(String s, String t) {
    Map<Character, Integer> s_map = makeMap(s);
    Map<Character, Integer> t_map = makeMap(t);
    
    if(s.length()!=t.length()) return false;

    for(int i=0; i<t.length(); i++){
      char c = t.charAt(i);
      if(!s_map.containsKey(c)) return false;
      if(s_map.get(c)!=t_map.get(c)) return false;
    }
    return true;
  }

  public Map<Character, Integer> makeMap(String str){
    Map<Character, Integer> map = new HashMap<>();
    for(int i=0; i<str.length(); i++){
      char c = str.charAt(i);
      if(map.containsKey(c)) map.put(c, map.get(c)+1);
      else map.put(c, 1);
    }
    return map;
  }
}

// s_map
{a=1913, b=2003, c=2000, d=1916, e=1978, f=1880, g=1949, h=1943, i=1949, j=1891, k=1923, 
        l=1922, m=1936, n=1978, o=1869, p=1874, q=1875, r=1985, s=1897, t=1838, u=1879, 
        v=1905, w=1940, x=1942, y=1915, z=1900}
// t_map        
{a=1913, b=2003, c=2000, d=1916, e=1978, f=1880, g=1949, h=1943, i=1949, j=1891, k=1923, 
        l=1922, m=1936, n=1978, o=1869, p=1874, q=1875, r=1985, s=1897, t=1838, u=1879, 
        v=1905, w=1940, x=1942, y=1915, z=1900}
        
50000
50000
// if(s.length()!=t.length()) return false;        
false

3. 다른 사람의 풀이

Arrays.sort를 이용해서 간단하게 풀이한 코드입니다. HashTable로의 구현만 생각하고 있어서 오히려 떠올리지 못했는데 이게 더 빠른 접근법이 될 것 같습니다.

• 시간복잡도: O(n)
• 공간복잡도: O(n)

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        Arrays.sort(sChars);
        Arrays.sort(tChars);
        return Arrays.equals(sChars, tChars);
    }
}

Hash Table을 이용한 방식도 있었습니다. .getOrDefault() 메서드로 더 간결하게 코드를 구현했고 문자열 s의 요소로 map에 추가, t의 요소로 map에서 차감하는 방식입니다. 그리고 마지막에는 value의 값이 0이 아닌 경우는 다 anagram을 만족하지 못하므로 false를 리턴합니다.

• 시간복잡도: O(n)
• 공간복잡도: O(n)

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> count = new HashMap<>();
        
        for (char x : s.toCharArray()) {
            count.put(x, count.getOrDefault(x, 0) + 1);
        }
        
        for (char x : t.toCharArray()) {
            count.put(x, count.getOrDefault(x, 0) - 1);
        }
        
        for (int val : count.values()) {
            if (val != 0) {
                return false;
            }
        }
        
        return true;
    }
}

4. 생각해보기

.getOrDefault(x, 0)를 이용한 풀이를 그 동안 코딩테스트 공부를 안하고 있어서 기억하지 못했는데 자료구조별로 필요한 메서드를 정리할 필요성을 느꼈습니다.

---

383. Ransom Note

1. 문제

문제 URL

• 두 개의 문자열 ransomNote와 magazine가 주어졌을 때, ransomNote로 magazine을 만들 수 있는지 여부를 반환합니다.
• 두 문자열은 모두 영어 소문자로 간주합니다.

2. 나의 풀이

Hash Table을 이용한 방식으로 ransomNote와 magazine을 map으로 만들고 ransomNote를 만들 수 있는지 체크했습니다.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> ransomNote_map = makeMap(ransomNote);
        Map<Character, Integer> magazine_map = makeMap(magazine);

        for(int i=0; i<ransomNote.length(); i++){
            char c = ransomNote.charAt(i);
            if(!magazine_map.containsKey(c)) return false;
            if(ransomNote_map.getOrDefault(c,0)>magazine_map.getOrDefault(c,0)) return false;
        }
        return true;
    }

    public Map<Character, Integer> makeMap(String str){
        Map<Character, Integer> map = new HashMap<>();
        for(int i=0; i<str.length(); i++){
            char c = str.charAt(i);
            if(map.containsKey(c)) map.put(c, map.get(c)+1);
            else map.put(c, 1);
        }
        return map;
    }
}

3. 다른 사람의 풀이

제가 푼 접근법보다 빠르고 간단한 방법으로 .toCharArray()를 이용한 풀이입니다.

• 먼저, magazine 문자열에서 각 문자의 출현 빈도수를 저장하기 위해 charCounts라는 길이 26의 정수 배열을 생성합니다. 이 배열은 소문자 영어 알파벳을 가정하고 있습니다.
• 다음으로, magazine 문자열을 순회하면서 각 문자의 출현 빈도수를 charCounts에 저장합니다.
• 그 후, ransomNote 문자열을 순회하면서 각 문자가 charCounts에 있는지 확인합니다.
  • 만약 charCounts에 해당 문자가 없다면, ransomNote를 만들 수 없기 때문에 false를 반환합니다.
  • 그렇지 않으면, charCounts에서 해당 문자의 출현 빈도수를 하나 줄입니다.
• 만약 ransomNote의 모든 문자를 순회했다면, ransomNote를 만들 수 있기 때문에 true를 반환합니다.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] charCounts = new int[26]; // Assuming lowercase English letters
        
        for (char c : magazine.toCharArray()) {
            charCounts[c - 'a']++;
        }

        for (char c : ransomNote.toCharArray()) {
            if ( !(charCounts[c - 'a'] > 0 ) ) {
                return false;
            } 
                charCounts[c - 'a']--;
        }
        
        return true;
    }
}

4. 생각해보기

과제에서는 Hash Table로 분류되어 있었지만 구현이 쉬운 다른 방법들도 고민해봐야할 것 같습니다.

---

219. Contains Duplicate 2

1. 문제

문제 URL

• 배열 nums와 정수 k가 주어졌을 때 거리 k 내에 떨어져 있는 동일한 요소가 있는지 여부를 확인합니다.
• 있으면 true, 없으면 false

2. 나의 풀이

시도 1

HashMap을 이용한 풀이입니다. 배열에서 동일한 값이 나오면 요소는 키로 그 인덱스는 값을 list로 받아서 넣어줍니다.

class Solution {
  public boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for(int i=0; i<nums.length; i++){
      if(map.containsKey(nums[i])){
        int a = map.get(nums[i]);
        if(i-a<=k) return true;
      }
      map.put(nums[i], i);
    }
    return false;
  }
}

3. 다른 사람의 풀이

HashTable 방식은 다른 사람들 풀이와 비슷했습니다.
아래 알고리즘은 슬라이딩 윈도우(sliding window) 방식을 사용합니다. 실제로 HashTable 방식보다 빨랐고 메모리 사용량도 다소 작았습니다.

• 윈도우의 앞쪽은 i 번째 요소이며, 뒤쪽은 k 거리만큼 떨어진 요소입니다. 이 윈도우 내에 있는 요소들은 Set을 사용하여 유지됩니다.
• 새로운 요소를 Set에 추가할 때, add() 메서드가 false를 반환하면 이미 Set에 해당 요소가 존재하는 것입니다. 이 경우, 중복된 값이 존재하므로 true를 반환합니다.
• for 루프에서 return true가 실행되지 않고 루프가 종료되면, 중복된 값이 없다는 것을 의미합니다.

public boolean containsNearbyDuplicate(int[] nums, int k) {
  Set<Integer> set = new HashSet<Integer>();
  for(int i = 0; i < nums.length; i++){
      if(i > k) set.remove(nums[i-k-1]);
      if(!set.add(nums[i])) return true;
  }
  return false;
}

4. 생각해보기

중복된 값을 찾는 문제와 같이 슬라이딩 윈도우 방식으로 해결할 수 있는 문제가 있다면, HashTable보다 더 효율적일 수 있습니다. 슬라이딩 윈도우 방식이 고정된 크기의 윈도우를 사용하여 데이터를 처리하기 때문에, 공간 복잡도와 시간 복잡도가 더 효율적일 수 있기 때문입니다.

---

1. Two Sum

1. 문제

문제 URL

• nums 배열에서 target 값을 만들기 위한 인덱스 순서를 배열로 반환하는 문제입니다.
• 167번 문제와 달리 nums가 정렬되지 않은 상태로 주어집니다.
• 배열 내 요소는 한 번만 사용될 수 있습니다.

2. 나의 풀이

가장 간단하게 for문으로 풀이했는데, 문제에서 원하는 시간복잡도 O(n^2) 미만 그리고 Hash Table을 이용한 방법을 찾지 못했습니다.

• 시간복잡도: O(n^2)
• 공간복잡도: O(n)

class Solution {
  public int[] twoSum(int[] nums, int target) {
    List<Integer> list = new ArrayList<>();
    for(int i:nums){
      list.add(i);
    }
    int i=0, a=0, b=0;
    for(i=0; i<nums.length; i++){
      a = target-nums[i];
      b = list.lastIndexOf(a);
      if(a>0 && b!=-1 && b!=i){
        break;
      }
    }
    return new int[]{i, b};
  }
}

3. 다른 사람의 풀이

Hash Table을 이용한 풀이입니다. 처음에는 왜 굳이 Map 처리를 하는가에 대해 생각했었는데 키-값 쌍 조회이므로 오히려 빠른 풀이가 될 수 있습니다.

• 먼저 HashMap 안에 target과의 차이만큼을 가지는 키 값이 있는지 확인하고 있다면 그 인덱스 배열을 반환합니다.
• 없다면, i의 값을 키로 하는 요소를 추가합니다.

시간복잡도와 공간복잡도

• 시간복잡도: O(n)
• 공간복잡도: O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[]{numMap.get(complement), i};
            }
            numMap.put(nums[i], i);
        }

        return new int[]{}; // No solution found
    }
}

4. 생각해보기

모든 키를 찾아야 하는 문제가 아니고 후보 키를 얻을 수 있는 문제이기 때문에 오히려 HashMap을 이용하는게 빠르다는 결론을 알 수 있습니다.

---

150. Evaluate Reverse Polish Notation

1. 문제

문제 URL

• Polish Notation tokens이 주어지고 결과값을 반환합니다.
• 0으로 나누는 일은 없고, 답과 모든 중간 계산은 32비트 정수로 표현될 수 있습니다.

2. 나의 풀이

시도 1

왜 역 폴란드 표기법을 사용하는 것인지 찾다가 위키 글을 토대로 코드를 작성하게 되었습니다. stack을 사용한 구현으로 괄호가 많은 계산식에서 오히려 역 폴란드 표기법을 사용하면 계산을 쉽게 만들 수 있습니다.

• EmptyStackException이 발생
  • Character.isDigit를 사용하는 경우 -11을 숫자로 보지 않는 경우가 발생했기 때문이었습니다.

class Solution {
  public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    int next;
    for(String s:tokens){
      if(Character.isDigit(s.charAt(0))){
        stack.push(Integer.parseInt(s));
      }
      else{
        int b = stack.pop();
        int a = stack.pop();

        if("+".equals(s)) stack.push(a+b);
        else if("-".equals(s)) stack.push(a-b);
        else if("*".equals(s)) stack.push(a*b);
        else stack.push(a/b);
      }
      System.out.println(stack);
    }
    return stack.pop();
  }
}

시도 2

다른 부분은 문제가 없는데 EmptyStackException이 발생하지 않도록 Character.isDigit 대신 사칙연산 기호 여부를 체크해서 조건을 거는 것으로 변경했습니다.

if("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s))

3. 다른 사람의 풀이

나머지 전체적인 풀이는 Stack 방식과 유사하나 메서드를 빼거나 사칙연산을 다음 코드처럼 set에 넣어서 확인하는 방법 등이 있었습니다. 코드가 길어진다면 가독성을 위해 계산부분을 메서드로 빼는 것도 좋은 방법이라는 생각이 들었습니다.
Deque를 이용한 풀이도 있었는데 기본적으로 Stack 구조만을 생각했는데 알고리즘 공부를 하다가 보면 Deque를 사용한 풀이도 꽤 많은 것 같아 참고하면 좋을 것 같습니다.

class Solution {
  public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    Set<String> ops = Set.of("+", "-", "*", "/");

    for (String s : tokens) {
      if (ops.contains(s)) {
        int a = stack.pop();
        int b = stack.pop();
        int c = 0;

        switch(s) {
          case "+" -> {c = b + a;}
          case "-" -> {c = b - a;}
          case "*" -> {c = b * a;}
          case "/" -> {c = b / a;}
        }
        stack.push(c);
      }
      else stack.push(Integer.parseInt(s));
    }
    return stack.peek();
  }
}

// TC: O(n), SC: O(n)

4. 생각해보기

Deque는 스택과 큐의 형태 모두 구현이 가능한 자료구조입니다. 양쪽 끝에서 원소의 삽입과 삭제가 가능합니다. 그리고 ArrayDeque는 동적으로 크기를 조절하는 배열 기반의 Deque 구현체이며, LinkedList는 연결 리스트 기반의 Deque 구현체입니다.

• 그렇다면 스택 또는 큐보다 Deque를 썼을 때 더 적합한 문제가 있을까?라는 질문에 ChatGPT는 답을 찾지 못했습니다.

---

155. Min Stack

1. 문제

문제 URL

• 스택을 구현하는 문제로 push, pop, top 그리고 가장 작은 원소를 동시에 검색할 수 있어야 합니다.

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

2. 나의 풀이

시도 1

기존에 구현에 대한 부분을 고민해봤을 때 LinkedList는 주소로 다음 리스트와 연결되어 있는 반면, ArrayList는 선형 구조로 되어 있기 때문에 O(n)만큼의 시간복잡도가 생깁니다. 메모리가 무한하다고 가정했을 때 LinkedList의 경우 더 무한히 새로운 자료를 삽입할 수 있다는 장점이 있습니다. ArrayList는 자료의 삽입, 삭제 과정에서 메모리 낭비가 발생합니다.
물론 여기서는 단순 stack의 구현이지만, 이 stack을 누군가 쓴다는 가정하에 LinkedList로 stack을 구현했습니다.

class MinStack {
  LinkedList<Integer> list;

  public MinStack() {
    list = new LinkedList<>();
  }

  public void push(int val) {
    list.push(val);
  }

  public void pop() {
    list.removeFirst();
  }

  public int top() {
    return list.peekFirst();
  }

  public int getMin() {
    LinkedList<Integer> sortedList =  new LinkedList<>(list);
    Collections.sort(sortedList);
    return sortedList.peekFirst();
  }
}

3. 다른 사람의 풀이

TplusMin라는 클래스를 두어 min 값도 저장하면서 마지막에 getMin()처리시 별도 정렬이 필요하지 않다는 점이 훨씬 효율적이라는 생각이 들었습니다. 이렇게 되면 단순히 push 처리에서만 신경을 써도 되기 때문입니다.

class MinStack {
    LinkedList<TplusMin> stack;
    private class TplusMin {
        int val;
        int min;
        public TplusMin(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }

    public MinStack() {
        stack = new LinkedList<>();
    }
    
    public void push(int val) {
        int newMin;
        if (stack.size() == 0){
            newMin = val;
        }
        else {
            int currentMin = stack.getFirst().min;
            newMin = val < currentMin ? val : currentMin;
        }
        stack.addFirst(new TplusMin(val, newMin));
    }
    
    public void pop() {
        stack.removeFirst();
    }
    
    public int top() {
        return stack.peekFirst().val;
    }
    
    public int getMin() {
        return stack.peekFirst().min;
    }
}

4. 생각해보기

단순히 stack을 구현한다고 했을 때 list에 저장될 값을 1가지 타입이 아닌 클래스로 정의해서 원하는 자료구조로 만들어 처리하는 방법을 익혔고 꼭 자료구조 아니여도 다른 코드를 작성할 때도 간단한 class 단위 객체로 저장하는 방식에 대해 고민해보게 되었습니다.

---

3. Longest Substring Without Repeating Characters

1. 문제

문제 URL

• 반복을 포함하지 않는 문자열로 잘랐을 때 최대 길이를 구하는 문제입니다.

2. 나의 풀이

시도 1

말그대로 substring하는 방식으로 접근했었는데 index 범위를 넘어서 이 접근이 아닌 다른 방식으로 시도해야겠다고 생각했습니다.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int answer = 1;
        for(int i=0; i<s.length()-1; i++){
            int j=i+1;
            while(j<s.length()){
                j++;
                String substring = s.substring(i,j);
                if(substring.indexOf(""+s.charAt(j))==-1){
                    answer = Math.max(answer, j-i);
                }
                else break;                
            }
        }
        return answer;
    }
}

시도 2

209번 문제에서 배운 슬라이딩 윈도우 개념으로 생각해봤습니다.
슬라이딩 윈도우는 연속된 데이터 구조에서 고정 크기의 윈도우를 움직이면서 특정 조건을 만족하는 부분 구간을 탐색하는 알고리즘 기법입니다.

• 코드 내에서 i와 j 두 개의 인덱스를 사용하여 슬라이딩 윈도우를 형성하고, seen 배열을 사용하여 각 문자의 중복 여부를 확인하고 있습니다.
• i는 슬라이딩 윈도우의 왼쪽 끝을, j는 슬라이딩 윈도우의 오른쪽 끝을 나타냅니다.
• 이 때 j는 반복문을 통해 슬라이딩 윈도우의 오른쪽으로 이동하며 조건을 검사합니다.
• 여기서 128은 아스키 코드 기준입니다.

시간복잡도와 공간복잡도

• 시간복잡도: O(n^2)
• 공간복잡도: O(1)

  class Solution {
  public int lengthOfLongestSubstring(String s) {
    int answer = 0;
    for (int i=0; i<s.length(); i++) {
      boolean[] seen = new boolean[128];  
      int j=i;
      while (j<s.length() && !seen[s.charAt(j)]) {
        seen[s.charAt(j)] = true;
        j++;
      }
      answer = Math.max(answer, j-i); 
    }
    return answer;
  }
  }
  

3. 다른 사람의 풀이

위의 풀이와 비슷한데 이 경우는 int[] 배열을 이용해 비교여부를 체크하고 있습니다.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLength = 0;
        int[] charIndex = new int[128];
        Arrays.fill(charIndex, -1);
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            if (charIndex[s.charAt(right)] >= left) {
                left = charIndex[s.charAt(right)] + 1;
            }
            charIndex[s.charAt(right)] = right;
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

4. 생각해보기

실상 단어가 맞는지 다 확인해야할 것 같지만 그럴 필요가 없다는 것을 알게 되었습니다. 어차피 중복을 피하기 위한 하나의 문자로 체크한다고 해도 같은 결과를 가지고 올 수 있기 때문입니다. 슬라이딩 윈도우 개념과 방법들을 숙지할 필요가 있습니다. 하지만 이 방법은

---

209. Minimum Size Subarray Sum

1. 문제

문제 URL

• 배열의 요소들의 합으로 target이 되기 위한 서브 배열의 최소 길이를 구하는 문제입니다.
• 배열 nums는 정렬되지 않았습니다.
• 서브배열이 없는 경우에는 0을 return 합니다.
• 시간복잡도가 O(n) 또는 O(n log n)인 방법을 찾아습니다.

2. 나의 풀이

시도 1

이중루프 밖에 생각나지 않아서 이렇게 시도했지만 역시나 시간초과로 실패했습니다.

• 시간복잡도: O(n log n)
• 공간복잡도: O(1)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        if(Arrays.binarySearch(nums, target)>=0) return 1;
        int j=1, cnt=0;
        boolean b = false;
        for(int i=0; i<nums.length; i++){
            int value = nums[i];
            j = i+1;
            while(true){
                if(j<=nums.length-1) value += nums[j];
                if(target==value){
                    b=true;
                    break;
                }
                if(j==nums.length-1 || target<value) break;
            }
            if(b) cnt = j-i+1;
        }
        return cnt;
    }
}

3. 다른 사람의 풀이를 보고 개선하기

슬라이딩 윈도우를 이용한 풀이었는데, 앞에서 나의 풀이와 같이 for문과 while문을 함께 쓰는 방식인데 효율적이라는 부분이 달랐습니다.

먼저 서브배열이 없는 경우 0을 반환합니다. 그리고 부분 배열의 합이 target 이상이 되도록 left 포인터를 이동시키면서 최소 길이를 갱신합니다.

• 시간복잡도: O(n)
• 공간복잡도: O(1)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int left = 0;
        int minLength = Integer.MAX_VALUE;
        int currentSum = 0;

        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];

            while (currentSum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                currentSum -= nums[left];
                left++;
            }
        }

        if (minLength != Integer.MAX_VALUE) 
            return minLength;
        else 
            return 0;
    }
}

4. 생각해 볼 부분

두 포인터를 이용한 방법과는 약간 상이했는데, 슬라이딩 윈도우를 사용하는 방법에 좀 더 능숙해져야 겠다고 생각했습니다.

---

167. Two Sum 2 Input Array Is Sorted

1. 문제

문제 URL

• 정렬된 배열 내 두 요소를 더한 값으로 원하는 값을 만드는 문제입니다.
• 이 때 그 배열 내 두 요소의 순서 쌍을 return 합니다.

2. 나의 풀이

시도 1

Arrays.binarySearch로 짝이 되는 index를 구할 수 있었습니다.

• 이렇게 풀었을 때 기본적인 예제는 다 통과했지만, [5,25,75]에서 100이 될 수 있는 값을 찾는 것에서 실패했습니다.
• output이 [1,-3]이 나왔는데 indexOf와 착각하고 -1만을 반환한다고 가정했기 때문입니다.
  • Arrays.binarySearch은 찾지 못한 경우 음수 값을 반환합니다. 반환 값은 key의 정확한 위치가 아니라 key를 삽입해야 할 위치에 대한 음수 값을 반환합니다.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i=0, j=0;
        for(i=0; i<numbers.length; i++){
            j = Arrays.binarySearch(numbers, target-numbers[i]);
            if(j>0) break;
        }
        return new int[]{i+1, j+1};
    }
}

시도 2

위에서 Arrays.binarySearch의 음수 문제, 동일한 숫자가 연속으로 있을 때의 같은 인덱스 반환문제, 반환 배열의 정렬문제 등을 고려해서 코드를 수정했습니다.

• 시간복잡도: O(n log n)
• 공간복잡도: O(1)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i=0, j=0;
        for(i=0; i<numbers.length; i++){
            j = Arrays.binarySearch(numbers, target-numbers[i]);
            if(j>=0 && i!=j) break;
        }
        if(i<j) return new int[]{i+1, j+1};
        else return new int[]{j+1, i+1};
    }
}

3. 다른 사람의 풀이를 보고 개선하기

주어진 nums 배열이 정렬된 값이므로 양쪽의 값을 더해서 target보다 작은지 큰지에 따라 포인터를 변경해주는 방식이었습니다. 코드도 훨씬 깔끔하고 이 접근법을 기억해두는게 좋겠다는 생각이 들었습니다.

class Solution {
  public int[] twoSum(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (nums[l] + nums[r] != target) {
      if (nums[l] + nums[r] < target)
        l++;
      else
        r--;
    }
    return new int[]{l + 1, r + 1};
  }
}

4. 생각해 볼 부분

참고한 풀이 작성자가 쓴 내용에서 정렬된 배열이 주어졌을 때 고려해볼 내용으로 다음 내용들을 추천했습니다. 이 문제에서는 두 포인터를 이용한 방식을 사용한 방법이었습니다.

• 이진 검색
• 두 개(또는 세 개)의 포인터
• 슬라이딩 윈도우
  • 슬라이딩 윈도우 알고리즘의 핵심 아이디어는 윈도우의 시작과 끝을 조절하면서 필요한 연산을 수행하는 것입니다. 이를 통해 불필요한 계산을 줄이고, 문제의 복잡도를 줄이며, 효율적으로 문제를 해결할 수 있습니다.
• 오른쪽부터 순회

---

125. Valid Palindrome

1. 문제

문제 URL

• Palindrome인지를 찾는 문제입니다. 예를 들어 토마토, 기러기, 우영우 같은 문자열 여부를 확인합니다.
  • true or false로 반환
• 특수문자와 공백은 제외하고 영자 대소문자는 동일하게 간주합니다.
• " " 빈 문자열도 Palindrome으로 간주합니다.

2. 나의 풀이

시도 1

문자열을 char[] 배열로 변환해서 뒤의 배열의 값과 비교하는 방식으로 풀이했습니다.

• 이 경우, 458 / 485 테스트케이스는 통과했지만 0P는 통과하지 못했습니다.
  • 문제에서 Alphanumeric characters include letters and numbers.로 숫자도 고려해야 하므로 수정이 필요했습니다.

class Solution {
    public boolean isPalindrome(String s) {
        if(s.isEmpty()) return true;
        int end = s.length()-1;
        char[] arr = s.toCharArray();
        for(int i=0; i<arr.length/2; i++){
            if(!(arr[i] >= 'A' && arr[i] <= 'Z') && !(arr[i] >= 'a' && arr[i] <= 'z'))
                continue;
            while(true){
                if((arr[end] >= 'A' && arr[end] <= 'Z') || (arr[end] >= 'a' && arr[end] <= 'z'))
                    break;
                else end--;    
            }
            if(Character.toLowerCase(arr[i]) != Character.toLowerCase(arr[end]))            
                return false;
            else end--;
        }
        return true;
    }
}

시도 2

위 코드에서 숫자를 다시 반영한 코드로 작성했지만 시간초과가 발생했습니다.

• !(start >= 0 && start <= 9) && !(start >= 'a' && start <= 'z')

class Solution {
    public boolean isPalindrome(String s) {
        if(s.isEmpty()) return true;
        int end = s.length()-1;
        char[] arr = s.toCharArray();
        for(int i=0; i<arr.length/2; i++){
            int start = Character.toLowerCase(arr[i]);
            int compare = Character.toLowerCase(arr[end]);
            if(!(start >= 0 && start <= 9) && !(start >= 'a' && start <= 'z'))
                continue;
            while(true){
                if((compare >= 0 && compare <= 9) || (compare >= 'a' && compare <= 'z'))
                    break;
                else end--;    
            }
            if(start != compare) return false;
            else end--;
        }
        return true;
    }
}

시도 3

이중 반복문 때문에 발생한 것 같아서 다른 방법을 생각해보게 되었습니다. while문으로 처리하지 않고 미리 s의 숫자와 영문자 외 다른 문자는 공백처리하는 방법입니다.

• 이 경우, 462 / 485 테스트케이스는 통과했지만 0P는 통과하지 못했습니다.
  • if(!(arr[i] >= 0 && arr[i] <= 9) && !(arr[i] >= 'a' && arr[i] <= 'z')) arr[i]=' ';
  • 이 부분에서 0을 공백처리하고 있었는데, if(!(arr[i] >= '0' && arr[i] <= '9') && !(arr[i] >= 'a' && arr[i] <= 'z')) arr[i]=' '; }로 변경해주었습니다.

결과적으로 통과는 했지만 마음에 드는 풀이는 아니었습니다.

• 시간복잡도: O(n)
• 공간복잡도: O(n)

class Solution {
    public boolean isPalindrome(String s) {
        if(s.isEmpty()) return true;
        s = s.toLowerCase();
        char[] arr = s.toCharArray();
        for(int i=0; i<arr.length; i++){
            if(!(arr[i] >= '0' && arr[i] <= '9') && !(arr[i] >= 'a' && arr[i] <= 'z')) arr[i]=' ';
        }
        String str = String.valueOf(arr).replaceAll(" ", "");
        arr = str.toCharArray();
        for(int i=0, j=arr.length-1; i<arr.length/2; i++, j--){
            if(arr[i]!=arr[j]) return false;
        }
        return true;
    }
}

3. 다른 사람의 풀이를 보고 개선하기

Character.isLetterOrDigit를 사용해서 코드를 확실히 깔끔하게 처리한 것을 볼 수 있었습니다. 그리고 저는 배열로 변환했다가 문자열로 합치는 과정을 거쳤는데 그냥 반복문을 돌면서 문자열의 문자 위치를 left와 right로 처리해서 비교하는 법을 배웠습니다.

• 시간복잡도: O(n)
• 공간복잡도: O(1)

class Solution {
   public boolean isPalindrome(String s) {
        if (s.isEmpty()) {
            return true;
        }

        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            char leftChar = s.charAt(left);
            char rightChar = s.charAt(right);

            if (!Character.isLetterOrDigit(leftChar)) {
                left++;
            } else if (!Character.isLetterOrDigit(rightChar)) {
                right--;
            } else {
                if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) {
                    return false;
                }
                left++;
                right--;
            }
        }

        return true;
    }
}

4. 생각해 볼 부분

너무 복잡하게 생각하지 말고, 기존 문자열을 최대한 변환하지 않는 선에서 문제를 풀어야겠다는 생각이 들었습니다.

---

169. Majority Element

1. 문제

문제 URL

• 배열에서 최대 빈도 값을 구하는 문제입니다.
• 최빈값은 적어도 배열의 길이/2 이상의 빈도를 갖습니다.
• 추가로 시간복잡도 O(n), 공간복잡도 O(1)의 방법으로 풀 수 있는지 알아보는 문제입니다.

2. 나의 풀이

먼저 제가 생각한 방식은 map에 같은 키를 가지는 값을 넣어주고 중복된 키를 갖는 경우 중복된 수를 값으로 넣어주는 방식이었습니다. 통과는 했지만 문제에서 고려해봐야할 복잡도 부분에서는 부족했습니다.

• 시간 복잡도: O(n + n log n)
• 공간 복잡도: O(n)

class Solution {
  public int majorityElement(int[] nums) {
    int limit = nums.length/2;
    Map<Integer, Integer> map = new HashMap<>();
    for(int i:nums){
      if(map.containsKey(i) map.put(i, map.get(i)+1);
      else map.put(i, 1);
    }
    List<Integer> keySet = new ArrayList<>(map.keySet());
    keySet.sort((o1, o2) -> map.get(o2).compareTo(map.get(o1)));
    return keySet.get(0);
  }
}

3. 다른 사람의 풀이를 보고 개선하기

Arrays.sort(nums) 이용하기
가장 먼저 본 풀이는 이 방법이었는데 이렇게 된다고 하는 생각이 들었지만, 생각해보니 limit 부분을 문제 풀면서 잊고 있었습니다. 최대 빈도 값은 배열의 길이/2 이상의 빈도를 갖기 때문에 정렬로 중앙값만 도출해도 값은 값이 나올 수 있는 문제였습니다. 하지만 원하는 시간, 공간 복잡도는 아니였습니다.

• 시간 복잡도: O(n log n)
• 공간 복잡도: O(1)

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return nums[n/2];
    }
}

Moore Voting Algorithm
과반수 요소를 구하기 위한 Moore Voting Algorithm입니다.

• 변수 candidate를 과반수 요소 후보로 초기화하고, count를 0으로 초기화합니다.
  • 배열을 순회하면서 각 요소에 대해 다음을 수행합니다.
  • 만약 count가 0이라면 현재 요소를 candidate로 설정합니다.
  • 만약 현재 요소가 candidate와 같다면 count를 증가시킵니다.
  • 그렇지 않으면 count를 감소시킵니다.
• 시간 복잡도: O(n)
• 공간 복잡도: O(1)

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;
        
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}

4. 생각해 볼 부분

Moore Voting Algorithm이 생소했는데 이번 기회에 과반수 이상의 요소를 구하기 위해 좋은 알고리즘에 대해 공부하게 되었습니다.
위에서 가장 이해되지 않았던 부분이 candidate = num; 부분이었는데 처음에 값을 넣는 건 당연했지만 값을 넣은 이후에 다른 요소로 빈도로 그 값(count)을 줄이고 0이 되면 다른 요소를 후보자로 넣는다는게 처음에 이해되지 않았습니다.

하지만 간단하게 예제로 주어진 배열 2,2,1,1,1,2,2을 넣어서 생각해보면 오히려 쉬웠는데 결국에는 이 알고리즘이 과반수 이상의 요소가 있다는 전제가 있었기 때문에 가능하므로 이 부분을 고려할 필요가 있습니다.

---

80. Remove Duplicates from Sorted Array 2

1. 문제

문제 URL

• 주어진 배열에서 순서대로 동일한 요소가 3개 이상 연속되지 않도록 만들어야 하는 문제입니다.
• 1,1,2,2,2,3일 때, 1,1,2,2,3,_으로 만들고 그 요소의 수를 return합니다.

2. 나의 풀이

먼저 어떻게 풀지에 대해 고민했는데 26번 문제를 풀 때 익힌 포인터 방식으로 풀고 싶었는데 두 번째 if문에서 방법이 생각나지 않았습니다..

class Solution {
  public int removeDuplicates(int[] nums) {
    int a=1, cnt=0;
    for(int i=1; i<nums.length; i++){
      if(nums[i]==nums[i-1]) cnt++;
      if(cnt>=2 || nums[i]!=nums[i-1]){
        //cnt=0;
        nums[a++]=nums[i];
      }

    }
    return a;
  }
}

3. 다른 사람의 풀이를 보고 개선하기

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

• 먼저 nums가 2보다 작다면 당연히 별도의 계산이 필요하지 않으므로 그 길이를 return 합니다.
• 그리고 시작되는 i와 index도 2의 값부터 진행될 수 있도록 합니다.
• 시간복잡도: O(n)
• 공간복잡도: O(1)

4. 생각해 볼 부분

if (nums[i] != nums[index - 2]) {
    nums[index] = nums[i];
    index++;
}

이 부분에 대한 내용이 헷갈렸는데 실제로 index로 들어간 배열들은 차곡차곡 중복을 2개까지 허용한 값들이고 nums[i]의 값이 기존에 값들과 다른 경우(새로 쌓은 배열과 다른 경우), nums[index] = nums[i];로 다른 요소를 넣어줍니다.

---

26. Remove Duplicates from Sorted Array

1. 문제

문제 URL

• 정렬된 배열 nums의 중복값을 제외한 요소의 수를 return하는 문제입니다.
• 배열의 중복값은 없어야 합니다.

2. 나의 풀이

class Solution {
    public int removeElement(int[] nums, int val) {
        nums = Arrays.stream(nums).distinct().toArray();
        return nums.length;
    }
}

IDE에서와 달리 nums 값의 output이 중복값이 제거되지 않은 상태로 나와서 다시 고민하게 되었습니다.

• 시간복잡도: O(n)
• 공간복잡도: O(n)

3. 다른 사람의 풀이를 보고 개선하기

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

nums의 값이 앞의 값과 같지 않으면, 인덱스 a 위치에 대입하게 됩니다.

4. 생각해 볼 부분

stream에서 사용되는 distinct()와 toArray()는 객체를 새로 생성, 메모리를 추가로 필요로 한다는 점에서 공간복잡도 결과가 좋지 않게 나왔습니다.
새로운 객체 생성보다는 주어진 nums 객체 값에 변화를 주는 방식으로 해결하는 것을 생각해봐야 합니다.

---

27. Remove Element

1. 문제

문제 URL

• nums 배열과 배열에서 삭제해야 하는 요소가 주어집니다.
• return 값은 배열로 삭제한 요소를 제외한 요소의 수입니다.

2. 나의 풀이

class Solution {
    public int removeElement(int[] nums, int val) {
        int answer = 0;
        for(int i=0; i<nums.length; i++){
            if(nums[i]!=val){ 
                nums[answer] = nums[i];
                answer++;
            }    
        }
        return answer;
    }
}

처음에 return 값만 고려해서 for문으로 만들었는데 nums[answer] = nums[i];와 같은 방식으로 nums 배열도 다시 고려해야 해서 추가해주었습니다. 이렇게 하면 val과 같지 않은 값들만 nums 배열 앞에 놓을 수 있습니다.

• 시간복잡도: O(n)
• 공간복잡도: O(1)

3. 다른 사람의 풀이를 보고 개선하기

class Solution {
    public int removeElement(int[] nums, int val) {
        int count=0; //variable for occurance
        int i=0; 
        int j=nums.length-1;
        while(i<nums.length){
            if(nums[i]==val){
               nums[i]=nums[j];
               nums[j]=-1;
               j--;
               count++;
            }
            else{
                i++;
            }
        }
        return nums.length-count;
    }
}

이 문제도 포인터로 접근한 분도 있었는데 시간복잡도와 공간복잡도가 이 경우는 저의 풀이와 같았습니다. val 값과 같은 경우는 다시 nums 뒤에 요소 값을 넣어주는 부분이 새로웠습니다.

4. 생각해 볼 부분

포인터를 이용한 풀이가 정렬 문제에서 시간복잡도를 줄일 수 있는 방법이므로 좀 더 익숙해지도록 해야겠습니다.

---

88. Merge Sorted Array

1. 문제

문제 URL

• nums1과 nums2가 주어지고 nums1 안에 병합한 뒤 정렬하는 문제입니다.
• 별도의 return 값은 없습니다.

2. 나의 풀이

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=0; i<n; i++){
            nums1[m+i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

nums1의 크기가 원래 문제에서 n+m의 크기로 주어지기 때문에 m개 외의 값은 0으로 되어 있다고 생각을 하고 그 이후의 값만 nums2에서 받아와서 for문으로 넣어주는 방식입니다. 병합 후 마지막 정렬은 Arrays.sort 메서드로 정렬했습니다.

• 시간복잡도: O(n + m * log(m+n))
• 공간복잡도: O(1)

3. 다른 사람의 풀이를 보고 개선하기

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

다른 풀이 중에 가장 깔끔하고 신선했던 접근이었습니다. 두 포인터를 두고 푸는 풀이고 시간복잡도가 O(n+m)으로 개선됩니다.

• 변수 i, j, k를 각각 nums1, nums2, 병합한 nums2의 인덱스로 초기화합니다.
• 주어진 배열이 이미 정렬되어 있다는 특징을 활용하여, 큰 값들을 뒤에서부터 순차적으로 nums1 배열에 채워 넣습니다.
• 병합시 더 큰 값을 nums1 배열의 끝부터 시작하는 인덱스 k에 저장합니다. 만약 nums1 배열의 요소가 nums2 배열의 요소보다 크다면 해당 요소를 먼저 nums1[k] 위치에 저장하고, 그렇지 않은 경우에는 nums2[j] 값을 nums1[k] 위치에 저장합니다.
• 각각의 배열 요소를 처리할 때마다, i, j, 그리고 k를 감소시킵니다.
• nums2 배열의 요소를 모두 nums1 배열에 합칠 때까지 위의 과정을 반복합니다.

4. 생각해 볼 부분

포인터를 이용한 접근법에 대해 생각해보지 못했는데 시간복잡도를 고려해 새로운 접근법을 익히게 된 계기가 되었습니다. Arrays.sort를 이용한 풀이가 시간복잡도가 높아진다는 것을 확인할 수 있었습니다.
그리고 return 값이 별도 존재하지 않고 nums1에 값에 병합처리한다는 전제가 다른 코드테스트 사이트와 차이가 있어 문제를 더 잘 읽어야겠다는 생각이 들었습니다.