[백준/c++] 13144번: List of Unique Numbers

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

13144번: List of Unique Numbers

 

문제 요약

 

길이가 N인 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수 구하라

 

범위

 

수열의 길이 N (1 ≤ N ≤ 100,000)

수열 내 수 (1 이상 100,000 이하)

 

 

 

---

 

우선, 문제를 잘 읽어보면 키워드가 보인다. 연속한, 1개 이상의 수

→ 연속된 수만 뽑는다. 연속하지 않은 수들은 뽑지 않는다. 즉, 양 옆으로 연결된 수들만 뽑는다는 것이다. 또한 1개 이상의 수를 뽑는다고 했으니 하나를 뽑는 것도 포함된다는 것이다.

 

1. 범위 지정 (L~R)
   
   
2. 중복 있는지 체크 
   
   → Bool 타입 배열 check []를 통해 중복을 체크한다.

 

L을 고정시키고 R를 뒤로 옮기면서 중복을 체크했다. R이 가리키는 원소를 check []의 인덱스로 넣어서 중복을 체크한다. 

• check[a[R+1]] == false 라면 ++R (여기서 꼭 check 배열을 true로 바꿔준다 → 이 값이 또 나오면 중복임)
  
  
• check[a[R+1]] == true 라면 중복이므로 빠져나온다. (더 이상 뒤로 이동할 필요가 없음)

 

R의 값을 이동하는 while문에서 카운팅을 하는 것이 아니라 L과 R을 이용해 해당 범위 내의 카운팅 개수를 계산할 수 있다.

 

  1  2  3  1  2
  L     R

//(1 2), (1 2 3), (2 3)

//R-L+1 = 3-1+1 = 3

 

그 후, L을 다음으로 이동시키기 전에 꼭 초기화(false)를 시켜준다. 연속 수의 범위를 옮기는 것이므로 중복을 나타낸 배열의 값을 초기화해줘야 한다. 

 

 

---

 

 

[전체 코드]

#include <iostream>
using namespace std;
int n, a[100002];
bool check[100002];

void input(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
}

void solution(){
    int R = 0;
    long ans = 0;
    for(int L = 1; L <= n; L++){
        while(R+1<=n && !check[a[R+1]]){ //R이 범위내에 있고 중복된 값이 아니라면
            check[a[++R]] = true; //다음으로 넘어가고 해당 원소값 체크
        }
        ans += R - L + 1; //카운팅 값
        check[a[L]] = false; //초기화
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

거의 다 풀었지만 굉장히 헷갈린 문제였다. R의 범위를 생각하는게 항상 어렵다. 더 많은 연습이 필요하다.

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!