[BOJ] 16639번: 괄호 추가하기 3
문제 (Gold 1)
풀이
- 숫자와 연산자를 한번에 저장할 수 있는 Expression 클래스 생성
-> 숫자를 char로 한번에 저장했더니, 9 이상의 숫자는 제대로 작동하지 않음 ㅠㅠ - 연산 리스트에서 숫자가 나오는 짝수 인덱스를 돌며 연산 수행 후, 남은 연산 리스트를 재귀 돌림
- 기저조건: 리스트에 원소 하나만 남아있을 때 ( == 숫자 하나가 남아있을 때 )
- 짝수 idx( 숫자가 있는 idx )를 돌면서 반복문 실행
- 해당 인덱스부터 숫자(i), 연산자(i+1), 숫자(i+2)를 차례로 추출
- 추출 후, 리스트에서 삭제
-> 기존 리스트에서 삭제 시, 다음 연산에 영향을 줌으로 복사한 리스트에서 로직 수행 - 연산자에 따라 연산 수행ㅁ
- 연산 수행 결과를 i번째 인덱스에 저장
- 연산자 리스트를 재귀에 태움
코드
package implement;
import java.util.*;
import java.io.*;
public class BOJ_16639_괄호추가하기3 {
/**
* Expression 원소들을 저장
*/
static class Expression{
boolean number;
long num;
char exp;
public Expression(boolean number, long num) {
this.number = number;
this.num = num;
}
public Expression(boolean number, char exp) {
this.number = number;
this.exp = exp;
}
}
static long result = Long.MIN_VALUE;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String str = br.readLine();
List<Expression> exp = new ArrayList<>();
for(int i =0 ; i < N ; i++){
if(0<=str.charAt(i)-'0'&&str.charAt(i)-'0'<10){ // 숫자 저장
exp.add(new Expression(true, str.charAt(i)-'0'));
} else{ // 연산자 저장
exp.add(new Expression(false, str.charAt(i)));
}
}
makeExpression(exp);
System.out.println(result);
}
private static void makeExpression(List<Expression> rem) {
if(rem.size() == 1){ // 숫자 하나만 남았을 때
result = Math.max(result, rem.get(0).num);
return;
}
for(int i =0 ; i < rem.size()-2 ; i+=2){
List<Expression> tmp = new ArrayList<>();
for(Expression e:rem) tmp.add(e);
long x = tmp.get(i).num; // 숫자 1
char y = tmp.get(i+1).exp; // 연산자
long z = tmp.get(i+2).num; // 숫자 2
tmp.remove(i+2); // 리스트에서 없앰
tmp.remove(i+1);
tmp.remove(i);
switch (y){
case '+':{
long n = x+z;
tmp.add(i, new Expression(true, n)); // 기존 인덱스에 계산 값 추가
break;
}
case '-':{
long n = x-z;
tmp.add(i, new Expression(true, n)); // 기존 인덱스에 계산 값 추가
break;
}
case '*':{
long n = x*z;
tmp.add(i, new Expression(true, n)); // 기존 인덱스에 계산 값 추가
break;
}
}
makeExpression(tmp);
}
}
}
Author And Source
이 문제에 관하여([BOJ] 16639번: 괄호 추가하기 3), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dot2__/BOJ-16639번-괄호-추가하기-3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)