디펜스 게임
문1) 준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.
- 준호는 처음에 병사 n명을 가지고 있습니다.
- 매 라운드마다 enemy[i]마리의 적이 등장합니다.
- 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
- 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
- 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
- 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
무적권은 최대 k번 사용할 수 있습니다.
준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.
준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ n ≤ 1,000,000,000
- 1 ≤ k ≤ 500,000
- 1 ≤ enemy의 길이 ≤ 1,000,000
- 1 ≤ enemy[i] ≤ 1,000,000
- enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
- 모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.
입출력 예
| n | k | enemy | result |
|---|---|---|---|
| 7 | 3 | [4,2,4,5,3,3,1] | 5 |
| 2 | 4 | [3,3,3,3] | 4 |
입출력 예 설명
입출력 예 #1
- 1, 3, 5 라운드의 공격을 무적권으로 막아내고, 2, 4 라운드에 각각 병사를 2명, 5명 소모하면 5라운드까지 공격을 막을 수 있습니다. 또, 1, 3, 4번째 공격을 무적권으로 막아내고, 2, 5 번째 공격에 각각 병사를 2명, 3명 소모하여 5라운드까지 공격을 막을 수 있습니다. 그보다 많은 라운드를 막는 방법은 없으므로 5를 return 합니다.
입출력 예 #2
- 준호는 모든 공격에 무적권을 사용하여 4라운드까지 막을 수 있습니다.
나의 풀이
처음 구성했던 로직 (실패)
package programmers;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class DefenseGame {
public static int solution(int n, int k, int[] enemy) {
int defenseRound = 0;
if(k >= enemy.length) {
defenseRound = enemy.length;
System.out.println(defenseRound);
return defenseRound;
}
List<Integer> enemyList = new ArrayList<>();
for(int i = 0; i < enemy.length; i++) {
enemyList.add(enemy[i]);
}
List<Integer> copyOfEnemyList = new ArrayList<>(enemyList);
Collections.sort(enemyList, Comparator.reverseOrder());
System.out.println(enemyList);
for (int i = k - 1; i >= 0; i--) {
copyOfEnemyList.remove((Integer)enemyList.get(i));
}
System.out.println(copyOfEnemyList);
int defenseCnt = 0;
for(int i = 0; i < copyOfEnemyList.size(); i++) {
if(copyOfEnemyList.get(i) > n) {
break;
}
n -= copyOfEnemyList.get(i);
defenseCnt++;
}
defenseRound = k + defenseCnt;
System.out.println(defenseRound);
return defenseRound;
}
public static void main(String[] args) {
int[] enemy = {4, 2, 4, 5, 3, 3, 1};
solution(7, 3, enemy);
}
}
우선순위 큐로 구성한 로직
package programmers;
import java.util.Collections;
import java.util.PriorityQueue;
public class DefenseGame {
public static int solution(int n, int k, int[] enemy) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
int soldiers = n;
int immuneUses = k;
int rounds = 0;
for (int currentEnemy : enemy) {
pq.add(currentEnemy);
if (soldiers < currentEnemy) {
if (immuneUses == 0) break;
soldiers += pq.poll();
immuneUses--;
}
soldiers -= currentEnemy;
rounds++;
}
return rounds;
}
public static void main(String[] args) {
int[] enemy = {4, 2, 4, 5, 3, 3, 1};
solution(7, 3, enemy);
}
}
나의 생각
접근법
1. 라운드마다 적군 수를 우선순위 큐에 추가
2. 병사 수가 적군 수보다 작을 경우에만 무적권을 사용
3. 무적권을 사용할 때는 우선순위 큐에서 가장 많은 적군 수를 가진 라운드를 제거하고, 그 수만큼 병사 수를 증가시킴
4. 그리고 나서 현재 라운드의 적군 수를 병사 수에서 차감
5. 무적권이 없고 병사 수가 부족할 경우 게임을 종료무적권을 사용하면, 해당 라운드에서 적을 막기 위해 필요한 병사의 수를 우선순위 큐에 추가한다. 그러나 병사의 수를 즉시 더하지 않는다.
why?
무적권을 사용함으로써 그 라운드를 병사를 소모하지 않고 방어하기 때문. 그리고 나중에 무적권을 사용할 수 없을 때 큐에서 가장 많은 적을 방어할 수 있는 수를 꺼내어 실제로 병사를 추가함. 이렇게 하면, 가장 많은 병사를 요구하는 라운드를 무적권으로 대체할 수 있다.
라운드별 상황
초기 상태:
병사 수: 7명
무적권: 3회
적의 공격: [4, 2, 4, 5, 3, 3, 1]
우선순위 큐: []
우선순위 큐는 병사 수가 적군 수보다 적을 때 적의 수를 추가하고,
무적권을 사용할 때 가장 많은 적을 막았던 라운드를 선택하여 무적권을 사용하는데 최적의 효과를 낼 수 있도록 함
라운드 1: 적의 수 = 4
병사가 충분합니다. 병사 3명 남음.
우선순위 큐: [4]
라운드 2: 적의 수 = 2
병사가 충분합니다. 병사 1명 남음.
우선순위 큐: [4, 2]
라운드 3: 적의 수 = 4
병사가 부족하므로 무적권을 사용합니다. 이번 라운드의 적은 우선순위 큐에 추가
우선순위 큐: [4, 2, 4]
남은 무적권: 2회
라운드 4: 적의 수 = 5
병사가 부족하므로 무적권을 사용합니다. 이번 라운드의 적은 우선순위 큐에 추가
우선순위 큐: [4, 2, 4, 5]
남은 무적권: 1회
라운드 5: 적의 수 = 3
병사가 부족하므로 무적권을 사용합니다. 이번 라운드의 적은 우선순위 큐에 추가
우선순위 큐: [4, 2, 4, 5, 3]
남은 무적권: 0회
이 시점에서 무적권을 모두 사용. 우선순위 큐에는 지금까지 막았던 라운드의 적의 수가 모두 들어 있음.
다음 라운드에서 병사 수가 적의 수보다 적으면 무적권을 사용할 수 없으므로 게임이 종료
라운드 6: 적의 수 = 3
무적권이 없고, 병사 수(1명)가 적의 수(3명)보다 적음. 이제 큐에서 가장 큰 수를 꺼내어 병사 수를 증가시킬 수 없음. 따라서 게임은 여기서 종료
결과적으로 준호는 5라운드를 방어할 수 있음. N-Queen
문2) 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.
제한사항
- 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
- n은 12이하의 자연수 입니다.
입출력 예
| n | result |
|---|---|
| 4 | 2 |
나의 풀이
package programmers;
import java.util.Arrays;
public class NQueen {
public static boolean isSafe(char[][] board, int row, int col, int n) {
for(int i = 0; i < col; i++) {
if(board[row][i] == 'Q') {
return false;
}
}
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
// Check lower diagonal on left side
for (int i = row, j = col; j >= 0 && i < n; i++, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
public static int solveNQUtil(char[][] board, int col, int n) {
if (col == n) {
return 1;
}
int count = 0;
for (int i = 0; i < n; i++) {
if (isSafe(board, i, col, n)) {
board[i][col] = 'Q';
count += solveNQUtil(board, col + 1, n);
board[i][col] = '.'; // BACKTRACK
}
}
return count;
}
public static int solution(int n) {
char[][] board = new char[n][n];
for(int i = 0; i < n; i++) {
Arrays.fill(board[i], '.');
}
int answer = solveNQUtil(board, 0, n);
System.out.println(answer);
return answer;
}
public static void main(String[] args) {
solution(12);
}
}
1차원 배열로 로직을 구성
package programmers;
import java.util.Arrays;
public class NQueen {
static int[] board;
static int answer;
public static int solution(int n) {
board = new int[n];
backTracking(0, n);
System.out.println(answer);
return answer;
}
public static void backTracking(int depth, int n) {
if(depth == n) {
answer++;
return;
}
for(int i = 0; i < n; i++) {
board[depth] = i;
System.out.println(Arrays.toString(board));
if(valid(depth)) {
backTracking(depth + 1, n);
}
}
}
public static boolean valid(int i) {
for (int j = 0; j < i; j++) {
if (board[i] == board[j]) return false;
if (Math.abs(i - j) == Math.abs(board[i] - board[j])) return false;
}
return true;
}
public static void main(String[] args) {
solution(4);
}
}
나의 생각
5*5 board 에서 Queen이 정 중앙에 있다면, 위 그림과 같이 X자리는 퀸을 배치할 수 없다.
- 하나의 퀸이 놓여진 가로(row)에는 다른 퀸이 놓여질 수 없다.
- 하나의 퀸이 놓여진 세로(col)에는 다른 퀸이 놓여질 수 없다.
- 하나의 쿤이 놓여진 대각선에는 다른 퀸이 놓여질 수 없다.
즉, 퀸은 각 행(row)과 열(col)에서 오직 하나만 존재할 수 있기 때문에, 일차원 배열로 이를 나타낼 수 있다. 예를들어, board[0] = 1은 board판의 첫 번째 행(row)의 두번째 열(col)에 퀸이 있다는 것을 의미(board[row] = col) 한다.
public static boolean valid(int i) {
for (int j = 0; j < i; j++) {
if (board[i] == board[j]) return false;
if (Math.abs(i - j) == Math.abs(board[i] - board[j])) return false;
}
return true;
}1. 직선 구간 체크(세로(col)): if (board[i] == board[j]) return false;
board[i]와 board[j]는 각각 i행과 j행에 있는 퀸의 열 위치를 나타냄
만약 두 퀸이 같은 열에 있다면 (board[i] == board[j]), 그들은 세로(col)로 서로를 공격할 수 있음
이 조건이 참이면 현재 위치가 안전하지 않다는 뜻이므로 함수는 false를 반환
2. 대각선 체크: if (Math.abs(i - j) == Math.abs(board[i] - board[j])) return false;
이 조건은 두 퀸이 대각선상에 있는지를 검사
Math.abs(i - j)는 i행과 j행의 위치 차이(세로 거리)를 절대값으로 계산
Math.abs(board[i] - board[j])는 해당 행에 있는 퀸들의 열 위치 차이(가로 거리)를 절대값으로 계산
체스에서 두 칸이 대각선상에 있으려면, 그들의 세로 거리와 가로 거리가 동일해야함
즉, 두 절대값이 같으면, 두 퀸은 대각선상에 위치하고 있음을 의미
이 조건이 참이면, 현재 퀸의 위치가 안전하지 않다는 뜻이므로 false를 반환
이 두 조건을 통해, 주어진 i행에 대해 모든 이전 행j의 퀸과 세로(col), 대각선 상에 충돌이
없는지 검사
가로 검사를 하지 않는 이유?
- backTracking 함수는 각 행에 하나의 퀸만 놓기 때문에, 각각의 퀸이 다른 행에 있음을 보장함public static void backTracking(int depth, int n) {
if(depth == n) {
answer++;
return;
}
for(int i = 0; i < n; i++) {
board[depth] = i; // 퀸을 depth 행의 i 열에 배치하겠다는 의미
if(valid(depth)) { // 각각의 depth 행에 대하여 유효성 검사를 실시
backTracking(depth + 1, n);
}
}
}다음은 n = 4일때 백트래킹 알고리즘의 시각화 모습이다. 각 단계에서 체스판의 상태를 출력하며, 퀸을 배치하고 제거하는 과정을 보여준다. 각 depth 값은 다음을 의미한다.
depth: 현재 처리 중인 행col: 시도하는 열board: 현재 행까지의 퀸 배치 상태를 나타내는 배열
백트래킹 진행 순서
- 첫 번째 행(
depth 0)에서 첫 번째 열에 퀸을 놓고 시작 - 유효성 검사를 통과하면 다음 행으로 이동
- 두 번째 행(
depth 1)에서 퀸을 배치할 수 있는 열을 찾음, 만약 유효한 열을
찾지 못하면, 이전 행으로 돌아가서 다른 열에 퀸을 배치함 (이것이백트래킹) - 이 과정을 모든 행에 대해 반복하며, 가능한 모든 해를 탐색
Placing queen at depth 0, col 0:
Q . . .
. . . .
. . . .
. . . .
--------
Placing queen at depth 1, col 2:
Q . . .
. . Q .
. . . .
. . . .
--------
Placing queen at depth 1, col 3:
Q . . .
. . . Q
. . . .
. . . .
--------
Placing queen at depth 2, col 1:
Q . . .
. . . Q
. Q . .
. . . .
--------
Placing queen at depth 0, col 1:
. Q . .
. . . .
. . . .
. . . .
--------
Placing queen at depth 1, col 3:
. Q . .
. . . Q
. . . .
. . . .
--------
Placing queen at depth 2, col 0:
. Q . .
. . . Q
Q . . .
. . . .
--------
Placing queen at depth 3, col 2:
. Q . .
. . . Q
Q . . .
. . Q .
--------
Solution found at depth 4:
. Q . .
. . . Q
Q . . .
. . Q .
--------
Placing queen at depth 0, col 2:
. . Q .
. . . .
. . . .
. . . .
--------
Placing queen at depth 1, col 0:
. . Q .
Q . . .
. . . .
. . . .
--------
Placing queen at depth 2, col 3:
. . Q .
Q . . .
. . . Q
. . . .
--------
Placing queen at depth 3, col 1:
. . Q .
Q . . .
. . . Q
. Q . .
--------
Solution found at depth 4:
. . Q .
Q . . .
. . . Q
. Q . .
--------
Placing queen at depth 0, col 3:
. . . Q
. . . .
. . . .
. . . .
--------
Placing queen at depth 1, col 0:
. . . Q
Q . . .
. . . .
. . . .
--------
Placing queen at depth 2, col 2:
. . . Q
Q . . .
. . Q .
. . . .
--------
Placing queen at depth 1, col 1:
. . . Q
. Q . .
. . . .
. . . .
--------
Result
2
괄호 변환
문3) 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.
수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.
용어의 정의
'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.
그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.
예를 들어, "(()))("와 같은 문자열은 "균형잡힌 괄호 문자열" 이지만 "올바른 괄호 문자열"은 아닙니다.
반면에 "(())()"와 같은 문자열은 "균형잡힌 괄호 문자열" 이면서 동시에 "올바른 괄호 문자열" 입니다.
'(' 와 ')' 로만 이루어진 문자열 w가 "균형잡힌 괄호 문자열" 이라면 다음과 같은 과정을 통해 "올바른 괄호 문자열"로 변환할 수 있습니다.
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
4-3. ')'를 다시 붙입니다.
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
4-5. 생성된 문자열을 반환합니다."균형잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.
매개변수 설명
- p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
- 문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다.
- 만약 p가 이미 "올바른 괄호 문자열"이라면 그대로 return 하면 됩니다.
입출력 예
| p | result |
|---|---|
| "(()())()" | "(()())()" |
| ")(" | "()" |
| "()))((()" | "()(())()" |
입출력 예 설명
입출력 예 #2
- 두 문자열 u, v로 분리합니다.
- u = ")("
- v = ""
- u가 "올바른 괄호 문자열"이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
- v에 대해 1단계부터 재귀적으로 수행하면 빈 문자열이 반환됩니다.
- u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 ""이 됩니다.
-따라서 생성되는 문자열은 "(" + "" + ")" + ""이며, 최종적으로 "()"로 변환됩니다.
입출력 예 #3
- 두 문자열 u, v로 분리합니다.
- u = "()"
- v = "))((()"
- 문자열 u가 "올바른 괄호 문자열"이므로 그대로 두고, v에 대해 재귀적으로 수행합니다.
- 다시 두 문자열 u, v로 분리합니다.
- u = "))(("
- v = "()"
- u가 "올바른 괄호 문자열"이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
- v에 대해 1단계부터 재귀적으로 수행하면 "()"이 반환됩니다.
- u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 "()"이 됩니다.
- 따라서 생성되는 문자열은 "(" + "()" + ")" + "()"이며, 최종적으로 "(())()"를 반환합니다.
- 처음에 그대로 둔 문자열에 반환된 문자열을 이어 붙이면 "()" + "(())()" = "()(())()"가 됩니다.
나의 풀이
package programmers;
import java.util.Stack;
public class ParenthesesConversion {
public static boolean isValid(String v) {
Stack<Character> stack = new Stack<>();
for(char c : v.toCharArray()) {
if(c == '(') {
stack.push(c);
}else if(c == ')') {
if(stack.isEmpty() || stack.pop() != '(') {
return false;
}
}
}
return stack.isEmpty();
}
public static String convert(String c) {
if(c.isEmpty()) return "";
int balance = 0;
int splitPoint = 0;
for(int i = 0; i < c.length(); i++) {
if(c.charAt(i) == '(') {
balance++;
}else {
balance--;
}
if(balance == 0) {
splitPoint = i + 1;
break;
}
}
String u = c.substring(0,splitPoint);
String v = c.substring(splitPoint);
if(isValid(u)) {
return u + convert(v);
}else {
String newString = "(" + convert(v) + ")";
String flippedU = u.substring(1, u.length() - 1)
.replaceAll("\\(", "0")
.replaceAll("\\)", "(")
.replaceAll("0", ")");
return newString + flippedU;
}
}
public static String solution(String p) {
String answer = "";
if(isValid(p)) {
answer = p;
return answer;
}
answer = convert(p);
return answer;
}
public static void main(String[] args) {
String bracket = ")(";
solution(bracket);
}
}
멀쩡한 사각형
문4) 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.
제한사항
- W,H : 1억 이하의 자역수
입출력 예
| W | H | result |
|---|---|---|
| 8 | 12 | 80 |
입출력 예 설명
입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.
나의 풀이
gcd 메서드를 직접 구현한 방법
package programmers;
public class NormalSquare {
public static long gcd(long a , long b) {
while(b != 0) {
long temp = b;
b = a % b;
a = temp;
}
return a;
}
public static long solution(int w, int h) {
long lw = (long) w;
long lh = (long) h;
long a = gcd(lw,lh);
long answer = lw * lh - (lw + lh - a);
return answer;
}
public static void main(String[] args) {
solution(8, 12);
}
}
BigInteger 클래스의 gcd메서드를 적용한 방법
package programmers;
import java.math.BigInteger;
public class NormalSquare {
public static long solution(int w, int h) {
long gcd = BigInteger.valueOf(w).gcd(BigInteger.valueOf(h)).longValue();
long answer = (long)w * (long)h - ((long)w + (long)h - gcd);
return answer;
}
public static void main(String[] args) {
long result = solution(8, 12);
}
}
나의 생각
long gcd = BigInteger.valueOf(w).gcd(BigInteger.valueOf(h)).longValue();
수식 최대화
문5) IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다.
이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다.
해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, ) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.
단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 즉, + > - > 또는 - > > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +, > - 또는 * > +,-처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다. 수식에 포함된 연산자가 2개라면 정의할 수 있는 연산자 우선순위 조합은 2! = 2가지이며, 연산자가 3개라면 3! = 6가지 조합이 가능합니다.
만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출하며 제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다.
예를 들어, 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다.
"100-200*300-500+20"
일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 > +,- 로 우선순위가 정의되어 있습니다.
대회 규칙에 따라 + > - > 또는 - > > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +, > - 또는 > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다.
반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.
참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.
제한사항
- expression은 길이가 3 이상 100 이하인 문자열입니다.
- xpression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
- 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
- expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
- 즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
- "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
- expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
- 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 26^3 - 1 이하가 되도록 입력이 주어집니다.
- 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.
입출력 예
| expression | result |
|---|---|
"100-200*300-500+20" | 60420 |
"50*6-3*2" | 300 |
입출력 예 설명
입출력 예 #1
* > + > - 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.
100-200*300-500+20
= 100-(200*300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420
따라서, 우승 시 받을 수 있는 상금은 |-60420| = 60420 입니다.
입출력 예 #2
- > * 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.(expression에서 + 연산자는 나타나지 않았으므로, 고려할 필요가 없습니다.)
50*6-3*2
= 50*(6-3)*2
= (50*3)*2
= 150*2
= 300
따라서, 우승 시 받을 수 있는 상금은 300 입니다.
나의 풀이
package programmers;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class MaximizeFormula {
public static long calculate(String expression, String opOrder) {
List<Long> numbers = new ArrayList<>();
List<Character> ops = new ArrayList<>();
String num = "";
for(char a : expression.toCharArray()) {
if(a == '-' || a == '*' || a == '+') {
numbers.add(Long.parseLong(num));
ops.add(a);
num = "";
}else {
num += a;
}
}
numbers.add(Long.parseLong(num));
for(char op : opOrder.toCharArray()) {
for(int i = 0; i < ops.size(); i++) {
if(ops.get(i) == op) {
long result = 0;
switch (op) {
case '+':
result = numbers.get(i) + numbers.get(i + 1);
break;
case '-':
result = numbers.get(i) - numbers.get(i + 1);
break;
case '*':
result = numbers.get(i) * numbers.get(i + 1);
break;
}
numbers.remove(i + 1);
numbers.set(i, result);
ops.remove(i);
i--;
}
}
}
return Math.abs(numbers.get(0));
}
public static void generateCombinations(List<Character> operators, String current, List<String> combinations ) {
if(operators.isEmpty()) {
combinations.add(current);
return;
}
for(int i = 0; i < operators.size(); i++) {
char operator = operators.remove(i);
generateCombinations(operators, current + operator, combinations);
operators.add(i, operator);
}
}
public static long solution(String expression) {
Set<Character> operatorSet = new HashSet<>();
List<String> combinations = new ArrayList<>();
for(char a : expression.toCharArray()) {
if(a == '-' || a == '*' || a == '+') {
operatorSet.add(a);
}
}
generateCombinations(new ArrayList<>(operatorSet), "", combinations);
long max = Long.MIN_VALUE;
for (String opOrder : combinations) {
long result = calculate(expression, opOrder);
max = Math.max(max, result);
}
return max;
}
public static void main(String[] args) {
String expression = "100-200*300-500+20";
solution(expression);
}
}
