1. 문제에 대한 이해
- 우리가 풀어야 할 문제는 무엇인가?
- 주어진 자료는 무엇인가?
- 조건은 무엇인가?
- 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
- 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라.
- 문제가 무엇인가?
-> 런타임 에러가 계속 발생한다
-> 괄호를 추가하거나 괄호를 추가하지 않거나라는 것이 무엇인가?
-> 괄호 안 친 경우라는 것이 무엇인가?
-> 어디서 부터 시작하면 되는가?
-> 이 코드의 의미가 무엇인가?
-> toCharArray란 무엇인가?
-> BufferedReader란 무엇인가?
-> 이 의미가 무엇인가?
-> 왜 이렇게 나누는가?
-> 끝에서는 못하기 때문 아닌가?
-> 그냥 보내면 된다
-> 4칸 보내면 된다
-> 이렇게 하면 간단히 해결된다
-> 따로 표기할 필요가 없다
-> int는 그냥 저렇게 쓰면 된다
-> 문제가 무엇인가?
->
2. 계획
- 전에 비슷한 문제를 알고 있는가?
- 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
- 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
- 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
- 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
- 자료는 모두 사용했는가?
- 조건을 모두 사용했는가?
- 문제에 포함된 핵심적인 개념은 모두 고려했는가?
3. 실행
- 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.
[내 코드]
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
public static int N;
public static int signs;
public static ArrayList<Integer> selected;
public static boolean[] check;
public static String str;
public static StringBuilder sb;
public static int maxResult;
public void calculate(){
check = new boolean[20];
for(int i=0; i<selected.size(); i++){
int num = selected.get(i);
check[num] = true;
}
int cnt = 0;
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
if(c == '+' || c == '-' || c == '*'){
if(check[cnt] == true){
int num1 = Character.getNumericValue(str.charAt(i-1));
int num2 = Character.getNumericValue(str.charAt(i+1));
int newNum = 0;
if(c == '+'){
newNum = num1+num2;
}else if(c == '-'){
newNum = num1-num2;
}else if(c == '*'){
newNum = num1*num2;
}
if(i == 1){
sb.append(Integer.toString(newNum));
}else{
sb.deleteCharAt(sb.length()-1);
sb.append(Integer.toString(newNum));
}
}else{
if(i == 1){
sb.append(Character.toString(str.charAt(i-1)));
sb.append(Character.toString(c));
}else{
sb.append(Character.toString(c));
}
}
cnt++;
}else{
if(i == 0){
continue;
}else{
int signNum = (i/2)-1;
if(selected.contains(signNum)){
continue;
}else{
sb.append(Character.toString(c));
}
}
}
}
}
public boolean isAble(){
for(int i=1; i<selected.size(); i++){
if(selected.get(i)-selected.get(i-1) == 1){
return false;
}
}
return true;
}
public int finalCalculate(){
Stack<Integer> stk = new Stack<>();
String str = sb.toString();
StringBuilder tmp = new StringBuilder();
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
if(c == '+' || c == '-' || c == '*'){
if(stk.size() == 0){
int num1 = Integer.parseInt(tmp.toString());
int num2 = Character.getNumericValue(str.charAt(i+1));
int newNum = 0;
if(c == '+'){
newNum = num1+num2;
}else if(c == '-'){
newNum = num1-num2;
}else{
newNum = num1*num2;
}
stk.push(newNum);
tmp.setLength(0);
}else{
int num1 = stk.pop();
int num2 = Character.getNumericValue(str.charAt(i+1));
int newNum = 0;
if(c == '+'){
newNum = num1+num2;
}else if(c == '-'){
newNum = num1-num2;
}else{
newNum = num1*num2;
}
stk.push(newNum);
}
}else{
tmp.append(Character.toString(c));
}
}
return stk.peek();
}
public void DFS(int pos){
if(pos == signs){
boolean result = isAble();
if(result == false){
return;
}
sb = new StringBuilder();
calculate();
int finalResult = finalCalculate();
maxResult = Math.max(maxResult, finalResult);
return;
}
selected.add(pos);
DFS(pos+1);
selected.remove(selected.size()-1);
DFS(pos+1);
}
public static void main(String args[]) throws NumberFormatException, IOException {
Main T = new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
str = br.readLine();
maxResult = Integer.MIN_VALUE;
signs = (N/2);
selected = new ArrayList<>();
int pos = 0;
T.DFS(pos);
System.out.println(maxResult);
}
}[참고 코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static int N;
public static char[]input;
public static int maxSum;
public static void main(String args[]) throws IOException {
Main T = new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
maxSum = Integer.MIN_VALUE;
N = Integer.parseInt(br.readLine());
input = new char[N];
input = br.readLine().toCharArray();
T.DFS(2, input[0]-'0');
System.out.println(maxSum);
}
public void DFS(int i, int sum){
if(i>=N){
maxSum = Math.max(maxSum, sum);
return;
}
if(i+2 < N){
int right = cal(input[i]-'0', input[i+2]-'0', input[i+1]);
int left = cal(sum, right, input[i-1]);
DFS(i+4, left);
}
DFS(i+2, cal(sum, input[i]-'0', input[i-1]));
}
public int cal(int num1, int num2, char op){
if(op == '+'){
return num1+num2;
}else if(op == '-'){
return num1-num2;
}else{
return num1*num2;
}
}
}4. 반성
- 문제를 다른 방식으로 해결할 수 있는가?
- 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
- 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?
- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
-> 코드를 정말 잘 짜야 한다
-> BufferedReader를 사용하는 법을 알아야 한다
-> 숫자의 경우 Integer.parseInt와 같이 사용한다
-> new BufferedReader(new InputStreamReader(System.in))
-> 이렇게 써야 한다
-> input을 문자 배열에 담아서 사용하면 매우 효율적이다
-> 왜냐하면 따로 변환작업이 필요 없기 때문에
-> 위치는 i로 표시하는 것이 좋다
-> i+2< N일 때만 괄호가 있는지 검사할 수 있다.(즉, 맨 끝이 아닐때만)
-> i+4와 같이 그냥 인덱스를 이동시킬 수 있다.
- cal이라는 함수를 따로 만들어서 계산할 수 있다
-> right를 먼저 계산하고, left를 계산할 수 있다.
- BufferedReader는 throws IOException과 같이 써줘야 한다.
'PS' 카테고리의 다른 글
| 행렬 테두리 회전하기 [프로그래머스] (0) | 2022.09.30 |
|---|---|
| 다단계 칫솔 판매 [프로그래머스] (1) | 2022.09.30 |
| 컴백홈 [BOJ 1189] (1) | 2022.09.26 |
| 양궁대회 [프로그래머스] - 2번째 (1) | 2022.09.23 |
| 나무 자르기 [BOJ 2805] (1) | 2022.09.23 |