[리트코드] 16일차

150. Evaluate Reverse Polish Notation

 

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> st = new Stack<>();
        for (int i = 0; i < tokens.length; i++){
            String token = tokens[i];
            if ("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token)) {
                st.push(caculate(st.pop(), st.pop(), token));
            }else{
                st.push(Integer.parseInt(token));
            }
        }
        return st.pop();
    }

    private int caculate (int num1, int num2, String op){
        switch(op) {
            case "+": return num2 + num1;
            case "-": return num2 - num1;
            case "*": return num2 * num1;
            case "/": return num2 / num1;
            default: throw new IllegalArgumentException("Invalid operator: " + op);
        }
    }
}

예전에 풀어본 문제라 간단하게 해결했다.

 

224. Basic Calculator

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        int result = 0;
        int number = 0;
        int sign = 1;
        for (int i = 0; i<s.length(); i++){
            char c = s.charAt(i);
            if (Character.isDigit(c)){
                number = 10 * number + (int)(c-'0');
            }else if(c=='+'){
                result += sign * number;
                number = 0;
                sign = 1;
            }else if (c=='-'){
                result += sign * number;
                number = 0;
                sign = -1;
            }else if (c == '('){
                stack.push(result);
                stack.push(sign);
                sign = 1;
                result = 0;
            }else if (c==')'){
                result += sign * number;
                number = 0;
                result *= stack.pop();
                result += stack.pop();
            }
        }
        if (number != 0) result += sign * number;
        return result;
    }
}

해결하려다가.. 풀이가 안 보여서 그만 이걸 보고 말았다. 정말 깔끔한 코드다. 

다음엔 꼭 풀어야지. 

 

141. Linked List Cycle

새로운 단원이다. linkedList.

쉬운문제인줄 알았는데 어려웠다. 숫자가 unique한 숫자가 아니라서 어떻게 해야할지 감이 안온다.

챗지피티에게 물어보니까 한 알고리즘을 소개해줬다. 그래서 그거 가지고 풀었다.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        

        while (fast != null){
            fast = fast.next;
            if (fast == null ||fast.next == null){
                return false;
            }
            fast = fast.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }
}

Floyd’s Cycle Detection Algorithm이라는 알고리즘이었는데, 구현방법도 어렵지 않았다. 덕분에 해결할 수 있었다.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }
}

깔끔한 버전

 

2. Add Two Numbers

처음에 모두 더한다음에 하나씩 넣으려고 했는데, 이러니 정답이 역순으로 나오지 않아 해결이 되지 않았다.

그래서 힌트를 보니 계산기 만들듯이 만드는 게 더 낫다는 결론에 도달했다.

해결해보자.

    /**
    * 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; }
    * }
    */
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(0);
            ListNode current = dummy;
            int carry = 0;
            while (l1 != null || l2 != null || carry != 0){
                int sum = carry;
                if (l1 != null) {
                    sum += l1.val;
                    l1 = l1.next;
                }
                if (l2 != null){
                    sum += l2.val;
                    l2 = l2.next;
                }
                carry = sum / 10;
                current.next = new ListNode(sum % 10);
                current = current.next;
            }

            return dummy.next;
        }
    }

 

완료!