무엇을 하든지 꾸준함이 중요한 것 같다.
그래서 필자는 leetcode를 시간이 날 때 마다 열심히 풀려고 한다.
이곳의 좋은점은 매일 매일 문제를 하나씩 제공한다는 사실! (물론 그냥 찾아서 할 수 있는데 그것도 좋고!)
어제와 오늘에 걸쳐서 문제를 풀어봤는데 이에 대해 공부한 내용을 적으려고 한다.
문제를 먼저 풀어보고 싶은 사람들은 위 문제들의 주소를 첨부해 두었으니 풀면 좋다
https://leetcode.com/problems/remove-covered-intervals/
Remove-covered-intervals!
요약을 하자면 이중배열이 존재하는데 이 배열 안의 배열의 길이는 무조건 2이고, 어느 한 배열이 하나의 배열의 범위 안에 들어가면 제거하고 그렇게 남은 배열 성분의 숫자를 출력하는 것이다.
첫번째 예시대로
[[1,4], [3,6], [2,8]]이 있다면, [1,4]는 [3,6]의 안으로 쏙! 들어가지 않는다(그러려고 하면 1이 3보다 크거나 같아야 한다.)
그런데 [3,6]은 [2,8]안에 쏙! 들어간다. 그래서 [3,6]은 제거를 해야한다.
이래서 첫번째 예시의 결과는 2가 되어야 한다.
내가 처음에 잡은 문제 해결 방법은 우선 이중 for문 이었다.
결국에 핵심은 int [][] test = [[1,4], [3,6], [2,8]]의 배열이 존재한다면, test[0]과 test[1], test[0]과 test[2], test[2]과 test[3]을 비교하면서 모든 성분을 돌아야 한다.
처음에는 그래서 이런 코드를 작성했다.
1차 시도...
class Solution {
public int removeCoveredIntervals(int[][] intervals) {
int result = 0;
for(int i = 0; i < intervals[0].length; i++){
int[] prev = intervals[i];
int[] target = intervals[i];
if(prev[0] <= target[0] && prev[1] <= target[1]){
result++;
}
}
return result;
}
}
우선 어떤 성분이 삭제되었는지, 아닌지를 고려하지 않고 카운팅만 하면 된다고 생각했다.
그리고 문제에서 주어진 remove 란 단어도 그렇게 개의치 않았다.
배열의 배열의 성분의 길이는 무조건 2로 고정되어 있고, 착각을 한 것이 한 방향으로만 배열을 세어주면 된다고 생각했다.
주어진 예시와 다르게
int [][] test = [[3,6], [2,8], [1,4]]의 배열이 존재한다면, 첫번째 시작부터 [3,6]은 [2,8]의 안에 쏙! 들어가므로 벌써 [3,6]은 사라져야 한다(사라진다는 말은 더이상 이 배열을 우리가 작업하는데에 고려하지 않겠다는 중요한 의미를 가짐)
그러니까 결과가 오잉... 맞는줄알고 좋아했다...
결과는 역시...
그래서 위의 코드에서 약간 변형을 해서 앞 뒤로 전부 확인할 수 있도록 수정을 했다.
2차 시도...
class Solution {
public int removeCoveredIntervals(int[][] intervals) {
int result = 0;
for(int i = 0; i < intervals.length-1; i++){
int[] prev = intervals[i];
for(int j = i + 1; j <intervals.length; j++){
int[] target = intervals[j];
if(prev[0] <= target[0] && prev[1] <= target[1]){
result++;
}else if(prev[0] >= target[0] && prev[1] >= target[1]){
result++;
}
}
}
return result;
}
}
비교하는 아이들이 한 방향에서만 하는 것이 아니라, 양 방향으로 확인을 하도록 코드를 수정했다.
int [][] test = [[3,6], [2,8], [1,4]] 이라면 test[0]성분이 test[1]성분에 들어가는 것만이 아니라 test[1]도 test[0]안에 들어가게 되면 카운팅을 해서 수를 셌다.
그런데 이것도 틀렸다.
int [][] test = [[3,6], [2,8], [1,4], [5,9], [5,6]]
그 이유는 위와 같은 방식으로 하게 된다면
test[0] => test[1], test[2], test[3], test[4]
test[1] => test[2], test[3], test[4]
test[2] => test[3], test[4]
test[3] => test[4]
하는 방식으로 for문을 돌게되는데 어떤것이 누구안에 쏙! 들어갈지 알고 이렇게 돌린다는것이 문제이다.
그러니까... 전부 확인을 해서 그중에서 포함되는 아이들을 제거해야 하는데 그렇게 될 수 없다는 구조이다.
그러므로 for문을 처리하는 로직에도 수정을 해야하고
또다른 문제는 remove에 주의해야 한다는 점이다. 전에도 언급을 했는데
remove하게 될 성분임이 판명되면 그 친구는 다른 아이들과 비교 자체를 하면 안된다.
그래서 다음과 같은 결과를 도출했다.
3차 시도
class Solution {
public int removeCoveredIntervals(int[][] intervals) {
Map<int[], int[]> map = new HashMap<>();
int result = intervals.length;
int[] target = null;
int[] temp = null;
for(int i = 0; i < intervals.length; i++){
for(int j = 0; j <intervals.length; j++){
if(j == i){
continue;
}
target = intervals[i];
temp = intervals[j];
if(map.containsKey(target) || map.containsKey(temp)){
continue;
}
if(target[0] <= temp[0] && target[1] >= temp[1]){
map.put(temp, temp);
}else if(target[0] >= temp[0] && target[1] <= temp[1]){
map.put(target, target);
}
}
}
return result - map.size();
}
}
배열을 일일이 새로 만들게 되면 매~우 안좋다고 생각을 했다. java에서 배열을 선언하면 call by reference라서 System.out.println으로 출력을 해보면 주소가 나오는것 같다. 그렇다는 말은 일일이 선언할 때 마다 어딘가에서 메모리를 잡아먹고 있다는 것이다!
for문도 같은 성분을때를 제외하고 전부 순회할 수 있도록 작성했다. 말했다시피 어떤 성분이 어디에 포함될 지 모르기 때문이다.
그러므로 map을 이용해서 제외된 성분을 저장해서 혹시 이 차례가 온다면 비교 자체를 안하도록 작성했다.
최종적으로는 저장된 map의 사이즈만큼 제거되었다고 판단하고 처음 배열의 길이에 map의 size를 뺐다.
그런데 여기에 더미 코드가 있는데... target 성분과 temp성분을 비교하는 곳에서 문제가 있다.
좀 전에 전부 다 순회를 한다고 설명을 했다.
그런데 전부 다 순회를 하면 양쪽에서 확인을 할 필요가 없다. 일일이 확인을 해주기 때문에 말이다.
int[][] test = [[1,3],[2,4],[3,6]]이라면
test[0] => test[1], test[2]
test[1] => test[0], test[2]
test[2] => test[0], test[1]
이런 식으로 돌게 될 터인데 굳이 한번 더 뒤에서 확인을 해줘야 하는 것이다. 어짜피 되지도 않을 로직인데 그냥 과감히 삭제를 하면...
최종 결과...
class Solution {
public int removeCoveredIntervals(int[][] intervals) {
Map<int[], int[]> map = new HashMap<>();
int result = intervals.length;
int[] target = null;
int[] temp = null;
for(int i = 0; i < intervals.length; i++){
for(int j = 0; j <intervals.length; j++){
if(j == i){
continue;
}
target = intervals[i];
temp = intervals[j];
if(map.containsKey(target) || map.containsKey(temp)){
continue;
}
if(target[0] <= temp[0] && target[1] >= temp[1]){
map.put(temp, temp);
}
}
}
return result - map.size();
}
}
이렇게 풀이를 완료했다.
과연 성능은 어떨지 궁금한데...
그렇게 썩 좋지는 않다. 약간~ 좋은 정도이고 간신히 문제를 해결한 정도이다.
근데 이것보다 훨씬 좋은 성능으로 푼 사람들의 풀이를 보았는데 뭔가 내꺼랑 좀 비슷한데(무쳤습니까 휴먼...)
class Solution {
public int removeCoveredIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));
int count = 0, cur = 0;
for(int interval[] : intervals){
if(cur < interval[1]){
cur = interval[1];
count++;
}
}
return count;
}
}
대부분 뒤져보니 Arrays.sort를 이용해서 먼저 정렬을 한 다음에
순서대로 counting을 하였다. 그렇게 하면은 뒤죽박죽이라 전부 for문을 돌릴 필요없이 순서대로 확인하는것이 가능한다. 또한, 배열의 배열의 두번째 성분만 고려하면 된다(이미 1차 정렬에서 앞의 성분은 정리가 된...)
'코딩 테스트 > 문제 풀기' 카테고리의 다른 글
| leetcode : 1046. Last Stone Weight (0) | 2022.04.10 |
|---|---|
| Sliding window (0) | 2022.03.20 |
| 1200. Minimum Absolute Difference (0) | 2022.02.26 |