👨🏻‍💻 PS

[Java] 162. Find Peak Element

문제 파악 주변 원소들보다 큰 원소를 peak element라고 한다. 그러한 원소가 여러개라면 아무 원소의 인덱스를 반환하면 된다. 시간 복잡도가 O(logN) 이 되도록 구현해야한다. 풀이 1️⃣ 이분 탐색을 이용한 풀이 💡 떠오른 Idea 시간복잡도를 통해 이분 탐색을 이용해야함을 알 수 있었다. 보통 이분탐색은 정렬된 배열에서만 사용해와서, 이분 탐색을 어떻게 활용할 수 있을지 오랫동안 생각해보았다. mid 포인트 값이 mid + 1 포인트 값보다 작다면? mid 포인트 값은 peak element 가 될 확률이 존재하지 않는다. 따라서 탐색 범위를 mid+1 이상으로 잡아줘야 할 것이다. 만약, mid 포인트 값이 mid + 1 포인트 값 보다 크다면 mid 포인트 값은 peak element ..

[Java] 148. Sort List

문제 파악 연결 리스트의 head가 주어진다. 오름차순으로 정렬해서 반환해야한다. 풀이 1️⃣ 배열과 mergeSort 💡 떠오른 Idea O(NlogN) 방식으로 해결하기 위한 방법을 떠올려봤다. 해당 시간 복잡도로 정렬할 수 있는 Merge Sort 방식을 사용해야 해결할 수 있을 것이라 판단했다. class Solution { public ListNode sortList(ListNode head) { int cnt = getCount(head); System.out.println(cnt); int[] arr = new int[cnt]; ListNode dummyHead = new ListNode(0, head); ListNode node = head; for (int i = 0; i < cnt; i..

[JAVA] 백준 22939번 【G4.문제 추천 시스템 Version 1】

문제 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 풀이 1️⃣ TreeMap 과 TreeSet을 이용한 풀이 💡 떠오른 Idea 1. 요구사항에 가장 난이도가 낮은 것에서 가장 문제번호가 작은 것과 가장 난이도가 높은 것에서 가장 문제번호가 큰 것을 출력하라고 했다. 따라서, 난이도를 key로 정렬해주는 TreeMap안에 value로 문제 번호의 크기순으로 정렬해주는 TreeSet을 사용하면 되겠다고 판단했다. 2. 또한, solved 요청 시 문제 번호를 입력받아 지워야 하는..

[JAVA] 백준 20166번 【G4.문자열 지옥에 빠진 호석】

문제 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 풀이 1️⃣ 백트래킹과 map을 이용한 풀이 이 문제는 백트래킹과 해시를 통해 문제를 해결하였다. 백트래킹을 통해서 만들 수 있는 문자열의 조합별 개수를 기록하였는데, 경로가 다르면 다른 경우의 수로 치기 때문이다. 백트래킹을 map의 각 포인트에서 시작하도록 설정하였고 탈출 조건을 설정한 길이에 도달했을 때 기록하는 방식을 사용했다. 왜냐하면, 예를 들어 (1,1) 에서 시작해서 길이가 2를 만족할때의 경우의 수는 다른 포인트에서 시작한 길이가 2인 경우와 절대 중복이 발생하지 않을 것이라 판단했기 때문이다. import java.io.*;..

[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] 백준 13414번 【S3.수강신청】

문제 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 풀이 먼저 이 문제는, 수강 신청을 한 학생들을 순서대로 자료구조에 넣어야 하는데, 이미 그 자료구조에 들어가 있는 학생인 경우, 제일 뒷 순서로 다시 집어넣어야 한다. 이 아이디어는, 이 문제를 푸는 누구나 떠올렸을텐데 생각보다 간단하게 풀릴 줄 알았는데 아니었다. 1️⃣ map과 priority queue 사용 set을 이용해서 중복여부를 확인할 수 있지만, 수강 신청 순서를 확인할 순 없다. HashMap map = new HashMap()..

[JAVA] 백준 20366번 【G3.같이 눈사람 만들래?】

문제 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 풀이 1️⃣ 조합을 이용한 풀이 주어진 눈덩이 중 2개로 만들 수 있는 눈사람의 높이를 모두 구한다. 단, 두 사람이 같은 눈덩이를 사용할 수 없다. 서로 다른 눈덩이 4개가 사용되어야 한다. 따라서, 그냥 합의 조합만 구하면 이러한 부분을 체크할 수 없기 때문에 어떤 인덱스의 눈덩이로 눈사람을 만든건지 정보가 필요하다. 따라서, 클래스를 새롭게 하나 정의해야한다. static class SnowMan{ int idx1; int..

[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..