분류 전체보기

[Java] 153. Find Minimum in Rotated Sorted Array

문제 파악 rotated 된 배열 nums의 최솟값을 찾는 문제이다. 시간 복잡도는 O(logN) 을 만족해야한다. 풀이 1️⃣ 이분 탐색을 이용한 풀이 💡 떠오른 Idea 이전에 풀었던 Search in Rotated Sorted Array 문제의 일부분과 같은 문제라서 쉽게 해결할 수 있었다. 이분 탐색을 진행하는데, mid 위치의 값과 right 위치의 값을 비교해서 mid 값이 작은 경우, mid 위치의 원소들은 오름차순으로 구성되어 있음을 보장할 수 있기 때문에 탐색 영역을 왼쪽 영역으로 이동하는 방식으로 구현하면 된다. class Solution { public int findMin(int[] nums) { int left = 0, right = nums.length - 1; while (le..

[Java] 33. Search in Rotated Sorted Array

문제 파악 오름차순으로 정렬되어 있는 배열 nums가 있었다. 인덱스 k번째 원소가 제일 첫 원소가 되도록 rotated 되어있다. target 이 배열 nums 에 포함되어있는지 O(logN) 으로 탐색하여 인덱스를 반환해야한다. 풀이 1️⃣ 이분 탐색을 이용한 풀이 💡 떠오른 Idea 먼저, 주어진 시간 복잡도를 만족하기 위해선 이분 탐색을 사용해야함을 알 수 있었다. 결과적으로는, target이 nums에 존재하는지를 이분 탐색해야하는데 특정 값을 탐색하기 위해선 정렬되어있어야 한다. 따라서, rotated된 배열을 정렬된 두개의 배열로 나누기 위해 배열 내의 최솟값을 검색한다. ex) [4, 5, 6, 7, 0, 1, 2] 배열이 있을 때, [4, 5, 6, 7] 과 [0, 1, 2] 배열 2개로..

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

병합 정렬 (Merge Sort) 을 구현해보자

정렬을 할 수 있는 방법은 여러가지가 있다. 대표적으로 다음과 같은 방법이 있다. 💡 정렬의 종류와 방식 1. 버블 정렬 : 2개의 원소를 계속 비교해나가며 값이 큰 원소가 앞에 있는 경우 위치를 교환한다. 제일 큰 값(오름차순의 경우)을 제일 뒤로 보내어 최종적으로 정렬된다. 시간 복잡도는 O(N^2)으로 볼 수 있다. 만약 한번 순회했을 때 두 원소간 위치가 변한 적이 없다면 순회를 빠져나가는 방식으로 최적화를 할 수 있다. 2. 선택 정렬 : 원소들을 순회하여 가장 작은 값을 찾은 뒤(선택), 제일 앞 원소와 위치를 바꿈으로서 작은 값이 계속 앞으로 이동하면서 최종적으로 정렬된다. 시간 복잡도는 O(N^2)으로 볼 수 있다. 3. 삽입 정렬 : 2번째 원소부터 시작해서 N번째 원소까지 N-1까지의 ..

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