백준 13144 c++, java 풀이

문제

길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다. 수열에 나타나는 수는 모두 1 이상 100,000 이하이다.

출력

조건을 만족하는 경우의 수를 출력한다.

예제 입력 1 복사

5
1 2 3 4 5

예제 출력 1 복사

15

예제 입력 2 복사

5
1 2 3 1 2

예제 출력 2 복사

12

예제 입력 3 복사

5
1 1 1 1 1

예제 출력 3 복사

5

 

 

이 문제는 투포인터 알고리즘을 사용한다.

 

문제의 로직

1.  수열들을 모두 입력 받는다.

2. 투포인터의 원점 start end를 선언해 준다.

3. 하나의 start에서 end를 ++ 하면서 올려준다.

4. 같은 숫자를 마주치지 않으면 계속해서 end++를 해준다.

5. 같은 숫자를 마주치면 break를 해준다.

6. res += end - start를 통해서 중복된 수 없이 진행된 값을 구해준다.

7. start가 하나 올라가기 때문에 visited[arr[start]]를 0으로 바꿔준다.

8. 반복한다.

9. 최종적으로 res값을 출력한다.

 

특이한 점

1. c++에서 문제를 푸는데 main 함수밖에 visited[] 배열을 선언한것과 main 함수안에서 visited를 선언한 차이밖에 없는데 오답과 정답으로 나뉘었다. 왜 그런지 찾아보니 main 함수 밖에서 visited를 선언하면 자동으로 visited 배열이 0으로 채워지지만 main 함수 안에서 visited를 선언하면 자동으로 0이 채워지지 않고 쓰레기값으로 채워진다고 한다... 로직을 모두 맞게 짰는데 에러가 나면 이런걸 확인해보자. 만약에 어쩔 수 없이 main 함수안에 배열을 선언하게 되면 memset을 통해서 꼭 배열을 초기화 하자.

 

 

 

- c++

#include<bits/stdc++.h>
using namespace std;


int n;

long long int res;
int visited[100001];

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    vector<int>arr(n);


    for(int i =0; i < n ;i++){cin >> arr[i];}

    int end = 0;
    for(int start = 0 ; start < n ; start++){
        while(end < n){
            if(visited[arr[end]])break;
            visited[arr[end]]=1;
            end++;
        }
        res += (end - start);
        visited[arr[start]]=0;
    }
    cout << res <<"\n";

    return 0;

}

 

 

- java

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


public class Main {



    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int [] arr = new int[100001];
        int [] visited = new int [100001];

        StringTokenizer st = new StringTokenizer(br.readLine());

        int arrindex=0;

        while(st.hasMoreTokens()){
            arr[arrindex]= Integer.parseInt(st.nextToken());
            arrindex++;
        }

        int end = 0;
        long res = 0;

        for (int i = 0; i < n ; i++) {
            while(end<n){
                if(visited[arr[end]]==1)break;
                visited[arr[end]]=1;
                end++;
            }
            res+=(end-i);
            visited[arr[i]]=0;
        }

        System.out.println(res);



    }
}