[伯俊]#13144 Unique Numbersリスト
10146 ワード
質問する
長さNの数列が与えられると、数列から1つ以上の連続する数列が抽出され、同じ数列が複数回現れると、その数列を解くプログラムが作成される.
入力
第1行は、数列の長さNを与える.(1 ≤ N ≤ 100,000)
2行目には、数列を表すN個の整数が与えられる.数列に表示される数字はいずれも1以上100000以下です.
しゅつりょく
条件を満たす数を出力します.
入力例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
に答える
この問題は二重ポインタで解くことができる.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String[] input = br.readLine().split(" ");
int[] arr = new int[N];
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(input[i]);
}
long ans = 0;
HashSet<Integer> visited = new HashSet<>(); //숫자 체크할 해쉬셋
int left = 0;
int right = 0;
while(true) {
if(right==N) {
if(left==N) break;
else {
ans += (right-left);
left++;
}
}
else if(!visited.contains(arr[right])) { //포함안된 숫자면 포인터 늘림
visited.add(arr[right]);
right++;
}
else {
ans += (right-left); //이미 포함된 숫자면 다 더해주고 시작 idx 늘림
visited.remove(arr[left]);
left++;
}
}
System.out.println(ans);
}
}
Reference
この問題について([伯俊]#13144 Unique Numbersリスト), 我々は、より多くの情報をここで見つけました https://velog.io/@pss407/백준13144-List-of-Unique-Numbersテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol