Baekjoon 1059 수2 JAVA

최근에 백준 등급 문제를 알게 되어 실버 5등급의 문제를 푸는 중인데 해당 문제를 발견하여 해결하였다.

https://solved.ac/problems/level

solved.ac - 문제

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

1059번: 좋은 구간

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201059

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

먼저 Lucky Set 이란 정수의 집합이다.

[A,B] -> A<= X <= B and A < B 해당 식을 만족해야 한다.

Unlucky의 경우 [A,B]구간에 속한 숫자가 Lucky Set에 존재하지 않아야 한다.

Lucky Set과 N이 주어지면 N을 포함한 Unlucky [A,B]구간의 개수를 구하는 게 주어진 문제이다.

​

먼저 Lucky Set에 포함된 숫자의 개수를 받아오고 이를 통해 배열을 생성해 준 뒤, 해당 배열에 Lucky Set 데이터를 입력받는다 이후 해달 배열을 정렬해 주고 입력받은 N으로부터 N과 인접한 최솟값과 최댓값을 구하여 저장한다.

이때 우리가 알아야 할 경우의 수는 2가지가 존재하게 된다 N이 Lucky Set 데이터의 최솟값보다 앞에 존재하는 경우와 Lucky Set 데이터들 사이에 존재하는 경우이다.

​

먼저 N이 Lucky Set 데이터의 최솟값보다 앞에 있는 경우 파악해야 할 것은 N이 1이거나 최솟값 보다 1 작은 경우는 N이 1부터 최솟값 사이에 있는 수를 한 번씩만 방문한 개수를 카운트해주면 문제가 해결된다.

​

하지만 N이 사이 값일 경우 N을 기준으로 이전 값이나 다음 값으로 한 번씩 방문해야 하며, N 기준으로 이전 다음 값들끼리도 방문을 해주어야 한다.

두 번째로 N이 Lucky Set 데이터들 사이에 존재하는 경우이다. 이 경우 인접한 최솟값과 최댓값을 구하여 N이 최솟값 보다 1 큰 경우는 N이 최솟값 +1부터 최댓값 사이 값들을 한 번씩만 방분한 개수를 카운트해주면 되고 마찬가지로 N이 최댓값 보다 1 장은 경우 최댓값 -1로부터 최솟값 사이 값들을 한 번씩만 방문한 개수를 카운트해주면 된다.

​

하지만 N이 사이 값일 경우 N을 기준으로 이전 값이나 다음 값으로 한 번씩 방문해야 하며, N 기준으로 이전 다음 값들끼리도 방문을 해주어야 한다.

​