Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- Java
- 알고리즘
- 완탐
- 그리디
- SWEA
- 다익스트라
- 완전탐색
- database
- 백준
- BFS
- 코딩테스트실력진단
- JPA
- 부분수열의합2
- 트러블슈팅
- 코드트리
- 자바
- 유니온파인드
- 싸피
- JUnit
- 그래프
- DP
- DFS
- SSAFY
- 다시보기
- 코딩테스트
- 기본유형
- Union Find
- Spring
- 알고리즘기본개념
- 코테
Archives
- Today
- Total
HwangHub
배열을 다룰 때 인풋 범위가 음수 포함이라면 본문
자바에서는 인덱스에 음수값이 들어갈 수 없다. 따라서 [-2,5]와 같은 구간은 존재할 수 없다.
하지만 만약 문제에서 -100부터 100까지의 x좌표평면 상에서 여러 구간을 주고 겹치는 구간의 수를 구하라고 한다면 어떨까?
자바 배열에서는 음수 인덱스를 사용할 수 없으니, 이를 양수로 바꿔야 한다. 단순하게 Offset을 음수 범위의 크기만큼 잡아주면 될 것이다.
예를 들어 x좌표평면의 범위가 아래와 같다고 해 보자.
- -100 ≤ x1 < x2 ≤ 100
그렇다면 offset은 100 정도로 주면 모든 x 인덱스가 양수로 올라오게 된다. 이를 이용하여 배열 크기는 200으로 잡고 연산을 수행하면 된다.
+++
만약 겹치는 구간을 찾을 때 각 구간의 끝 점에서 닿는 것도 겹치는 것으로 간주한다면 stream 기준 IntStream.rangeClosed(a,b) ... 을 사용하고, 끝 점이 닿는 것은 겹치는 것으로 간주하지 않는다면 stream기준 IntStream.range(a,b) ... 을 사용하면 된다.
'CS-STUDY > 자료구조 & 알고리즘' 카테고리의 다른 글
시간복잡도 (0) | 2023.07.21 |
---|---|
코딩테스트 시작 전 유형 익히기 (0) | 2023.07.11 |
[그래프] 인접 행렬, 인접 리스트 (스크랩) (0) | 2023.07.11 |
시뮬레이션 : 시간/날짜 (0) | 2023.07.05 |
BFS와 DFS (0) | 2023.05.19 |
Comments