[백준] 알고리즘 분류(두 포인터,JAVA)13144번, List of Unique Numbers

문제 링크

13144번: List of Unique Numbers

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 길이가 N인 수열이 존재합니다.

2. 수열에서 연속한 값을 1개이상 뽑을 때 같은 값을 가지지 않는 모든 경우의 개수를 결과로 출력합니다.

3. 메모리 제한 32MB!!!!, 결과값은 int 형의 범위를 벗어납니다!!!!

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 수열을 순차적으로 탐색하며, 중복된 값이 발생하였을 때 이전의 연속한 경우를 구합니다.

 

3. 탐색이 끝났을 때 모든 경우의 수를 결과로 출력합니다.

 

연속한 값 탐색

 

방문했던 값을 확인하기 위해서  HashSet<Integer>()를 사용하였습니다.

 

 

수열을 순차적으로 중복된 값을 만나기까지 탐색합니다.

 

중복된 값을 만나면 이전에 해당 값을 만났을 때까지 연속된 모든 경우를 구합니다.

 

예를 들어

 

수열 : 1 3 5 1

 

1 3 5 `1`

`1`이라는 중복된 값 확인!

 

현재 연속된 수에서 1을 만나지 않을 때까지 시작값 땡기기!

 

`1` 3 5 1

 

`1`에서 나올 수 있는 모든 경우는

 

1

 

1 3

 

1 3 5

 

간단한 규칙을 발견할 수 있습니다.

 

1	3	5	1
0	1	2	3

 

`1`에서 나올 수 있는 경우는 `1`까지의 길이입니다.

`1`(3) - `1`(0) = 3개

 

수열에 끝까지 위 과정을 통해 탐색합니다.

 

수열에 끝에 도착하였을 때에는

 

현재 연속된 수의 시작값부터 선택할 수 있는 모든 경우를 더합니다.

 

모든 경우의 개수 :  시작값 ~ 수열 끝의 길이

 

예제입력 2.

1. 입력된 정보를 저장합니다.

 

N : 5

 

{1, 2, 3, 1, 2};

 

2. 수열을 순차적으로 탐색하며, 중복된 값이 발생하였을 때 이전의 연속한 경우를 구합니다.

 

1	2	3	1	2
0	1	2	3	4

 

순차적으로 중복된 값이 발생하지 않을 때까지 탐색!

 

1	2	3	1	2
0	1	2	3	4

 

중복된 값 발생!!

 

이전에 해당 값을 만났을 때까지 연속된 모든 경우 구하기!!

 

1	2	3	1	2
0	1	2	3	4

 

`1`(3) - `1`(0) : 3개

 

 

순차적으로 중복된 값이 발생하지 않을 때까지 탐색!

 

1	2	3	1	2
0	1	2	3	4

 

중복된 값 발생!!

 

이전에 해당 값을 만났을 때까지 연속된 모든 경우 구하기!!

1	2	3	1	2
0	1	2	3	4

 

 

`2`(4) - `2`(1) : 3개

 

순차적으로 중복된 값이 발생하지 않을 때까지 탐색!

 

1	2	3	1	2
0	1	2	3	4

 

수열에 끝에 도착!!

 

현재 연속된 수의 시작값부터 선택할 수 있는 모든 경우를 더합니다.

 

3(2) : 4(수열 끝) - 2  + 1 = 3개

 

1(3) : 4(수열 끝) - 3 + 1 = 2개

 

2(4) : 4(수열 끝) - 4  + 1 = 1개

 

3. 탐색이 끝났을 때 모든 경우의 수를 결과로 출력합니다.

 

모든 경우의 수 : 3(`1`) + 3(`2`) + 3(`3`) + 2(`1`) + 1(`2`) = 12

 

12결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 수열의 숫자들을 띄어쓰기 기준 나누었습니다.
• 수열을 순차적으로 탐색하며, 중복된 값이 찾았을 때 시작 Index 땡기기 진행합니다.
• 수열을 끝에 도착했을 때 현재 시작 Index를 기준으로 모든 경우 탐색합니다.
• 탐색이 종료되었을 때 조건에 만족하는 모든 경우의 개수를 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

 

결과코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] arr = new int[N];	//수열 저장 배열
        HashSet<Integer> set = new HashSet<>();	//중복 방문 확인 HashSet<>()
        long result = 0;
        //입력값 저장!!
        for(int i=0;i<N;i++)
            arr[i] = Integer.parseInt(st.nextToken());

        int start = 0;	//연속된 수 시작 Index 변수
        //수열 순차적으로 탐색!
        for(int i=0;i<N;i++){
            if(set.contains(arr[i])){		//중복된 수 탐색!
                //중복된 값이 없어질 때까지 땡기기!
                for(int j=start;j<i;j++){
                    result += i-j;	//땡겨져서 떨어지는 값 모든 경우 더하기!
                    start++;		//시작 Index 증가
                    if(arr[j] == arr[i])	//중복된값 찾았을 때
                        break;
                    set.remove(arr[j]);	//떨어진 값 미방문으로 변경
                }
            }else		//중복된 값이 아닐 때
                set.add(arr[i]);
        }
        //수열에 끝에 도착했을 때 현재 시작값 기준 모든 경우 구하기!
        for(int i=start;i<N;i++)
            result += N-i;	//N - i : 시작값 ~ 수열의 끝의 길이
        
        bw.write(String.valueOf(result));	//모든 경우 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();

    }
}