본문 바로가기

Algorithm/문제풀이

 (45)
[백준] 2164번: 카드2 문제링크 : https://www.acmicpc.net/problem/2164 문제풀이 처음엔 규칙을 찾아서 풀으려고 했는데, 이 문제는 Deque를 사용해서 푸는 문제가 맞는 것 같다. 문제에 나온 순서대로 값 추가 / 삭제를 하면 된다. Deque : https://manzoo.tistory.com/83 소스코드 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Deque; public class P2164 { public static void main(String[] ar..
[LeetCode] 4번: Median of Two Sorted Arrays 문제링크 : https://leetcode.com/problems/median-of-two-sorted-arrays/ 문제풀이 두 배열을 합쳤을 때 중간 값을 출력하는 문제이다. 홀수 개 일 때는 중간 값 출력, 짝수 개 일 때는 중간 두 값의 평균을 출력한다. 문제를 보니 병합정렬이 생각나서 그 방식을 떠올리며 문제를 풀었다. 1) nums1과 nums2의 길이를 더한 만큼의 크기로 배열을 생성한다. 2) 각 배열의 첫번째 값, nums1[0]과 nums2[0]를 비교한다. 더 작은 값을 nums 배열에 넣는다. 3) 이전 작업에서 nums1[0] 값을 넣었으므로, 다음 값을 비교한다. nums1[1]과 nums2[0]을 비교해 더 작은 값을 nums 배열에 넣는다. (이하반복) 4) 2~3 작업을 반..
[LeetCode] 3번: Longest Substring Without Repeating Characters 문제링크 : https://leetcode.com/problems/longest-substring-without-repeating-characters/ 문제풀이 중복되는 문자를 포함하지 않는, 가장 긴 구간을 찾는 문제이다. 방법1) 입력된 문자의 처음부터 끝까지 중복되지 않는 모든 경우를 찾는다. 가장 단순한 방법이지만, 이렇게 풀면 n까지 for문을 두 번 돌게 되므로 O(n2)의 시간복잡도가 나온다. 방법2) 투 포인터 알고리즘을 사용한 방법이다. 투 포인터 알고리즘은 인덱스를 가리키는 두 개의 포인터를 이동시키는 방법이다. 포인터 i, j가 있다고 하면, 조건에 일치하는 경우 j 포인터 이동, 일치하지 않는 경우 i 포인터를 이동시킨다. Set은 중복을 허락하지 않는 자료구조이다. Set에 값을 ..
[LeetCode] 2번: Add Two Numbers 문제링크 : https://leetcode.com/problems/add-two-numbers/ 문제풀이 두 링크드 리스트의 각 숫자끼리 짝지어 차례로 더하는 문제이다. 링크드 리스트의 길이가 서로 다를 때 오류가 발생하여 한쪽 값이 null이면 숫자 0을 더하도록 수정했다. 소스코드 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode nextNode = null; List..
[LeetCode] 1번: Two Sum 문제링크 : https://leetcode.com/problems/two-sum/ 문제풀이 배열의 데이터들을 두 개씩 더하면서 target과 일치하는지 체크한다. 소스코드 class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length - 1; i++) { for (int j = i + 1; j < nums.length; j++) { int sum = nums[i] + nums[j]; if (sum == target) { return new int[] {i, j}; } } } return null; } }
[백준] 4963번: 섬의 개수 문제링크 : https://www.acmicpc.net/problem/4963 문제풀이 DFS/BFS로 풀 수 있는 문제이다. DFS로 풀었으며 상하좌우, 대각선 네 방향으로 이동하면서 땅이 있는지 체크하였다. 소스코드 import java.io.*; import java.util.*; public class p_4963 { static final int MAX = 50; static int[][] map = new int[MAX][MAX]; static int[] dx = new int[] {0, -1, -1, -1, 0, 1, 1, 1}; static int[] dy = new int[] {1, 1, 0, -1, -1, -1, 0, 1}; public static void main(String[] a..
[백준] 10828번: 스택 문제링크 : https://www.acmicpc.net/problem/10828 문제풀이 Stack 자료구조를 이용해서 명령에 따라 그에 해당하는 작업을 처리하면 된다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Stack; import java.util.StringTokenizer; public class p_10828 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sys..
[백준] 1012번: 유기농 배추 문제링크 : https://www.acmicpc.net/problem/1012 문제풀이 dfs, bfs로 풀 수 있는 문제이다. 문제 2667번과 동일한 방식으로 쉽게 풀 수 있다. dfs, bfs 두 방식으로 모두 풀어보았다. 소스코드 import java.io.*; import java.util.*; public class p_1012 { static int[][] arr = new int[50][50]; static int[] dx = {0, 0, -1, 1}; static int[] dy = {1, -1, 0, 0}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(ne..

티스토리툴바