[백준 - 13144][GOLD 4][해설 X] - List of Unique Numbers (JAVA)

 

문제 링크

---

https://www.acmicpc.net/problem/13144

 

문제

---

유니스트 컴퓨터공학과에 다니는 서윤이는 이번에 어떤 과목을 들을지 고민중이다. 학점을 잘 받을 수 있으면서도 중요한 과목을 듣고 싶은 서윤이는 모든 과목의 중요도와, 일정 이상의 학점을 받기 위해 필요한 공부시간을 다 적었다.

처음에는 모든 과목을 들으려고 했던 서윤이는 자신의 공부 시간에 한계가 있다는 것을 깨달았다. 그래서, 공부 시간의 한계를 초과하지 않으면서 과목의 중요도 합이 최대가 되도록 몇 개만 선택하여 수강하기로 마음먹었다.

중요도가 최대가 되도록 과목을 선택했을 때, 최대가 되는 중요도를 출력하는 프로그램을 작성하시오.

 

입력

---

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

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

 

출력

---

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

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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());
        int[]num = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
        //윈도우(l~r 사이) 안에 있는 숫자 목록
        Set<Integer> set = new HashSet<>();

        int l = 0;
        int r = 0;
        long count = 0;

        while(r < num.length){
        	//중복되는 숫자가 있다면 왼쪽 범위를 오른쪽으로 좁힌다
            while(set.contains(num[r])){
                set.remove(num[l]);
                l++;
            }

            set.add(num[r]);
			
            //num[r]을 이용해서 만들 수 있는 경우의 수는 {num[l]} ,{num[l],num[l+1]} .. {num[l],num[l+1] ... num[r-1],num[r]}
            //즉 l~r의 길이만큼 만들 수 있다.
            count = count + r - l + 1;
            r++;
        }

        System.out.println(count);
    }
}

 

 

실행 결과

---

 

팁

---

• 항상 최대개수는 int형인지 long형인지 생각하자.
• 연속한 수의 범위는 슬라이딩 윈도우가 좋다.