[BOJ]1059 좋은구간(S4, C++)

📋 개요

이번 문제도 풀면서 살짝 해매다가 2시간이 넘어버렸지만, 거의 답에 가까워졌다. 문제는 그리 어렵지 않았다. 좋은 구간의 조건을 알고 있다면 풀기 쉬운 문제다.

 

 

---

🧩 문제

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

1059번: 좋은 구간

📝  형식 

📥 입력	📤 출력
첫째 줄에 집합 S의 크기 L이 주어진다. 둘째 줄에는 집합에 포함된 정수가 주어진다. 셋째 줄에는 n이 주어진다.	첫째 줄에 n을 포함하는 좋은 구간의 개수를 출력한다.

💡  예제

🔢 번호	📥 입력	📤 출력
1	4 1 7 14 10 2	4
2	5 4 8 13 24 30 10	5
3	5 10 20 30 40 50 30	0
4	8 3 7 12 18 25 100 33 1000 59	1065

 

🥲  정답코드

---

📖  해설 및 느낀점

#해설

"좋은 구간"은 두가지 조건이 있다.

 

- A<B- A<= X <= B를 만족하는 정수X가 S집합에 속하지 않는다.

 

두번째 조건과 예제3을 보면 n이 S집합안에 포함되어있으면 좋은 구간은 없다. 왜일까?

 

n이 S집합에 포함되어있는 30이라면, 30이 포함된 "좋은 구간"은 찾을 수가 없다. 2번째 조건인 S집합에 속하지 않는다.라는 조건 때문이다. 그렇기 때문에 S에 n을 포함하면 0이 된다. 그게 첫번째 예외이다.  

 

이제 예외처리를 했으니 "좋은 구간"을 찾아보자. n이 포함된 "좋은구간"을 찾기 위해서는 S집합에 n을 넣어서 찾으면 된다.

 

먼저 vector에 넣어 오름차순으로 정렬을 하고, n의 index를 기준으로 앞뒤에 있는 값을 찾는다.

  if(S[i] ==n){
            s = S[i-1]; //앞
            e = S[i+1]; //뒤
}

 

그리고 찾았으면 "좋은구간"의 두번째 조건인 S집합에 포함되지 않게 시작점과 마지막 점을 조정한다.

 

시작점은 찾은 앞의 값에 +1, 끝점은 찾은 뒤의 값에 -1을 해서 2번째 조건에 위배되지 않도록 하여 for문을 돌린다.여기서 유의해야할점은 시작점과 끝점이 같다면 무시해야한다. 그리고 for문에서 시작점과 끝점을 for문으로 돌릴때 n을 마지막과, 시작으로 하여 n을 기준으로 구간을 설정하면 된다.

    for(int i = s+1 ; i <= n ; i ++){
        for(int j = n ; j <= e-1; j++ ){
            if(i ==j) continue;
            cnt++;
        }
    }

 

#느낀점

아이디어적인 요소들이 많이 필요한 문제였다. 중간에 n을 넣어서 정렬하는것도 그렇고 범위가 1000이기때문에 수직선위에 1000을 그려놓고 하는 것도 그려놓고 남은 값들을 찾는 것도 해서 고민을 많이 해야할 문제였던 것 같다.

 

아이디어가 쉽게 떠오른다면 빨리 풀겠지만, 아니라면 빨리 솔루션을 작성할 수 없을거 같다.