패스트캠퍼스 챌린지 27일차

투 포인터 응용

List of Unique Numbers (BOJ 13144) 난이도 4

- 수열에서 연속한 1개 이상의 수를 뽑았을 떄 같은 수가 여러번 등장하지 않는 경우의 수

 

정답의 최대치

 

 

구현

static int N;
static int[] A, cnt;
    
static void pro() {
	long ans = 0;

    for (int L=1, R=0; L<=N; L++){  // L 마다 R 을 최대한 옮겨 줄 계획이다.
    // R 을 옮길 수 있는 만큼 옮긴다.
    while (R + 1 <= N && cnt[A[R+1]] == 0){
    	R++;
        cnt[A[R]]++;
    }
            
    // 정답을 갱신한다
    ans += R - L + 1;

    // L 을 옮겨주면서 A[L] 의 개수를 감소시킨다.
    cnt[A[L]]--;
    }

    System.out.println(ans);
}

 

고냥이 BOJ 16742

- 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다.

- 인식할 수 있는 최대 문자열의 길이는 얼마일지가 궁금하다

 

 • 정답의 최대치

  - N이 26이라면 문자열 전체를 인식하므로, 최대 길이 10만이 정답이다.

 

R : 인식하고 싶은 구간의 오른쪽 끝

L : 인식 가능한 가장 왼쪽 위치

 

구현

static int N, kind;
static String A;
static int[] cnt;

static void add(char x) {  // x 라는 알파벳 추가
	cnt[x - 'a']++;
	if (cnt[x - 'a'] == 1)  // 새롭게 나타난 알파벳이라는 뜻
	kind++;
}

static void erase(char x) {  // x 라는 알파벳 제거
	cnt[x - 'a']--;
	if (cnt[x - 'a'] == 0)  // 인식해야 하는 알파벳에서 빠지는 순간
	kind--;
}

static void pro() {
	len = A.length(), ans = 0;
	for (int R = 0, L = 0; R < len; R++) {
		// R 번째 문자를 오른쪽에 추가
		add(A.charAt(R));

		// 불가능하면, 가능할 때까지 L을 이동
		while (kind > N) {
			erase(A.charAt(L++));
		}

		// 정답 갱신
		ans = Math.max(ans, R - L + 1);
	}
	System.out.println(ans);
}

시간 복잡도 : O(N)

 

 

 

 

 

 

 

 

 

 

 

27일차 인증

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]