겹치는 선분의 길이 문제풀이
주어진 세 선분의 두 선분 이상 겹치는 부분의 길이를 반환
세 선분이 모두 겹쳐도 겹치는 부분은 한번만 반영된다.
1번선분-2번선분
2번선분-3번선분
1번선분-3번선분
이 겹치는 부분을 구하여 각각 겹치는 부분의 길이를 더한 후
세 선분이 모두 겹치는 부분의 길이를 빼준다...
public int solution(int[][] lines) {
int answer = 0;
List<HashSet<Integer>>lineList = new ArrayList<HashSet<Integer>>();
List<HashSet<Integer>>tempLineList = new ArrayList<HashSet<Integer>>();
for (int i = 0; i < lines.length; i++) {
HashSet<Integer> line = new HashSet<Integer>();
HashSet<Integer> tempLine = new HashSet<Integer>();
for (int j = lines[i][0]; j < lines[i][1]+1; j++) {
line.add(j);
tempLine.add(j);
}
lineList.add(line);
tempLineList.add(tempLine);
}
tempLineList.get(0).retainAll(lineList.get(1));
answer=(tempLineList.get(0).size()<2)?answer:answer+tempLineList.get(0).size()-1;
tempLineList.get(1).retainAll(lineList.get(2));
answer=(tempLineList.get(1).size()<2)?answer:answer+tempLineList.get(1).size()-1;
tempLineList.get(2).retainAll(lineList.get(0));
answer=(tempLineList.get(2).size()<2)?answer:answer+tempLineList.get(2).size()-1;
tempLineList.get(0).retainAll(tempLineList.get(1));
tempLineList.get(1).retainAll(tempLineList.get(2));
answer=(tempLineList.get(0).size()<2)?answer:answer-tempLineList.get(0).size()+1;
answer=(tempLineList.get(1).size()<2)?answer:answer-tempLineList.get(1).size()+1;
return answer;
}
lineList에 한 선분이 지나는 점을 가진 Set을 추가하고 추가한대로 1번 선분, 2번 선분, 3번 선분으로 부르기로한다.
ArrayList가 아닌 Set을 사용한 이유는 중복을 허용하지 않는 Set의 retainAll 함수를 사용해 차집합을 구하기 위해서이다.
++집합 메서드
addAll() : 인자로 받은 set과의 합집합으로 변경 후 성공시 true 반환
retainAll() : 인자로 받은 set과의 교집합으로 변경 후 성공시 true 반환
removeAll() : 인자로 받은 set과의 차집합으로 변경 후 성공시 true 반환
containsAll() : 인자로 받은 set을 부분집합으로 가진다면 true 반환
집합 메서드는 기존 집합을 인자로 받은 집합과 비교해 처리하고 기존 집합을 변경해주고 논리값을 반환해준다.
tempLineList를 만든 이유는 라인끼리 겹치는 부분을 비교할때마다 LineList가 변경되기 때문에 다음 비교때 문제가 생기기 때문이다.
tempLineList.get(0)에는 0번과 1번 선분이 겹치는 부분을 집합으로 가지고
tempLineList.get(1)에는 1번과 2번 선분이 겹치는 부분을 집합으로 가지고
tempLineList.get(2)에는 2번과 0번 선분이 겹치는 부분을 집합으로 갖는다.
만약 집합이 원소를 하나만 갖는다면 한 점만 겹치고(만나고) 겹치는 부분의 길이를 갖지 못하기 때문에
정답 answer를 계산할때 추가하면 안된다.
그래서 size가 2이상일때만 answer 연산을 한다.
세 선분이 겹치는 부분들 중 다시 겹치는 부분을 구할 때는 2번만 연산하면 되기 때문에
겹치는 부분을 계산할때 기준 집합이 변형되도 상관없다.
0번과 1번 선분이 겹치는 부분의 집합과 1번과 2번 선분이 겹치는 부분의 집합의 교집합 ,
1번과 2번 선분이 겹치는 부분의 집합과 2번과 0번 선분이 겹치는 부분의 집합의 교집합을
구해 answer에서 빼준다.
다른 사람의 풀이 중 map을 이용
public int solution2(int[][] lines) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < lines.length; i++) {
for (int j = lines[i]]0]; j < lines[i][1]; j++) {
map.put(j, map.getOrDefault(j, 0) + 1);
}
}
int answer = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() >= 2) {
answer++;
}
}
return answer;
}
map에 각 선분의 시작점부터 끝점까지 지나가는 점을 key로 하여 중복되는 개수를 구한다.
만약 2번이상 중복되면 answer를 증가시킨다.
하나의 키값을 갖는 점이 3번 중복되더라도 answer는 한번만 증가하기 때문에 계산이 쉽다.