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
- database
- 코테
- JUnit
- 백준
- 코드트리
- SSAFY
- 다시보기
- 코딩테스트
- JPA
- 코딩테스트실력진단
- 알고리즘기본개념
- BFS
- 유니온파인드
- 알고리즘
- 자바
- 싸피
- Union Find
- 그리디
- 완전탐색
- Java
- 기본유형
- DFS
- 그래프
- Spring
- 트러블슈팅
- 부분수열의합2
- SWEA
- 완탐
- 다익스트라
- DP
Archives
- Today
- Total
HwangHub
[Java/투포인터] 코드트리. 겹치는 숫자가 없는 최대 구간 본문
🤔 Intuition
투포인터를 아직도 제대로 못 하는 것 같아서 트레이닝을 위해 개념 문제를 풀었다.
투포인터 문제인지 알고 접근했다.
🔎 Algorithm & Complexity
* @algorithm two pointer
* @time O(N) : 선형탐색
* @memory O(N + R) : 주어지는 숫자 개수 N + 주어지는 숫자 범위 R
👨🏻💻 Logic
- 입력되는 숫자 배열을 운영함과 동시에, 숫자들의 등장 횟수를 저장하는 count array를 운영하면 투포인터를 진행하는 과정에서 숫자의 중복 여부 또는 숫자의 등장 횟수를 O(1)로 관리할 수 있다.
- 이를 이용하여 투포인터를 운영하면 된다.
public class Main {
private static int N;
private static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int[] counting = new int[100001];
int right = 0; // right pointer init
int ans = 0;
for (int left = 0; left < N; left++) { // left pointer
while (right < N) {
int num = arr[right];
if (counting[num] == 1) {
break;
}
counting[num]++;
right++;
}
ans = Math.max(ans, right - left);
int pop = arr[left];
counting[pop]--;
}
System.out.println(ans);
}
}
위 로직을 투포인터 템플릿에 맞게 맞춰서 좀 더 명료하고 깔끔하게 바꾸면 아래와 같이 될 수 있다.
import java.util.*;
import java.io.*;
public class Main {
private static int N;
private static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int[] counting = new int[100001];
int right = -1; // right pointer init (right + 1이 0번 인덱스부터 바라봐야 하므로 -1로 초기화)
int ans = 0;
for (int left = 0; left < N; left++) { // left pointer
while (right + 1 < N && counting[arr[right+1]] != 1) {
counting[arr[right + 1]]++;
right++;
}
ans = Math.max(ans, right - left + 1);
counting[arr[left]]--;
}
System.out.println(ans);
}
}
'workspace > 알고리즘' 카테고리의 다른 글
[Java/백트래킹] 백준 2239. 스도쿠 (0) | 2024.03.27 |
---|---|
[Java/투포인터] 백준 2482. 색상환 (1) | 2024.03.27 |
[Java/Topological Sort] 백준 2252. 줄세우기 (0) | 2024.03.22 |
[Java/다익스트라] 백준 13549. 숨바꼭질3 (0) | 2024.03.21 |
[Java/Map] 코드트리. 두 수의 합 (0) | 2024.03.20 |
Comments