1. 등굣길 - lv 3 출처 https://school.programmers.co.kr/learn/courses/30/lessons/42898
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
Sol)
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));
}
} - 중학교 교과과정 중에 있는 경우의 수 파트 내용과 관련이 있다.
- 첫 행과 첫 번째 열에 있는 위치로 가는데 최단 거리는 모두 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
import java.util.Scanner;
public class BaekJoon1 public static void main (String[] args) new Scanner(System.in);
int num, end, cnt;
while (true ){
cnt = 0 ;
num = scan.nextInt();
if (num == 0 ){
return ;
}
end = (int ) Math.sqrt(num);
for (int i = 1 ; i <= end; ++i){
if (i * i == num){
++cnt;
break ;
}
for (int j = i; j <= end; ++j){
if (i * i + j * j == num){
++cnt;
break ;
} else if (i * i + j * j > num) {
break ;
}
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
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 };
System.out.println(maxProduct(nums));
nums = new int []{0 , 2 };
System.out.println(maxProduct(nums));
nums = new int []{2 , 0 , -1 };
System.out.println(maxProduct(nums));
nums = new int []{-2 , 3 , -4 };
System.out.println(maxProduct(nums));
nums = new int []{2 ,-5 ,-2 ,-4 ,3 };
System.out.println(maxProduct(nums));
nums = new int []{1 ,0 ,-1 ,2 ,3 ,-5 ,-2 };
System.out.println(maxProduct(nums));
}
} - 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을 곱하는 결괏값이 더 클 수 있다.
== 오류 코드 ==
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) 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;
int r = mid + 1 ;
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];
}else {
--l;
mul *= nums[l];
}
ret = Math.max(ret, mul);
}
return ret;
}
public static void main (String[] args) int [] nums = {2 , 3 ,-2 ,4 };
System.out.println(maxProduct(nums));
nums = new int []{0 , 2 };
System.out.println(maxProduct(nums));
nums = new int []{2 , 0 , -1 };
System.out.println(maxProduct(nums));
nums = new int []{-2 , 3 , -4 };
System.out.println(maxProduct(nums));
nums = new int []{2 ,-5 ,-2 ,-4 ,3 };
System.out.println(maxProduct(nums));
nums = new int []{1 ,0 ,-1 ,2 ,3 ,-5 ,-2 };
System.out.println(maxProduct(nums));
}
} - 케이스의 길이가 길어지면 자꾸 에러가 났다....
- 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
import java.util.Scanner;
public class LeetCode public static int largestPalindrome (int n) if (n == 1 ){
return 9 ;
}
long max = (long ) Math.pow(10 , n) - 1 ;
long start = max - 1 ;
long end = (long ) Math.pow(10 , n - 1 );
for (long i = start - 1 ; i >= end; --i){
String str = String.valueOf(i);
StringBuffer sb = new StringBuffer(str).reverse();
long palindromeCan = Long.parseLong(str + sb.toString());
long min = (long ) Math.ceil(Math.sqrt(palindromeCan));
for (long j = max; j >= min ; --j){
if (palindromeCan % j == 0 ){
return (int ) (palindromeCan % 1337 );
}
}
}
return -1 ;
}
public static void main (String[] args) 2 ));
System.out.println(largestPalindrome(4 ));
System.out.println(largestPalindrome(5 ));
System.out.println(largestPalindrome(6 ));
}
} - 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)
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) "aa" ;
String pattern = "a" ;
System.out.println(isMatch(str, pattern));
str = "aa" ;
pattern = "*" ;
System.out.println(isMatch(str, pattern));
str = "cb" ;
pattern = "?a" ;
System.out.println(isMatch(str, pattern));
str = "adceb" ;
pattern = "a???b" ;
System.out.println(isMatch(str, pattern));
str = "adceb" ;
pattern = "*a*b" ;
System.out.println(isMatch(str, pattern));
}
} - 어떤 String str에 대해 str.length() = 0과 str = null 은 다르다.
- "" 와 null의 차이는?
->"": 실제 문자열이지만 비어있는 문자열(str = "")이다., null은 String 변수가 아무것도 가리키지 않는다.
-> ""는 실제 문자열이므로 String의 length()같은 메서드를 호출 가능, null은 불가능하다.