[백준/BOJ] 1059번 : 좋은 구간 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

1059번: 좋은 구간

---

- 문제 -

 

난이도 실버 5 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

처음 입력값을 L, 다음 라인의 입력값들을 그냥 num, 마지막 입력값을 n이라 하자.

n이 포합된 집합이면서 num들이 포함 되면 안된다. 그렇다면 여기서 원하는건 num값들 중 n보다 작은 값들중 제일 큰값과 큰 값들 중 제일 작은 값을 찾으면 된다.(주어진 num들 중 n 값과 제일 가까운 값을 구하라는 것이다.)

예제 4로 예를 들면 3 7 12 18 25 100 33 1000이 num들이다. 59가 n이다.

그렇담 n인 59보다 작은 값들은 [3, 7, 12, 18, 25, 33]이 있다. 이중 제일 큰 값은 33이 되는 것이다.

n보다 큰 수들을 보자 [100, 1000]이다. 이 중 제일 작은 값은 100이 되는 것이니 위에서 말한 조건을 충족하는 수들은 33과 100인 것이다.

이제 이 두 수가 여기서 원하는 집합의 최대한의 범위이다. 이제 여기서 나올 수 있는 집합은 (A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.) 이 조건을 만족 할 것이다.

이제 다음으로 만족해야할 조건은 n값을 포합해야하는 것이다. 그럴려면 A ~ B 집합에 n인 59가 포합 되어야 한다는 것이기 때문에 A는 59보다 작거나 같아야 하고, B는 59보다 크거나 같아야 한다. 이 조건으로 만들 수 있는 조합의 개수를 구하면 된다. 방법은 2중 for문을 사용하자.

for(int A = (33 + 1); A <= n; A++) {
	for(int B = n; B < 100; B++) {
		result++;
	}
}

예제를 코드로 나타내면 이렇게 된다.(result는 조합의 개수를 저장할 정수형 변수이다.)

저렇게 하면 조합의 개수를 알아낼 수 있다. 하지만 그렇다고 저대로 출력하면 틀릴 것인데, 이유는 저 조합에서 나오면 안될 조합 하나가 나오기 때문이다. 그것은 바로 [n, n]이 나온다. 시작과 끝이 같은 조합은 있을 수 없다. 그렇기 때문에 마지막에 저 조합을 빼주기 위해 -1을 해주고 출력해주면 된다.

 

코드를 보기 전에 하나 더 추가해줘야 할 것을 말하겠다. n값이 num값들중 같은 값이 있다면? 동일 한 값이 존재하면 안된다는 좋은 조합 조건에 맞지 않기 때문에 0이 출력되야 한다. 조건을 넣자 n과 num이 같다면 0을 출력하자는 조건을.

 

코드를 보자.

---

-풀이-

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int L = Integer.parseInt(br.readLine());
		//n값보다 큰 수들중 제일 작은 수를 저장 할 변수
		int high = 1000;
		//n값보다 작은 수들중 제일 큰 수를 저장 할 변수
		int low = 0;
		//n과 num이 같은지 판단 할 변수
		int count = 0;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < L; i++) {
			int num = Integer.parseInt(st.nextToken());
			
			//n과 num이 같다면 count에 1을 더하고 반복문 종료
			if(num == n) {
				count++;
				break;
			}
			
			//n 기준 제일 가까운 수들을 뽑을 조건 문
			if(num < n && low < num) low = num;

			if(num > n && high > num) high = num;
		}
		//조합의 개수를 저장 할 변수
		int result = 0;
		//count가 1이면 n과 num이 같다는 뜻이니 0 출력
		if(count == 1) {
			System.out.println(0);
		}else {
			//풀이 방법에서 말한 조합 개수를 구하는 반복문
			for(int i = (low + 1); i <= n; i++) {
				for(int j = n; j < high; j++) {
					result++;
				}
			}
			//[n,n]이 있기때문에 -1해서 출력
			System.out.println((result - 1));
		}
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.