1. 문제
- 배열에서 뒷 요소와 앞 요소를 뺐을 때 가장 차이가 큰 값을 구하여라
2. 시도
배열에서 min과 max를 각각 구해 max-min을 하면 될 것 같았다. 주의할 부분으로는 max가 min보다 앞에 있을 수 있기에 인덱스 위치 파악을 해야할 듯하다.
class Solution {
public int maxProfit(int[] prices) {
int min = prices[0];
int max = 0;
int index = 0;
for (int i=0; i< prices.length; i++) {
if (min > prices[i]) {
min = prices[i];
index = i;
}
}
System.out.println("min = " + min);
System.out.println("index = " + index);
for (int i=index; i<prices.length; i++) {
if (max < prices[i]) {
max = prices[i];
}
}
System.out.println("max = " + max);
return max-min;
}
}
일부 테스트 케이스를 통과하며 방향은 맞아 보였다. 그러나 무작정 최솟값만 찾다 보니 큰 수가 앞에 있고 작은 수가 맨 뒤에 있는 경우는 에러였다.
3. 개선
컴퓨터로 코드를 쳐보는 것도 좋지만 가끔 생각이 안될 때 손으로 코드를 써보기도 한다. 최솟값을 찾는 것은 좋다 생각했기에 찾은 최솟값을 각 요소에서 빼보는 것을 시도해봤다.
class Solution {
public int maxProfit(int[] prices) {
int min = prices[0];
int max = 0;
System.out.println("1 min = " + min);
System.out.println("1 max = " + max);
for (int i=1; i<prices.length; i++) {
if (min > prices[i]) {
min = prices[i];
System.out.println("2 min = " + min);
} else if (prices[i] - min > max) {
System.out.println("prices[i] = " + prices[i]);
System.out.println("3 min = " + min);
max = prices[i] - min;
System.out.println("2 max = " + prices[i] + " - " + min + " = " + max);
}
System.out.println("4 min = " + min);
}
System.out.println("3 max = " + max);
return max;
}
}
'자바 알고리즘' 카테고리의 다른 글
[leetcode - Java] 167. Two Sum II - Input Array Is Sorted (0) | 2023.08.26 |
---|---|
[leetcode - Java] 125. Valid Palindrome (0) | 2023.08.26 |
[leetcode - Java] 189. Rotate Array (0) | 2023.08.24 |
[leetcode - Java] 169. Majority Element (0) | 2023.08.24 |
[leetcode - Java] 80. Remove Duplicates from Sorted Array II (0) | 2023.08.24 |