백준 6503번 풀이 : 망가진 키보드 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/6503

6503번: 망가진 키보드

 

❓  문 제

상근이의 키보드가 망가졌다. 키보드의 일부 키는 작동을 해서 아직 입력을 할 수 있다. 상근이는 키보드의 레이아웃을 바꿔서 단어를 입력하려고 한다. 지금 키보드에서 작동하는 키의 개수는 m개이다.

상근이가 입력하려고 하는 문장이 주어졌을 때, 키보드의 레이아웃을 바꾸지 않고 입력할 수 있는 연속하는 문자의 최댓값을 구하는 프로그램을 작성하시오. 키보드의 한 키는 문자 하나에 매핑되고, 다른 키와 조합을 이용해서 문자를 입력할 수는 없다. 즉, 최대 m개의 서로 다른 문자로 이루어진 가장 긴 부분 문자열을 찾으면 된다.

 

✏️  입 력

상근이의 키보드가 망가졌다. 키보드의 일부 키는 작동을 해서 아직 입력을 할 수 있다. 상근이는 키보드의 레이아웃을 바꿔서 단어를 입력하려고 한다. 지금 키보드에서 작동하는 키의 개수는 m개이다.

상근이가 입력하려고 하는 문장이 주어졌을 때, 키보드의 레이아웃을 바꾸지 않고 입력할 수 있는 연속하는 문자의 최댓값을 구하는 프로그램을 작성하시오. 키보드의 한 키는 문자 하나에 매핑되고, 다른 키와 조합을 이용해서 문자를 입력할 수는 없다. 즉, 최대 m개의 서로 다른 문자로 이루어진 가장 긴 부분 문자열을 찾으면 된다.

 

💻  출 력

각 테스트 케이스에 대해서 최대 m개의 서로 다른 문자로 이루어진 가장 긴 부분 문자열의 길이를 출력한다.

 

❗️ 예 제

 

---

💡 문제 풀이

• 양쪽 구간에서 사용된 문자 갯수의 합을 구한다.
• 투포인터 알고리즘을 사용
  • cnt 를 사용된 문자의 갯수로 가정한다.
    • cnt < n  : 포인터 사이의 문자 갯수가 입력값보다 작을 때
    • cnt > n : 포인터 사이의 문자 갯수가 입력값보다 많을 때

 

아래의 Mississ의 배열이 있으며 n = 1 이라고 가정해 보자

시작의 cnt는 0이고 n = 1 이기 때문에 cnt < n 조건에 성립한다. 

따라서 투 포인터의 조건에 따라 right를 1 증가시킨다.

 

right가 가르키고 있는 곳의 check 값을 1 증가시켜준다.

여기서 check 배열은 해당 알파벳이 한번 사용 했는지 안했는지를 판단하는 배열이다.

따라서 M 에 대한 배열값은 0에서 1로 증가되고 cnt도 1이 증가된다.

 

right를 증가시켰을 때는 수를 더했다면 left를 증가시켜주면

선택된 값에 대한 배열값을 1을 빼준 후 만일 뺀 이후의 값이 0이 되면 

cnt 에서도 1을 빼준다.

 

여러번 진행하다보면 아래와 같은 상황이 나오게 된다.

이때 s에 대한 배열값은 이전에 1이 증가된 상황이므로 cnt는 증가되지 않은 상태로 

right 가 증가하게 된다.

 

여기에 해당하는 조건이 아래의 풀이 코드 중 else if 문이다.

 

또한 여기서 바로 종료하지 않는 이유는 문자열 뒤에 답이 될 수 있는 경우의 수가 더 있기 때문에

종료 조건은 문자열을 끝까지 탐색했을 때 종료 하여야 한다.

 

⌨️  풀이 코드

package develope;

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(true){
            int n = sc.nextInt();
            if(n == 0) break;
            sc.nextLine();
            String str = sc.nextLine();

            int[] check = new int[128];
            int right = -1, left = -1, cnt = 0, max = 0;

            // left : 시작포인터
            // right : 끝포인터
            // n : 입력값
            // cnt : 문자 갯수
            while(left <= right){
                // 포인터 사이의 문자 갯수가 입력값보다 작을 때
                if(cnt < n){
                    // 우측 포인터 증가
                    right++;

                    // 우측 포인터가 증가하고 해당 포인터의 값을 확인해 봤을 때 
                    // 처음보는 값이면 cnt를 증가 시킨다. 한번 더 보는 값이면 그대로 진행
                    check[str.charAt(right)]++;
                    if(check[str.charAt(right)] == 1)
                        cnt++;
                }

                // 문제의 핵심 부분
                // cnt가 이미 n개이지만 다음에 올 문자열이 이미 사용된 문자열이면 
                // 한개를 더 추가할 수 있다.
                else if(cnt == n && check[str.charAt(right + 1)] > 0){
                    right++;
                    check[str.charAt(right)]++;
                }
                    
                // 포인터 사이의 문자 갯수가 입력값보다 더 많을 때
                else{
                    // 좌측 포인터 증가
                    // 좌측 포인터를 증가시켜 문자 갯수를 줄인다.
                    left++;

                    // 좌측 포인터가 증가하면 증가한 포인터가 가르키는 곳의 값을 확인해 봤을때
                    // 0이면 더이상 카운트 하지 않는 것이기 때문에 cnt를 줄인다.
                    check[str.charAt(left)]--;
                    if(check[str.charAt(left)] == 0)
                        cnt--;
                }

                max = Math.max(right - left, max);

                // 종료 조건을 변경
                if(right == str.length() - 1)
                    break;
                // else{
                //     System.out.println(cnt);
                //     break;
                // }
            }
            System.out.println(max);
        }
    }
}

 

✅ 비고

처음에 종료 조건을 else 문 즉 입력 받은 n과 문자열의 갯수인 cnt가 동일 할 때라는 조건으로 종료를 했다.

하지만 해당 조건으로 종료하게 되면 입력받은 수와 동일한 수가 계속해서 리턴되게 되며 

종료된 구간 외에 정답 구간이 따로 있음에도 불구하고 종료되게 되었다.

 

해당 문제의 요점은 투포인터 알고리즘을 이해하고 있는지와 종료 구간, 그리고 투포인터 내에서도 문제에 해당하는 조건

즉 다음에 올 문자가 현재 한번 사용했던 문자인가 이 부분을 조건으로 넣으면 해결할 수 있는 문제다.