개발자 Lim

<아이디어>

무방향 그래프에서 모든 노드에 도달할 수 있는 정점은 결과적으로 제일 마지막으로 다른 노드를 가르키는 노드임으로

모든 노드가 가르키는 노드들을 체크해서 아무런 노드에게 지목되지 않는 노드들을 찾아 해당 노드를 반환하면 된다.

<풀이 코드>

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        List<Integer> ans = new ArrayList<>();
        // 다른 노드에게 가르킴 당하는 노드인지 아닌지 여부를 확인하는 배열
        Boolean[] isDirectnode = new Boolean[n];
        Arrays.fill(isDirectnode,false);
        for (List<Integer> node:edges)
            isDirectnode[node.get(1)]=true;
        for (int i = 0; i < n; i++) {
            if(!isDirectnode[i])
                ans.add(i);
        }
        return ans;
    }
}

<아이디어>

구현 문제를 푸는 방법처럼 노드의 맨끝과 맨처음에서 점차 한 칸씩 앞으로 이동 하면서 합계를 구하고 최대값을 반환

맨끝에 존재하는 노드에서 한 칸씩 앞으로 가는 방법은 재귀를 이용하여 구현

<풀이 코드>

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    private int ans=Integer.MIN_VALUE;
    private ListNode start;
    // 제일 뒤에 노드와 제일 앞의 노드의 합계를 구하고 ans에 최대값을 저장
    public void addEachStartNodeEndNode(ListNode end){
        // 제일 맨 끝 노드로 이동
        if(end==null)
            return;
        addEachStartNodeEndNode(end.next);

        ans = Math.max(ans,(end.val+start.val));
        start = start.next;
    }
    public int pairSum(ListNode head) {
        start = head;
        ListNode end = head;
        addEachStartNodeEndNode(end);
        return ans;
    }
}
public class MaximumTwinSumofaLinkedList {
}

<아이디어>

노드 2개씩 바꾸는 작업을 하기 때문에 3가지 노드의 위치를 구하고 

Node pre(이전 노드)

Node cur(현재 노드)

Node next(다음 순서로 작업해야 할 노드)

<연결 교환 작업>

cur -> cur.next.next

cur.next -> cur 

pre -> cur.next

<정답코드>

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode tmp = head;
        ListNode prev = new ListNode();
        // 연결고리의 제일 앞의 노드가 오도록 최신화
        head = tmp.next;
        while(tmp.next!=null){
            ListNode switchOp1 = tmp;
            ListNode switchOp2 = tmp.next;
            // 다음 타순으로 변경할 노드
            ListNode next = tmp.next.next;
            // 교환 작업
            switchOp1.next = next;
            switchOp2.next = tmp;
            // 이전 노드의 연결 최신화
            prev.next = switchOp2;
            prev = switchOp1;
            // 다음 타순으로 변경할 노드가 없다면 중지
            if(next==null) break;
            tmp = next;
        }

        return head;
    }
}

<문제 풀이 과정>

단순 반복문을 사용한 구현 풀이 -> Time Out

class Solution {
    public int bulbSwitchFail(int n) {
        if(n==0) return 0;
        int ans = 0;
        boolean[] array = new boolean[n+1];
        Arrays.fill(array,false);
        for (int i = 1; i < n; i++) {
            for (int j = i; j <= n; j+=i) {
                array[j] = !array[j];
            }
        }
        array[n] = !array[n];

        for (boolean unit: array)
            if(unit) ans++;

        return ans;
    }
}

단순 반복문으로는 해당 문제를 해결할 수 없기 때문에 수학적으로 접근해야 했다.

해당 반복을 자세히 보면 각 n번째 전구는 n의 약수 일 때만 상태가 바뀜을 알 수 가 있다.

즉 6번 전구의 경우에는: Round가 1, 2, 3, 6일 때 마다 바뀌게 된다.

전구(n)가 불이 켜진 상태가 되려면 짝수번 바뀌어야 하고 (n의 약수의 갯수가 짝수)

불이 꺼진 상태가 되려면 홀수번 바뀌어야 함을 알 수 있다. (n의 약수의 갯수가 홀수)

즉 1~n까지의 경우에서 답은 

해당 숫자(n)에서 약수의 갯수가 홀수인 수의 갯수 임을 추론 할 수 있다.

약수의 갯수가 홀수가 나오기 위해서는 완전 제곱수가 되어야 한다.
ex: 4 -> 1,2,4  9 -> 1,3,9  16 -> 1,4,16

즉 해당 문제는 1~n까지의 수중에서 완전 제곱수의 갯수를 구하는 문제임을 
알 수 있다. 

<풀이 코드>

class Solution {
    public int bulbSwitch(int n){
        int ans = 0;
        for (int i = 1; i*i <= n; i++) {
            ans++;
        }
        return ans;
    }
}

이런 식으로 반복문으로 답을 구할 수도 있지만

좀 더 간결하게 바꾼다면
수학적 정의의 의하면 n의 제곱근은 1~n까지의 자연수 중에서 완전 제곱수의 갯수와
동일함을 이용한다면

<최종 정답 코드>

class Solution {
    public int bulbSwitchOtimal(int n){
        return (int)Math.sqrt(n);
    }
}

다음과 같이 아주 간결하게 줄일 수가 있다.

<아이디어>

실제 Stack을 바탕으로 시뮬레이션을 통해 가능한지 아닌지 확인 한다.

 poped의 첫 번째 값은 pushed에서 모든 값이 올 수 있지만

단 그 이후 poped의 값들은 pushed 배열에서 poped 배열에 첫 번 째로 온 값의

바로 전 값이거나 그 뒤에 있는 요소들이어야 한다.

<정답 코드>

import java.util.HashSet;
import java.util.Stack;

class Solution {
    // 시간 복잡도 O(n*n) 공간 복잡도 O(n)
    public boolean validateStackSequences(int[] pushed, int[] popped) {
//        pops의 첫번째 요소는 모든 요소가 오는 것 이 가능
//        pops의 두번째 요소는 처음 요소의 바로 앞 혹은 그 뒤에 오는 요소들 이어야 함
//        pops의 세번째 요소는 두번째 요소의 바로 앞 혹은 그 뒤에 오는 요소들 이어야 함
        // 실제 시뮬레이션 용 Stack
        Stack<Integer> pStack = new Stack<>();
        // 그 뒤에 오는 요소들 중 대상 요소를 빠르게 검사하기위한 Set
        HashSet<Integer> beforeUnits = new HashSet<>();
        // 첫 번째 요소를 찾았는지 확인할 변수
        boolean isFound = false;
        // 첫 변수의 pushed에서의 인덱스
        int firstIndex = 0;
        // stack과 set에 첫 번째 요소를 찾을 때 까지 채우기
        for (int i = 0; i < pushed.length; i++) {
            if(!isFound)
                pStack.add(pushed[i]);
            else
                beforeUnits.add(pushed[i]);
            if(pushed[i]==popped[0]) {
                firstIndex = i;
                pStack.pop();
                isFound = true;
            }
        }

        // 시뮬레이션 시작
        for (int i = 1; i < popped.length; i++) {
            // 바로 전 요소라면 pop
            int beforeValue = -1;
            if(!pStack.isEmpty())
                beforeValue = pStack.peek();

            if(beforeValue==popped[i]){
                pStack.pop();
                continue;
            }

            // 후속으로 존재하는 요소들 중에 pop 되어야 될 요소가 있다면
            else if(beforeUnits.contains(popped[i])){

                for (int j = firstIndex+1; j < pushed.length ; j++) {
                    // pushed의 이전 요소의 인덱스에서 다음으로 올 요소까지 push
                    pStack.add(pushed[j]);
                    // 만약 다음으로 pop되어야 할 요소를 찾았다면 pop 하고 이전요소(firstIndex)초기화
                    if(pushed[j]==popped[i]){
                        pStack.pop();
                        firstIndex=j;
                        break;
                    }
                }
            }
            else
                return false;
        }
        // 시뮬레이션이 마치고 스택이 비어 있으면 true 아니라면 false
        return pStack.isEmpty();
    }
}

<최적화>

class SolutionOtimal {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int N = pushed.length;
        Stack<Integer> stack = new Stack();

        int j = 0;
        for (int x: pushed) {
            stack.push(x);
            while (!stack.isEmpty() && j < N && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }

        return j == N;
    }
}

<메모> 

뭐든 단순하게 생각하고 하는게 좋을 것 같다.

<아이디어>

문자열 path를 "/"를 기준으로 나누어야 하므로 String.split(), StringTokenizer, String.toChararray() 중 한 가지를 사용해아 한다. 그리고 /..이 있을 경우 전에 있던 경로에서 한칸 앞으로 가야 하는 문제가 있는데 Stack을 활용한다면 쉽게 해결 할 수 있다. 즉 Stack과 Tokenizer를 활용하여 문제에 답에 필요한 문자열 그룹을 확보하고 

마지막으로 StringBuilder를 통해서 문자열 사이사이 "/"를 넣어 반환 한다. 

<해답 코드>

import java.util.Stack;
import java.util.StringTokenizer;

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        // Tokenizer는 split("/+")와 같이 구분되는 문자가 여러개 와도 감안 하여 분할 해준다.
        StringTokenizer st = new StringTokenizer(path,"/");
        StringBuilder ans = new StringBuilder();
        while(st.hasMoreTokens()){
            String tmp = st.nextToken();
            if(tmp.equals("."))
                continue;
            else if(tmp.equals("..")) {
                if (!stack.isEmpty())
                    stack.pop();
            }
            else
                stack.add(tmp);
        }
        
        for (String s : stack) {
            ans.append("/");
            ans.append(s);
        }

        return ans.toString().equals("") ?"/":ans.toString();
    }
}

<아이디어>

'*' 가 나올 경우 바로 앞에 있는 요소를 제거해야 한다는 점에서 선입선출 FIFO 개념인 Stack을 생각을 할 수 있었고

Stack의 담은 문자들을 하나로 합치는데 시간을 단축 시키기 위해 StrringBuilder를 생각 할 수 있었다.

<코드>

import java.util.Stack;

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public String removeStars(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuilder ans = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char unit = s.charAt(i);
            if(unit!='*')
                stack.push(unit);
            else
                stack.pop();
        }

        for (Character character : stack)
            ans.append(character);

        return ans.toString();
    }
}

+ 해당 문제를 Stack을 사용하지 않고 구현으로 풀 경우

이점: Stack을 사용한 것과 시간 복잡도 자체는 같지만 Stack의 push pop의 사전 과정이 필요가 없기 때문에 더 빠른 속도를 가지고 있다.

class Solution2 {
	// 시간 복잡도 O(n) 공간 복잡도 O(n)
    public String removeStars(String s) {
        int len = s.length();
        char[] chars = new char[len];
        int index = len, count = 0;
		// 문자열 s의 뒤에서 부터 시작
        for (int i = len - 1; i >= 0; i--) {
            char c = s.charAt(i);
            // *이 오면 제거해야할 문자 수 count++
            if (c == '*') {
                count++;
            } 
            // *이 아니고 제거해야 할 문자가 아니라면 char 배열에 추가
            else {
                if (count > 0) {
                    count--;
                } else {
                    chars[--index] = c;
                }
            }
        }
        // char 배열의 마지막으로 추가한 문자의 인덱스 부터 ~ 유효한 마지막 인덱스 까지의 범위 를 바탕으로 문자열을 만들어 반환 
        return String.valueOf(chars, index, len - index);
    }
}

제약:

• n == spells.length
• m == potions.length
• 1 <= n, m <= 105
• 1 <= spells[i], potions[i] <= 105
• 1 <= success <= 1010

<아이디어>

long 타입의 success를 비교하는 방법은 (long)spell*potion >= success 타입 캐스팅을 통해 해결이 가능하다.

문제점은 단순 이중 for문을 통해 해결 하려할 경우 제한 시간 초과가 나오기 때문에

선형 탐색보다 더 빠른 이분 탐색을 사용 할 필요가 있었다. 

여기서 우리가 배열에서 찾아야 할 건 주어진 비교식에 처음으로 성립하는 값이다.

<정답 코드>

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    // 시간 복잡도 O(nlog m) 공간 복잡도 O(1)
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        List<Integer> ans = new ArrayList<>();
        int m = potions.length;
        Arrays.sort(potions);
        for (int spell : spells) {
            int left = 0;
            int right = m-1;
            // 이분 탐색 변형
            while(left<=right){
                // System.out.println(left+", "+right);
                int mid = left+(right-left)/2;
                long tmp = (long)spell*potions[mid];
                // 종료 조건을 넣지 않는 이유는 배열에서 주어진 비교식에 처음으로 성립하는 값을 찾기 위해서다.
                // 찾는 값이 mid의 해당하는 값보다 작거나 같다면 탐색 범위의 오른쪽의 범위를 좁힌다.
                if(tmp>=success)
                    right = mid-1;
                // 찾는 값이 mid의 해당하는 값보다 크다면 탐색 범위의 오른쪽의 범위를 좁힌다.
                else
                    left = mid+1;
            }
            ans.add(m-left);
        }
        // 리스트 보다는 일반 배열을 사용하는걸 권장한다.
        return ans.stream().mapToInt(i->i).toArray();
    }
}