Valid Parentheses 문제
https://leetcode.com/problems/valid-parentheses/
Valid Parentheses - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: trueExample 2:
Input: s = "()[]{}"
Output: trueExample 3:
Input: s = "(]"
Output: false풀이
백준이나 프로그래머스에서 흔히 볼 수 있는 올바른 괄호 찾기 문제와 유사합니다. Map.of를 이용해서 Map을 만들어 주었습니다. Map.of는 둘 이상의 (k, v) 쌍을 호출하게 되면 ImmutableCollections 안에 있는 MapN<K, V> 객체를 만들어 내게 됩니다. Map.of(key1, value1, key2, value2...) 이런 식으로 만든다. String으로 받은 s를 toCharArray()를 이용해서 Character로 변환해주면서 for문을 반복합니다. 만약 chr이 (, {, [ 인 여는 괄호이면 stack.push 해줍니다. 만약 stack이 비어있거나 stack.pop 했을 때 map.get(chr)인 value값과 같지 않으면 false를 return 합니다. for문이 끝나고 stack이 비어있는지 확인해 그 값을 return 한다.
java 9 부터 도입된 Map.of 메소드를 알아봅시다.
java 9 버전 부터 Map.of 메소드가 생겼습니다. 이것을 언제 쓸 법 한지 알아보고, 간단하게 내부를 보도록 하겠습니다. 보시면, unmodifiable map을 리턴하게끔 되어 있습니다. 수정할 수 없는 맵을
codingdog.tistory.com
코드
class Solution {
public boolean isValid(String s) {
boolean answer = true;
Map<Character, Character> map = Map.of(')', '(', '}', '{', ']', '[');
Stack<Character> stack = new Stack<>();
for(Character chr : s.toCharArray()) {
if(chr == '(' || chr == '{' || chr == '[') {
stack.push(chr);
}
else if(stack.isEmpty() || stack.pop() != map.get(chr)){
return answer = false;
}
}
answer = stack.isEmpty();
return answer;
}
}Merge Two Sorted Lists 문제
https://leetcode.com/problems/merge-two-sorted-lists/
Merge Two Sorted Lists - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]Example 2:
Input: list1 = [], list2 = []
Output: []Example 3:
Input: list1 = [], list2 = [0]
Output: [0]Constraints:
- The number of nodes in both lists is in the range [0, 50].
- -100 <= Node.val <= 100
- Both list1 and list2 are sorted in non-decreasing order.
풀이
LeetCode에서 알고리즘 문제를 풀다 보면 ListNode를 이용해 풀어야 하는 문제가 있습니다. ListNode로 list1, list2를 받아서 p1, p2에 각각 넣어줍니다. while을 이용해서 p1과 p2가 null이 아닐 때까지 반복하는데 만약 p1의 값이 p2의 값과 비교했을 때 p2의 값이 크면 p.next에 p1을 대입한다. p1의 값을 p1.next의 값으로 바꾸어주고 p에 p.next 값을 대입한다. 만약 p1의 값이 더 클 경우 p.next에 p2의 값을 대입한다. p2.next 값을 p2에 대입하고 p에 p.next값을 대입한다. while 문이 끝나고도 남은 ListNode가 발생할 수 있어 p1이 null이 아니면 p.next에 p1을 대입하고 p2가 null이 아니면 p.next에 p2를 대입한다.
- ListNode 참고 자료 : https://jaime-note.tistory.com/66
[LeetCode] 자주 사용되는 자료구조 - ListNode 구현
모든 소스 코드는 여기 있습니다. LeetCode 에서 알고리즘 문제를 풀다보면 ListNode 를 이용해 테스트 해야할 일이 많이 있습니다. 테스트 코드나 main 메서드 내에서 객체를 생성하고 ListNode 를 파라
jaime-note.tistory.com
코드
/**
* 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 mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head = new ListNode();
ListNode p = head;
ListNode p1 = list1;
ListNode p2 = list2;
while(p1 != null && p2 != null) {
if(p1.val < p2.val) {
p.next = p1;
p1 = p1.next;
}
else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if(p1 != null) {
p.next = p1;
}
if(p2 != null) {
p.next = p2;
}
return head.next;
}
}'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
| 프로그래머스 최솟값 만들기, JadenCase 문자열 만들기 (0) | 2022.09.23 |
|---|---|
| 백준) DP, DFS (0) | 2022.08.27 |
| 백준) HashMap (0) | 2022.07.23 |
| 백준) BFS, 다익스트라 (0) | 2022.07.19 |
| 백준) 우선순위 큐, DP (0) | 2022.07.18 |
