[BOJ] 백준 5676번 : 음주 코딩 (JAVA)

문제

오늘은 ACM-ICPC 대회 전 날이다. 상근이는 긴장을 풀기 위해서 팀원들과 근처 술집으로 갔다.

상근이와 친구들은 다음 날 있을 대회를 연습하기 위해서 작은 게임을 하기로 했다.

 

먼저, 선영이는 상근이에게 총 N개의 정수로 이루어진 수열 X1, X2, ... XN을 적어준다. 게임은 총 K번 라운드로 이루어져있고, 매 라운드마다 선영이는 상근이에게 명령을 하나씩 내린다. 명령은 아래와 같이 두 가지가 있다.

 

• 변경: 이 명령은 친구가 수열의 한 값을 바꾸고 싶을 때 사용한다.
• 곱셈: 선영이는 상근이에게 i와 j를 말한다. 상근이는 Xi × Xi+1 × ... × Xj-1 × Xj 의 값이 양수인지, 음수인지, 0인지를 대답한다.

 

곱셈 명령에서 상근이가 대답을 잘못했을 때의 벌칙은 소주 한 잔이다. 상근이는 갑자기 대회가 걱정되기 시작했다. 또, 상근이는 발머의 피크 이론을 증명하고 싶지 않다.

 

다행히 선영이는 상근이에게 노트북 사용을 허락했다. 상근이는 자신의 수학 실력보다 코딩 실력을 더 믿는다.

상근이를 돕는 프로그램을 작성하시오.

 

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 수열의 크기 N과 게임의 라운드 수 K가 주어진다. (1 ≤ N, K ≤ 105)

둘째 줄에는 총 N개의 숫자 Xi가 주어진다. (-100 ≤ Xi ≤ 100)

 

다음 K개 줄에는 선영이가 내린 명령이 주어진다. 명령은 C 또는 P로 시작한다.

C로 시작하는 명령은 변경 명령이고, 그 다음에 i와 V가 주어진다. Xi를 V로 변경하는 명령이다. (1 ≤ i ≤ N, -100 ≤ V ≤ 100)

 

P로 시작하는 명령은 곱셈 명령이고, 그 다음에 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)

각 테스트 케이스에 곱셈 명령은 항상 한 번 이상있다.

 

 

출력

각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다.

 

 

풀이

세그먼트 트리를 이용하여 풀 수 있는 문제였습니다.

 

그리고 2가지 사항을 제외하면 '11505번 구간 곱 구하기'와 상당히 유사한 문제였습니다.

위 문제에 대해 궁금하신 분은 아래 포스팅을 참조하시길 바랍니다.

 

 

[BOJ] 백준 11505번 : 구간 곱 구하기 (JAVA)

 

 

제가 위에서 언급한 2가지 사항을 말씀드리겠습니다.

전자는 EOF입니다.

EOF는 End of File로, 데이터 소스로부터 더 이상 읽을 수 있는 데이터가 없음을 나타냅니다.

문제의 입력값이 특정한 횟수 없이 계속 들어오기때문에 EOF 처리를 해 주어야 합니다.

 

EOF는 다음과 같은 코드로 작성할 수 있습니다.

 

 

 

 

두 번째는 오버플로우의 발생입니다.

N은 최대 10⁵이고, 배열의 각각의 요소는 최대 100입니다.

하지만, 곱셈 연산을 반복하다보면, 100¹⁰⁵이 되어 필연적으로 오버플로우가 발생할 수 밖에 없습니다.

 

따라서 이를 해결하기 위해서는 처음에 배열의 값을 입력받을 때, 양수면 1, 음수면 -1, 0이면 0으로 입력받도록 조정해야 합니다. 또한, 명령어 'C'를 입력받아서 특정 배열의 값을 V로 변경할 때도, V를 1 or -1 or 0으로 변경해 주어야 합니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.