leeso

문제

https://leetcode.com/problems/bulls-and-cows/

풀이

bulls : guess의 숫자가 secret의  올바른 위치에 있는 경우

cows : secret에 있는 숫자이지만 guess에서 잘못된 위치에 있는 경우

numsSecret==numsGuess 인 경우 bulls를 ++

정확하게 일치하는 경우 외에,

secret에 있는 숫자인 경우 -- 해주고, guess에 있는 숫자인 경우 ++ 해준다.

그 이후 배열의 숫자를 확인해서

numsGuess에 있는게 -인 경우 cows++해주고, numsSecret에 있는게 +인 경우 cows++ 해준다.

Java Code

class Solution {
    public String getHint(String secret, String guess) {
        int bulls=0;
        int cows=0;
        int[] nums=new int[10];
        for(int i=0;i<secret.length();i++){
            int numsSecret=secret.charAt(i)-'0';
            int numsGuess=guess.charAt(i)-'0';
            if(numsSecret==numsGuess){
                bulls++;
            }else{
                if(nums[numsGuess]<0){
                    cows++;
                }
                if(nums[numsSecret]>0){
                    cows++;
                }
                nums[numsGuess]++;
                nums[numsSecret]--;
            }
            
        }
        return bulls + "A" + cows + "B";
    }
}

문제

https://leetcode.com/problems/backspace-string-compare/

풀이

s문자를 배열로 바꿔서 stack 활용해서 문자 만들어주고,

t문자를 배열로 바꿔서 같은 방법으로 해줘서 결과 비교해서 return 해준다.

Java Code

import java.util.Stack;

class Solution {
    public boolean backspaceCompare(String s, String t) {
        char[] arr = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != '#') {
                stack.push(arr[i]);
            } else if(!stack.isEmpty()){
                stack.pop();
            }
        }
        String str1 = stack.toString();
        stack.clear();
        char[] arr1 = t.toCharArray();
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != '#') {
                stack.push(arr1[i]);
            } else if(!stack.isEmpty()){
                stack.pop();
            }
        }
        String str2 = stack.toString();
        if (str1.equals(str2)) {
            return true;
        } else {
            return false;
        }
    }
}

문제

https://leetcode.com/problems/find-all-anagrams-in-a-string/

s문자열이 주어졌을 때, p문자열이 모두 들어있는 모든 첫번째 인덱스를 return해준다.

풀이

1. p의 길이가 s의 길이보다 긴 경우, return 해준다.

2. 먼저 알파벳의 크기만큼 s와 p 배열을 만들어준다.

3. 문자의 길이가 정해져있으니까 왼쪽, 오른쪽 ++ 해주어 숫자를 비교해준다..

Java Code

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length()) return new ArrayList<>();

        int[] sHash = new int[26];
        int[] pHash = new int[26];

        for (int i = 0; i < p.length(); i++) {
            pHash[p.charAt(i) - 'a']++;
            sHash[s.charAt(i) - 'a']++;
        }

        int left = 0, right = p.length();
        List<Integer> ans = new ArrayList<>();

        while (right < s.length()) {
            if (Arrays.equals(sHash, pHash)) ans.add(left);

            char acquire = s.charAt(right);
            sHash[acquire - 'a']++;

            char discard = s.charAt(left);
            sHash[discard - 'a']--;

            left++; right++;
        }
        
		//	두 배열이 같은 경우 left값을 정해준다.
        if (Arrays.equals(sHash, pHash)) ans.add(left);

        return ans;
    }
}

문제

https://leetcode.com/problems/validate-binary-search-tree/

트리가 주어지는데, 이 트리가 이진트리인지 판단한다.

풀이

1. 특정 노드를 기준으로, 왼쪽 자식 노드는 (B)는 부모노드(A)보다 값이 작아야하고, 오른쪽자식노드(C) 보다 커야한다.

B의 왼쪽 자식노드(D)는 B보다 작아야하며, 오른쪽 자식노드(E)는 B보다 커야되고, A보다는 작아야한다.

1. root 부터 isValidBST 함수를 실행한다.

* 이때 노드의 범위가 정수 범위이므로, Long 값의 최대, 최소값을 세팅해준다.

2. isValidBST() 함수에서 node가 null이면, true이다.

3. node의 값이 min 보다 작거나 같다면 false를 반환한다.

4. node의 값이 max 보다 크거나 같다면 false를 반환한다.

5. 왼쪽 자식노드가 유효한지 확인한다.

5-1.

isValidBST() 함수를 재귀 호출한다. 인자로 왼쪽 자식노드 node.left, 최소값으로 min 그리고 최대값으로 현재 노드의 값 node.val을 전달한다. (왼쪽 자식노드는 부모 노드보다 작아야 하기 때문에 최대 한계값으로 현재 노드의 값을 전달한다.)
5-2. 왼쪽 자식노드가 유효하지 않다면 false를 반환한다.

6. 오른쪽 자식노드가 유효한지 확인한다.
6-1. isValidBST() 함수를 재귀 호출한다. 인자로 오른쪽 자식노드 node.right, 최소값으로 현재 노드의 값 node.val 그리고 최대 한계값 max를 전달한다. (오른쪽 자식노드는 부모 노드보다 커야 하기 때문에 최소 한계값으로 현재 노드의 값을 전달한다.)
6-2. 오른쪽 자식노드가 유효하지 않다면 false를 반환한다.

7. 최종적으로 모든 노드가 유효하다면 true를 반환한다.

Java Code

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    boolean isBST(TreeNode root,long min,long max)
    {
        if(root == null)
            return true;
        
        if(root.val <= min || root.val >= max)
            return false;
        
        boolean left = isBST(root.left,min,root.val);
        boolean right = isBST(root.right,root.val,max);
        return left && right;
    }
}

문제

https://leetcode.com/problems/linked-list-cycle-ii/

linked list에 head가 주어진다. 이때 사이클이 시작하는 노드를 return 한다. 없는 경우 null을 return 한다.

풀이

1. 사이클인지 판별한다.

2. 사이클인 경우 사이클의 진입부분을 찾는다.

"토끼와 거북이 알고리즘" 을 사용한다.

1. 거북이를 시작지점으로 옮긴다.

2. 토끼와 거북이가 만날 때까지 한칸씩 이동한다.

3. 둘이 만나는 지점이 사이클의 시작지점이다.

D : 시작점(head)에서 사이클 시작점까지의 거리
M : 사이클 시작점에서 둘이 만난 지점까지의 거리
R : 둘이 만난 지점부터 다시 사이클 시작점까지의 거리

거북이 = D + M
토끼 = 2(D + M) = 2D+2M

토끼는 거북이의 2배씩 움직이므로, 위의 수식은 쉽게 구할 수 있다.

이때 토끼가 이동한 경로는 시작점 -> 사이클 시작점 -> 둘이 만난 곳 -> 사이클 시작점 -> 둘이 만난 곳이 된다.

이제 토끼가 이동한 경로를 D,M,R을 사용하여 표시를 해보면 다음과 같다.

토끼 = D + M + R + M = D + R + 2M

이제 토끼가 이동한 거리를 표현한 수식이 2개가 되었다. 이 두 개를 가지고 R과 D의 관계를 계산할 수 있다.

2D + 2M = D+R+2M 
-> D = R

D = R, 즉, "시작점부터 사이클 시작점 까지의 거리"는 "둘이 만난 곳 부터 다시 사이클 시작점까지 가는 거리"와 같다.

이 알고리즘이 옳다는 것을 증명했으므로, 이를 사용해 구현하게 되면 어렵지 않게 문제를 해결할 수 있다.

Java Code

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null || head.next==null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
               while(head!=slow){
                   head=head.next;
                   slow=slow.next;
               }
               return slow;
            }
        }
        return null;
    }
}

문제

https://leetcode.com/problems/first-bad-version/

n개의 버전[1, 2, ..., n]이 있고 첫 번째 불량 버전을 찾은 그 이후 다음 버전은 모두 불량이다.

버전이 잘못된지 여부를 반환하는 API bool isBadVersion(version) 이 제공된다.

API에 대한 호출 수를 최소화하여 첫 번째 불량 버전을 찾는 기능을 구현해야 된다.

풀이

1. 전체 버전에서 첫 번째와 마지막 버전을 지정한다.
2. 가장 중앙 버전의 불량여부를 확인한다.
3. 중앙 버전이 불량인 경우,
   1. 해당 제품의 이전 제품이 정상인 경우, 중앙값 리턴,
   2. 이전 제품도 불량이라면, 중앙제품 이전 제품을 마지막 버전으로 설정한다.
4. 중앙 버전이 정상인 경우 중앙 다음 제품을 최초 제품으로 설정한다.

Java Code

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if(n==1) return 1;        
        
        int begin = 1;
        int end = n;
        int mid = (end - begin) / 2 + begin;
        
        while(true){
            if(isBadVersion(mid)){
                
                if(!isBadVersion(mid-1)){
                    return mid;
                } else {
                    end = mid-1;
                    mid = (end-begin) / 2 + begin;
                }
                
            } else {
                
                begin = mid+1;
                mid = (end-begin) / 2 + begin;
                
            }
        }
    }
}