leeso

문제

https://www.acmicpc.net/problem/11047

공부한 부분

그리디 알고리즘 : 각 단계별로 최선의 선택지를 선택하는 것.

그리디 알고리즘은 항상 최적의 해를 도출해내는 것은 아니다.

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj11047 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] coin = new int[N];
        for (int i = 0; i < N; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }
        int count = 0;
        for (int i = N -1; i>= 0; i--) {
            if(coin[i] <= K) {
                count += (K / coin[i]);
                K = K % coin[i];
            }
        }
        System.out.println(count);
    }
}

문제

https://www.acmicpc.net/problem/1699

공부한 부분

dp 관련 문제는 일단 dp[10] 정도까지는 써보면서 규칙을 확인해보면 좋을 것 같다.

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class boj12865 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];

        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = 100001;
            for (int j = 1; j <= i / 2; j++) {
                if (j * j == i) {
                    dp[i] = 1;
                    break;
                }
                dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
            }
        }
        System.out.println(dp[n]);
    }

}

문제

https://www.acmicpc.net/problem/2231

공부한 부분

숫자가 주어지고 각각 자리수의 합을 구하려고 할 때, %10이랑 /10 활용하면 좋다.

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class boj2231 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = 0;

        for (int i = 1; i <= N; i++) {
            int tmp = i;
            int sum = i;

            while (tmp > 0) {
                sum = sum + tmp % 10;
                tmp = tmp / 10;
            }
            if(sum == N) {
                M = i;
                break;
            }
        }
        System.out.println(M);
    }
}

문제

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://www.acmicpc.net/problem/1189

풀이

dfs탐색으로 모든 경우의 수를 탐색해준다

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj1189 {

    static int R, C, K;
    static char[][] map;
    static int[][] visited;
    static int answer;

    static int[] moveR = {1, -1, 0, 0};
    static int[] moveC = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        visited = new int[R][C];

        for (int i = 0; i < R; i++) {
            String s = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = s.charAt(j);
            }
        }

        visited[R - 1][0] = 1;
        dfs(R - 1, 0, 1);

        System.out.println(answer);

    }

    static void dfs(int r, int c, int moved) {
        if (r == 0 && c == C - 1) {
            if (moved == K) {
                answer++;
            }
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nextR = r + moveR[i];
            int nextC = c + moveC[i];
            if (nextR < 0 || nextR >= R || nextC < 0 || nextC >= C) {
                continue;
            }
            if (visited[nextR][nextC] == 1 || map[nextR][nextC] == 'T') {
                continue;
            }
            visited[nextR][nextC] = 1;
            dfs(nextR, nextC, moved + 1);
            visited[nextR][nextC] = 0;

        }

    }

}

문제

https://www.acmicpc.net/problem/2164

풀이

큐를 사용하면 되겠다!

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            queue.add(i);
        }

        while (queue.size() > 1) {
            queue.remove();
            if(queue.isEmpty()) break;
            int top = queue.poll();
            queue.add(top);
        }
        System.out.println(queue.peek());
    }

}

문제

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;
    }
}