1. 등굣길 - lv 3
출처 https://school.programmers.co.kr/learn/courses/30/lessons/42898
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
Sol)
<hide/>
// 프로그래머스 - 등굣길
import java.util.Arrays;
public class Practice2 {
public static int solution(int m, int n, int[][] puddles) {
int mod = 1000000007;
int[][] board = new int[n + 1][m + 1];
for(int i = 0;i < puddles.length; ++i){
board[puddles[i][1]][puddles[i][0]] = -1;
}
board[1][1] = 1; // 방문 처리
for(int i = 1;i <= n; ++i){
for(int j = 1;j <= m; ++j){
if(board[i][j] == -1){
continue;
}
if(board[i][j - 1] > 0 ){
board[i][j] += board[i][j - 1] % mod;
}
if(board[i - 1][j] > 0 ){
board[i][j] += board[i - 1][j] % mod;
}
}
}
for(int[] b: board){
System.out.println(Arrays.toString(b));
}
return board[n][m] % mod;
}
public static void main(String[] args) {
int [][] puddles = {{2, 2}};
System.out.println(solution(4, 3, puddles)); // 4
}
}- 중학교 교과과정 중에 있는 경우의 수 파트 내용과 관련이 있다.
- 첫 행과 첫 번째 열에 있는 위치로 가는데 최단 거리는 모두 1일 것이다.
-> 이를 지나서 갈 수 있는 다른 위치들에 대해 대각선끼리 더해주다 보면 마지막에는 목표 지점까지 가는데 경우의 수를 구할 수 있게 된다.
- 물 웅덩이에 대한 배열 puddles을 {2, 2}라고 주는데 배열 딸랑 하나만 주고 나니까 이게 행, 열 중 무엇이 먼저인지 헷갈렸다.
-> 문제에서 행을 n, 열을 m으로 주어지니까 웅덩이 배열도 이와 반대로 넣어주니 해결됐다.
-> board[puddles[i][1]][puddles[i][0]] = 1
2. 라그랑주의 네 제곱수 정리
출처 https://www.acmicpc.net/problem/3933
3933번: 라그랑주의 네 제곱수 정리
입력은 최대 255줄이다. 각 줄에는 215보다 작은 양의 정수가 하나씩 주어진다. 마지막 줄에는 0이 하나 있고, 입력 데이터가 아니다.
www.acmicpc.net
Sol) 2000ms -> 1700ms
<hide/>
import java.util.Scanner;
// 라그랑주의 네제곱수 정리
public class BaekJoon1 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int num, end, cnt;
while(true){
cnt = 0; // 초기화
num = scan.nextInt();
if(num == 0){
return;
}
end = (int) Math.sqrt(num); // 소수는 따질 필요 없으니 int로 한다. 제곱수로 만들 수 있는 후보 중 가장 큰 값
for(int i = 1; i <= end; ++i){
// i = end이면서 제곱근인 경우
// input이 제곱수인 경우에 딱 한번만 실행될 것이다.
if(i * i == num){
++cnt;
break;
}
for(int j = i; j <= end; ++j){
if (i * i + j * j == num){ // 두 개만으로 제곱수를 만들 수 있는 경우
++cnt;
break; // . 따라서 continue처리
} else if (i * i + j * j > num) {
break; // 다음 반복문은 j가 더 크니까 어차피 조건을 만족하지 못할 것이다 break 하고 다음 i로 넘어간다.
}
for(int k = j; k <= end; ++k) {
if (i * i + j * j + k * k == num) { // 세 개만으로 제곱수를 만들 수 있는 경우
++cnt;
break;
} else if (i * i + j * j + k * k > num) {
break;
}
for(int l = k; l <= end; ++l){
if(i * i + j * j + k * k + l * l == num){ // 네 개만으로 제곱수를 만들 수 있는 경우
++cnt;
break;
}else if(i * i + j * j + k * k + l * l > num){
break;
}
}
}
}
}
System.out.println(cnt);
}
}
}
- 4중 for문을 이용한다.
- end = Math.sqrt(num);으로 제곱수를 만들기 위한 후보의 최댓값을 정한다.
- while문은 마지막에 0이 들어오면 return하도록 작성한다.
- 반복문의 if문에 대해 break를 걸어주니까 처음에 continue를 했을 때보다 속도가 700ms 정도 줄었다.
cf) 유사한 문제인 백준 17626번과는 다르게 이 문제는 조합에 가깝다. (17626번에서는 dp[5]를 1^2 + 2^ 2, 2^2 + 1^1 을 다르게 본다. => 순열에 가깝다.)
- 따라서, for문의 각각 i, j, k, l에 대해서 j는 i부터 시작, k는 j부터 시작, .. 하여 순서는 다르지만 구성이 같은 묶음이 발생하지 않도록 방지한다.
유사 문제 https://www.acmicpc.net/problem/17626
17626번: Four Squares
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1
www.acmicpc.net
3. Maximum Product Subarray - Midium
출처 https://leetcode.com/problems/maximum-product-subarray/submissions/
Maximum Product Subarray - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Sol) 2ms
참고) https://itkevin.tistory.com/41
<hide/>
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Practice3 {
static int[] nums;
public static int maxProduct(int[] nums) {
int max = nums[0];
int min = nums[0];
int result = nums[0];
for(int i = 1; i < nums.length; ++i){
System.out.println("i = "+ i + ", nums[i] = " + nums[i]);
int now = nums[i];
int tmpMax = max * now;
int tmpMin = min * now;
System.out.println("tmpMax = " + tmpMax);
System.out.println("tmpMin = " + tmpMin);
max = Math.max(now, Math.max(tmpMax, tmpMin));
min = Math.min(now, Math.min(tmpMax, tmpMin));
System.out.println("max = " + max);
System.out.println("min = " + min);
result = Math.max(result, max);
System.out.println("result = " +result);
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 3,-2,4}; // 2 3 -2 4 = > 6 -8
System.out.println(maxProduct(nums)); // 6
nums = new int[]{0, 2};
System.out.println(maxProduct(nums)); // 2
nums = new int[]{2, 0, -1};
System.out.println(maxProduct(nums)); // 2
nums = new int[]{-2, 3, -4};
System.out.println(maxProduct(nums)); // 24
nums = new int[]{2,-5,-2,-4,3};
System.out.println(maxProduct(nums)); // 24
nums = new int[]{1,0,-1,2,3,-5,-2};
System.out.println(maxProduct(nums)); // 60
}
}- max, min의 초깃값은 nums[0]으로 두고 for문은 i = 1부터 시작해서 비교한다.
- max와 min은 현재 배열의 원소 / tmpMax / tmpMin 중에 최댓값과 최솟값
-> i가 바뀔 때마다 result에는 부분배열끼리 곱해서 나올 수 있는 최댓값이 저장되고 min에는 최솟값이 저장된다.
-> now를 곱해서 나온 tmpMax, tmpMin보다 now가 더 큰 경우에는 now을 선택할 수 있도록 Math.max() 함수를 이용한다.
- tmp가 음수일 경우, 양수인 max를 곱해서 나오는 tmpMax 보다 음수인 tmpMin을 곱하는 결괏값이 더 클 수 있다.
== 오류 코드 ==
<hide/>
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Practice3 {
static int[] nums;
public static int maxProduct(int[] nums) {
int n = nums.length;
Practice3 solutions = new Practice3();
Practice3.nums = nums;
return solve(0, nums.length - 1);
}
public static int solve(int left, int right){ //left: 0, right: 2 => mid = 1
if(left == right){
return nums[left];
}
int mid = left + (right - left) / 2;
int ret = Math.max(solve(left, mid), solve(mid + 1, right));
int l = mid; // 1
int r = mid + 1; // 2
int mul = 1;
mul = nums[l] * nums[r];
ret = Math.max(mul, ret);
while(left < l || r < right){ // 둘다 양 끝쪽으로 이동할 때 까지 이동하낟.
if(left == l && r < right ||
left < l && r < right && mul <= mul * nums[r + 1] && mul * nums[l - 1] <= mul * nums[r + 1]){ // 오른쪽으로 이동해야하는 상황
++r;
mul *= nums[r];
// System.out.printf( "mul *= %d = %d %n",nums[r], mul);
}else { // 조건을 더 추가??모르겠다.
--l;
mul *= nums[l];
// System.out.printf( "mul *= %d = %d %n", nums[l], mul);
}
// System.out.printf( "max(%d, %d) %n", ret, mul);
ret = Math.max(ret, mul);
// System.out.printf( "ret = %d%n", ret);
}
return ret;
}
public static void main(String[] args) {
int[] nums = {2, 3,-2,4}; // 2 3 -2 4 = > 6 -8
System.out.println(maxProduct(nums)); // 6
nums = new int[]{0, 2};
System.out.println(maxProduct(nums)); // 2
nums = new int[]{2, 0, -1};
System.out.println(maxProduct(nums)); // 2
nums = new int[]{-2, 3, -4};
System.out.println(maxProduct(nums)); // 24
nums = new int[]{2,-5,-2,-4,3};
System.out.println(maxProduct(nums)); // 24
nums = new int[]{1,0,-1,2,3,-5,-2};
System.out.println(maxProduct(nums)); // 60
}
}- 케이스의 길이가 길어지면 자꾸 에러가 났다....
- while문을 적당히 수정하면 될 것 같다..
4. Largest Palindrome Product - hard
- input으로 자릿수가 주어지면 그 자릿수 내의 자연수끼리 곱해서 만들 수 있는 가장 큰 팰린드롬 숫자를 반환하라.
- 정답을 1337로 나눠 반환한다.
출처 https://leetcode.com/problems/largest-palindrome-product/
Largest Palindrome Product - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Sol) 500ms
<hide/>
import java.util.Scanner;
public class LeetCode {
public static int largestPalindrome(int n) { // 2
if(n == 1){
return 9;
}
long max = (long) Math.pow(10, n) - 1; // 99
long start = max - 1; // 98
long end = (long) Math.pow(10, n - 1); // 10
for(long i = start - 1; i >= end; --i){
// 97부터 시작한다.
// max - 1부터 하면 553ms
// max - 2 = start 부터 하면 335
String str = String.valueOf(i);
StringBuffer sb = new StringBuffer(str).reverse();
long palindromeCan = Long.parseLong(str + sb.toString());
// System.out.println("palindromeCan: " + palindromeCan);
long min = (long) Math.ceil(Math.sqrt(palindromeCan)); // 팰린드롬보다 작거나 같은 수중에서 가장 큰 제곱근
// System.out.println("max: " + max);
// System.out.println("min: " + min);
for(long j = max; j >= min ; --j){ // max = 99 부터 시작하는건 고정이다.
if(palindromeCan % j == 0){
return (int) (palindromeCan % 1337);
}
}
// System.out.println();
}
return -1;
}
/* 팰린드롬 판별 메서드
public static boolean isPallindrome(String str){
// String str = String.valueof;
for(int i = 0; i < str.length() / 2; ++i){
if(str.charAt(i) != str.charAt(str.length() - 1 - i)){
return false;
}
}
return true;
}
*/
public static void main(String[] args){
System.out.println(largestPalindrome(2)); // 987
System.out.println(largestPalindrome(4)); // 597
System.out.println(largestPalindrome(5)); // 677
System.out.println(largestPalindrome(6)); // 1218
}
}- n은 최대 8까지 입력 가능 => 10^16 이면 long의 범위 내에 있다.
- int: 2^31 = 약 21억
- long: 2^63 = 약 9 * 10^18
-> 따라서 n에 6을 넣을 때부터는오버플로우가 발생해서 마이너스 값이 나온다.
-> 그래서 문제에서 1337로 나눈 나머지를 반환하도록 주어진다.
- StringBuffer에 있는 reverse()메서드를 이용하면 문자열을 뒤집을 수 있다.
-> String str과 str을 뒤집은 StringBuffer sb를 이어 붙이면
-> Long.parseLong(str + sb.toString()) 는 팰린드롬을 만족하는 long형 데이터가 된다.
- for문의 인덱스를 start - 1, 즉 max -2 (= 97)부터 실행해야 속도가 300ms정도로 나온다.
-> 팰린드롬을 만들기 위한 데이터인 i는 99, 98은 왜 안 넣을까?
-> for문을 보면 j는 max부터, 즉 가능한 가장 큰 값인 max부터 min을 대입하는 것이 고정되어 있다.
-> 따라서, i에 대한 for문까지 굳이 99부터 시작할 필요가 없다. (99 * 99 => 팰린드롬이 되더라고 j에대한 for문에서 카운트 할 것이기 때문이다.)
5. WildCard Matching
출처 https://leetcode.com/problems/wildcard-matching/submissions/
Wildcard Matching - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
참고) https://github.com/hanbi97/LeetCode/blob/main/wildcard-matching/wildcard-matching.java
https://hanbi97.tistory.com/478
Sol)
<hide/>
import java.util.ArrayList;
import java.util.Scanner;
public class BaekJoon3 {
public static boolean isMatch(String s, String p) {
if(p == null || s == null) {
return false;
}
boolean [][] dp = new boolean[s.length() + 1][p.length() + 1];
// 초기화
dp[0][0] = true;
for(int i = 1; i <= s.length(); ++i){ //
dp[i][0] = false;
}
for(int j = 1;j <= p.length(); ++j){
if(p.charAt(j - 1)== '*'){
dp[0][j] = dp[0][j - 1];
}
}
// 계산
for(int i=1; i<=s.length(); i++){
for(int j = 1; j <= p.length(); j++){
if((s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?') && dp[i-1][j-1])
dp[i][j] = true;
else if (p.charAt(j-1) == '*' && (dp[i-1][j] || dp[i][j-1]))
dp[i][j] = true;
}
}
return dp[s.length()][p.length()];
}
public static void main(String[] args) {
String str = "aa";
String pattern = "a";
System.out.println(isMatch(str, pattern)); // false
str = "aa";
pattern = "*";
System.out.println(isMatch(str, pattern)); //true
str = "cb";
pattern = "?a";
System.out.println(isMatch(str, pattern)); // false
str = "adceb";
pattern = "a???b";
System.out.println(isMatch(str, pattern)); // true
str = "adceb";
pattern = "*a*b";
System.out.println(isMatch(str, pattern)); // false
}
}- 어떤 String str에 대해 str.length() = 0과 str = null 은 다르다.
- "" 와 null의 차이는?
->"": 실제 문자열이지만 비어있는 문자열(str = "")이다., null은 String 변수가 아무것도 가리키지 않는다.
-> ""는 실제 문자열이므로 String의 length()같은 메서드를 호출 가능, null은 불가능하다.
'자료구조와 알고리듬 With Java > [Study] BAEKJOON 프로그래머스 CodeUp LeetCode' 카테고리의 다른 글
| 2022-07-27 [8회차] 알고리즘 스터디 (0) | 2022.07.26 |
|---|---|
| 2022-07-20 [7회차] 알고리즘 스터디 (0) | 2022.07.20 |
| 2022-06-29 [5회차] 알고리즘 스터디 (0) | 2022.07.06 |
| 2022-06-29 [4회차] 알고리즘 스터디 (0) | 2022.06.29 |
| 2022-06-22 [3회차] 알고리즘 스터디 (0) | 2022.06.22 |