[LeetCode] 205. Isomorphic Strings [Java]
알고리즘 분류: 해시맵 문제 링크: https://leetcode.com/problems/isomorphic-strings/description/ 【 문제 】 두 문자열 s와 t가 주어졌을 때, 두 문자열의 형태가 같은 지 판단하는 문제이다. 【 풀이】 s의 각 문자 위치에 해당되는 t의 문자를 map에 저장한다. 이미 저장된 문자가 다른 문자와 매핑되어 있다면 false를 반환한다. t의 문자가 이미 다른 문자에 매핑되어 있다면 false를 반환한다. 시간 복잡도: O(n) 공간 복잡도: O(n) 【 코드】 public class LeetCode_205 { public boolean isIsomorphic(String s, String t) { Map map = new HashMap(); for (in..
[프로그래머스] 야근 지수 [Java]
알고리즘 분류: 우선순위 큐, 구현, 시뮬레이션 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 【 문제 】 야근 피로도는 works 배열 각 요소들의 제곱의 합이다. 주어진 n을 통해 works 에서 주어진 각 일들의 작업량을 1씩 줄일 수 있다. 이때, 야근 피로도를 최소로 줄였을 때의 그 야근 피로도를 반환하는 문제이다. 【 풀이 】 가장 작업량이 많은 일을 먼저 처리하는 것이 이득이다. 따라서 works 배열을 내림차순으로 ..
[LeetCode] 125. Valid Palindrome [Java]
알고리즘 분류: 문자열, 파싱 문제 링크: https://leetcode.com/problems/valid-palindrome/description/ 【 문제 】 주어진 문자열이 팰린드롬(가운데를 기준으로 양쪽이 동일한 문자열)인지 확인하는 문제이다. 대소문자를 구분하지 않으며(모두 소문자로), 영문자와 숫자만을 대상으로 한다. 【 풀이 】 문자열을 순회하며 영문자와 숫자만을 StringBuilder에 추가한다. (Character 인터페이스의 isLetterOrDigit 메소드 사용) StringBuilder의 처음과 끝부터 비교하며 팰린드롬 여부를 확인한다. 시간 복잡도: O(n) 공간 복잡도: O(n) 【 코드 】 public class LeetCode_125 { public boolean isPa..
[LeetCode] 392. Is Subsequenc [Java]
알고리즘 분류: 파싱 문제 링크: https://leetcode.com/problems/is-subsequence/description/ 【 문제 】 문자열 s와 t의 subsequence 인지 확인하는 문제이다. 【 풀이 】 문자열 s와 t의 길이가 0이면 true를 반환한다. 문자열 t를 순회하면서, s의 문자와 같은 문자가 나오면 idx를 증가 시킨다. idx가 s의 길이와 같아지면 s가 t의 subsequence 임을 의미하므로, true를 반환한다. t를 모두 순회했을 때, idx가 s의 길이와 같아지지 않으면 false를 반환한다. 시간 복잡도: O(n) 공간 복잡도: O(1) 【 코드 】 public class LeetCode_392 { public boolean isSubsequence(S..
[백준] 1149번: RGB거리 [C++]
알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 【 풀이 】 한층 밑으로 내려갈 때마다 각 칸에 맞는 경우의 수 중에 최솟값을 저장하고 마지막 값들 중 최솟값을 출력해주면 되는 문제이다. 최솟값을 계산해 저장하는 배열을 dp, 원본 배열은 rgb라고 하자. dp[0][0] = rgb[0][0] dp[0][1] = rgb[0][1] dp[0][2] = rgb[0][2] 가 될 ..
[백준] 7576번: 토마토 [C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 【 풀이 】 이 문제는 시작점이 여러 개로 주어질 수 있기 때문에, 여러 정점에서 동시에 출발할 수 있도록 해주어야 한다. 즉 모든 시작점(1) 들을 큐에 밀어 넣어서, bfs를 정점들마다 번갈아가면서 탐색할 수 있게끔 해주면 된다. 그리고 날짜를 기록하는 게 곧 탐색의 거리를 의미하기도 하기에 배열마다 거리..
