👨🏻‍💻 PS/LeetCode 150

[Java] 242. Valid Anagram

문제 파악 두 문자열 s와 t가 주어진다. 두 문자열을 이루는 문자의 종류와 개수가 동일할 때, Anagram 이라고 하는데 Anagram인지 판단하는 문제이다. 풀이 1️⃣ map을 이용한 풀이 💡 떠오른 Idea s 문자열을 쪼갠 후, 각 문자별 개수를 map에 기록한다. 그리고 t 문자열을 쪼갠 후, 순회하면서 map에 기록되어있는지 확인하고 개수를 -1 한다. 만약, 문자가 존재하지 않거나 개수가 0미만이 되면 false를 반환한다. 또한, 애초에 문자열의 길이가 다르다면 false를 반환한다. [Java] 383. Ransom Note 문제 파악 ransomNote 문자열이 magazine 문자열의 문자들로 구성될 수 있으면 true를, 그렇지 않다면 false를 반환해야한다. magazine의..

[Java] 383. Ransom Note

문제 파악 ransomNote 문자열이 magazine 문자열의 문자들로 구성될 수 있으면 true를, 그렇지 않다면 false를 반환해야한다. magazine의 문자는 중복으로 여러번 쓰일 수 없다. 풀이 1️⃣ map을 이용한 풀이 💡 떠오른 Idea magazine 문자열을 문자로 쪼갠 후, map 자료구조를 이용해서 문자 별 개수를 기록한다. 그리고, ransomNote 문자열의 문자를 순회하면서 기록한 map 자료구조에 문자가 존재하는지 체크하고 있다면 개수를 -1 한다. 기록되어 있는 문자가 없거나 개수가 모자른 경우 false 를 반환한다. import java.util.*; class Solution { public boolean canConstruct(String ransomNote, S..

[Java] 219. Contains Duplicate II

문제 파악 정수 배열인 nums 에서 두 인덱스의 차이가 k 이하이면서 값이 같으면 true를 반환하고 없다면 false를 반환해야한다. 풀이 1️⃣ Map을 이용한 풀이 💡 떠오른 Idea nums를 순회하면서 map에 값을 key로 인덱스를 value로 저장하고, map에 이미 존재하면 현재 위치와 map에 저장되어 있는 인덱스의 차이를 구해서 비교해본다. 만약, 인덱스간 차이가 k보다 크다면 map을 갱신해준다. 왜냐하면 이후에 인덱스 차이가 k 이하인 경우가 생길 수 있기 때문이다. import java.util.*; class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { HashMap map = new HashMa..

[Java] 1. Two Sum

문제 파악 정수 배열 nums 가 주어진다. 배열의 두 원소를 더했을 때, target이 되는 값의 인덱스를 반환해야한다. 답은 정확히 1개 존재한다. 풀이 1️⃣ HashMap 을 이용한 풀이 💡 떠오른 Idea 각 값을 key 로, 인덱스 값을 value 로 저장하는 map을 정의한다. nums 배열을 순회하면서 target-nums[i] 가 map 에 존재하는지 확인하고, 존재한다면 답으로 반환한다. import java.util.*; class Solution { public int[] twoSum(int[] nums, int target) { HashMap map = new HashMap(); for(int i=0;i a[0] - b[0]); int left = 0, right = nodes.l..

[Java] 150. Evaluate Reverse Polish Notation

문제 파악 역 폴란드 표기법에 따른 연산 결과를 반환해야한다. 연산자를 만나면 이전에 만났던 숫자 2개를 연산하는 방식이다. 예로, 4 13 5 / + 의 경우 / 연산자를 만나기 직전 13 과 5가 있으므로 13 / 5 를해주고 나온 결과를 다시 넣어주면 4 2 + 가 된다. 그리고 + 연산자를 만나기 직전 4와 2가 있으므로 4 + 2 를 한 값인 6을 반환하면 된다. 풀이 1️⃣ 스택을 이용한 풀이 💡 떠오른 Idea 역 폴란드 표기법의 연산 방식 상, 스택을 이용해서 풀어야겠다는 생각이 바로 들었다. 연산자를 만나면, 가장 근처에 있는 수를 뒤로 두고 연산한 다음, 다시 스택에 넣는 방식으로 진행하면 될 것이다. import java.util.*; class Solution { Stack stac..

[Java] 155. Min Stack

문제 파악 O(1) 시간 복잡도로 해당 메서드 들을 동작할 수 있도록 구현해야한다. 풀이 1️⃣ Stack 클래스 이용 위 문제에서, 가장 중요한 메서드는 getMin() 메서드이다. 다른, push(), pop(), top() 메서드는 기존 Stack 클래스에서도 O(1) 에 수행할 수 있기 때문이다. 따라서, 스택에 요소를 삽입할 때, 최솟값을 저장하고 getMin() 메서드를 호출할 때 바로 반환할 수 있도록 해야 O(1)을 만족할 수 있을 것이다. 최솟값을 저장하는 스택을 따로 추가해서, 값을 push 할때마다 해당 위치의 스택 값까지의 최솟값을 기록하도록 구현하였다. import java.util.*; class MinStack { Stack stack; Stack stackForMin; pub..

[Java] 74. Search a 2D Matrix

문제 파악 m x n 행렬이 주어진다. 각 행은 비내림차순으로 정렬되어있다. 각 행의 첫 원소는 이전 행의 마지막 원소보다 크다. target이 행렬에 존재하는지 찾아야한다. 시간 복잡도는 O(log(m*n)) 으로 수행해야한다. 풀이 1️⃣ 이분 탐색 💡 떠오른 Idea 행렬 내에 원소가 존재하는지만 판단하면 되기 때문에, 2차원 행렬을 1차원으로 변환시킨 후 이분탐색을 진행하면 시간복잡도 O(log(m*n)) 도 만족하면서, 문제를 해결할 수 있을 것이라 생각이 들었다. 또한, 각 행 내 원소와 행들 끼리 정렬되어 있어서 편하게 이분탐색을 사용할 수 있을 것이라고 판단하였다. 위 아이디어를 바탕으로, 특정 원소를 찾아내는 이분탐색 코드를 구현하였다. class Solution { public bool..

[Java] 35. Search Insert Position

문제 파악 중복되지 않는, 정렬된 정수 배열이 주어진다. target 에 해당하는 원소의 위치나, 없다면 삽입했을때 정렬을 유지할 수 있는 인덱스의 위치를 반환해야한다. 그리고 시간 복잡도는 O(logN) 이어야 한다. 풀이 1️⃣ 이분 탐색 💡 떠오른 Idea 시간 복잡도를 O(logN) 으로 해야한다는 말을 보자마자, 이분탐색으로 해결해야겠구나 생각이 들었다. 이분탐색을 구현해서, target 이 들어갈 수 있는 적절한 위치를 찾으면 된다. nums가 정렬되어있기 때문에 target이 nums의 어떠한 원소보다 작거나 큰 경우는 앞선에서 처리해주었다. 이분탐색에서는, 정렬을 유지하면서 target 값 이하를 배열에 입력할 수 있는 인덱스를 반환하도록 구성하였다. class Solution { publ..

[Java] 21. Merge Two Sorted Lists

문제 파악 정렬된 두 연결 리스트의 첫번째 노드를 입력받는다. 두 연결 리스트를 하나의 정렬된 연결리스트로 만들어야한다. 반드시 입력받은 노드로 구성해야한다. 풀이 1️⃣ 💡 떠오른 Idea 각 리스트의 값을 비교하고, 작은 값을 포함하는 노드를 추가하는 식으로 합치면 된다. 단, 비교할 노드가 없어진 경우 남아있는 노드를 순차적으로 추가해주면 된다. class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode head = new ListNode(); ListNode ans = head; ListNode result; while (list1 != null || list2 != null) { if (list..

[Java] 2. Add Two Numbers

문제 파악 비어있지 않은 두개의 연결 리스트가 주어진다. 음수가 아닌 정수의 숫자를 역순으로 연결리스트에 보관되어있다. ex. 342 인 경우 연결리스트에 [2] -> [4] -> [3] 으로 구성 연결리스트로 표현되는 두 정수의 합을 동일한 방식으로 연결리스트로 반환해야한다. 풀이 1️⃣ 💡 떠오른 Idea l1의 val과 l2의 val을 더하고 10으로 나눈 몫과 나머지를 구한다. 10으로 나눈 몫은 다음 노드들의 val 합에 더해주어야 한다. 나머지를 통해 노드 클래스를 만들어 이전 노드의 next 노드로 연결해준다. 그리고, l1 과 l2의 길이가 다를 수 있다. 따라서, l1 과 l2가 둘다 null이 아니라면 로직을 계속 수행해야한다. 또한, 몫으로 넘어온 값이 있는 경우 노드를 추가로 생성해..

[Java] 141. Linked List Cycle

문제 파악 연결 리스트의 헤드가 주어진다. 그리고 이 연결 리스트가 사이클을 이루는지 결정해야한다. 풀이 1️⃣ Set 자료구조를 이용한 풀이 💡 떠오른 Idea 노드를 set 자료구조에 입력하고, 다음 노드로 진행하기 전에 진행할 노드가 set에 입력되어있는지 확인한다. 진행할 노드가 set에 입력되어있었다면, 사이클임을 알 수 있다. 위 아이디어를 바탕으로 코드를 작성하였다. public class Solution { public boolean hasCycle(ListNode head) { Set set = new HashSet(); ListNode now = head; set.add(now); while (now != null) { ListNode nextNode = now.next; if (set..

[Java] 3. Longest Substring Without Repeating Characters

문제 파악 문자열 s가 주어진다. 문자가 반복되지 않는 가장 긴 부분 문자열을 반환해야한다. 풀이 1️⃣ Queue 를 이용한 풀이 💡 떠오른 Idea 문자열을 순회하면서, Queue에 문자를 입력한다. 단, 입력하기 전, 입력하려는 문자가 Queue에 이미 존재한다면 그 문자를 제거하고 입력한다. 만약 pwwkew 문자열인 경우 첫 p는 큐에 없으므로 큐에 입력한다. Queue = [ p ] 두번째 w로 아직 큐에 없으므로 큐에 입력한다. Queue = [ p, w ] 세번째 w는 이미 큐에 존재하는 문자이므로 큐에 문자 w가 없어질때까지 pop 한다. 그리고 입력한다. Queue = [ w ] ... 이런식으로 진행되면서 중복되는 문자가 없는 부분 문자열이 큐에 갱신된다. class Solution ..

[Java] 209. Minimum Size Subarray Sum

문제 파악 정수 배열 nums 와 양수 target 이 주어진다 부분 집합의 합이 target 과 동일하거나 이상 값을 갖는 최소 길이를 반환해야한다. 없다면, 0을 반환한다. 풀이 1️⃣ 투 포인터 풀이 💡 떠오른 Idea 투포인터 방식으로 부분합을 구하다가, target과 동일하거나 그 이상 값이 되면 기록한다. 그리고, 왼쪽 포인터를 옮긴 뒤에 다시 탐색을 한다. class Solution { public int minSubArrayLen(int target, int[] nums) { int ans = Integer.MAX_VALUE; int left = 0, right = 0; int sum = 0; while (right = target 이 되는 부분 찾기 int find = target + f..

[Java] 167. Two Sum II - Input Array Is Sorted

문제 파악 비 내림차순으로 정렬되어 있는 정수 배열 numbers 가 주어진다. 배열에서 target 값을 만들 수 있는 값 2개를 찾아, 해당 값의 인덱스를 반환해야한다. ( index1 < index2 ) 풀이 1️⃣ 투 포인터 방식 💡 떠오른 Idea 인덱스 0 부터 시작하는 left 와 배열의 끝에서 시작하는 right 포인터를 정의한 뒤, 두 값의 합이 target 보다 크면 right 포인터를 감소시키고 target보다 작으면 left 를 증가시키는 방식으로 구현하면 될 것이라 판단했다. 왜냐하면, 비 내림차순으로 정렬되어 있고 정답이 무조건 존재하는 배열로 주어지기 때문에 가능하다고 판단했다. 그리고 시간복잡도도 O(N) 으로 해결할 수 있기 때문이다. class Solution { publ..

[Java] 125. Valid Palindrome

문제 파악 모든 대문자를 소문자로 변환 후, 숫자와 알파벳이 아닌 문자를 제거한 문자가 뒤로 읽었을때와 앞으로 읽었을때가 같으면 palindrome 이라고 한다. palindrome 이 맞으면 true를, 아니면 false를 반환하라 풀이 1️⃣ StringBuilder 사용 풀이 💡 떠오른 Idea 먼저, 공백과 문자 혹은 숫자가 아닌 것들을 제거해서 붙이는 작업이 필요하다. 그리고, 역순으로 나열한 문자와 동일한지 확인해서 palindrome 인지 확인하면 될 것이다. class Solution { public boolean isPalindrome(String s) { StringBuilder sb = new StringBuilder(); char[] arr = s.toLowerCase().toCha..