다트게임 결과는 문자열로 주어집니다. (예: 1S2D*3T )
게임 횟수 총 3번
각 게임에서 얻을 수 있는 점수 0 ~ 10점 (10은 길이가 2인 문자열임을 주의)
S, D, T (1제곱, 2제곱, 3제곱)
게임당 한개씩만 나옵니다.
' * '
*, # 는 둘 중 하나만 존재, 없을 수도 있습니다.
3번의 게임에서 얻은 점수 합을 출력하세요.
그렇게 어려워 보이지는 않습니다.
구현 문제의 경우 저는 다음과 같이 합니다.
다시 문제 확인 안 할 정도로, 빼먹은 조건이 없는지 검토
위의 문제의 란에 적은 내용이 손으로 정리한 내용입니다.
길이 n인 문자열에 각 수식 계산
O(n) 3(최대 3 거듭 제곱) = O(n) 상수생략
문자열 최대 길이 9
1억에 1초 걸리기 때문에 시간안에 충분히 풀 수 있습니다.
#include <string>
#define max_int 4
using namespace std;
/*
시간 복잡도: O(n)
공간 복잡도: O(n)
사용한 알고리즘: 거듭제곱
사용한 자료구조: 배열
*/
/*
거듭 제곱
3제곱 까지 이기 때문에
num * num * num 해도 되고
반복문 써도 되고
분할해서 DP 써도 되고
*/
int pow(int num, char c){
int result = num;
int a = 0;
if(c == 'S') a = 1;
else if(c == 'D') a = 2;
else a = 3;
for(int i=2; i<=a; i++) {
result = result * num;
}
return result;
}
int solution(string dartResult) {
// 1. 입력 및 초기화
int answer = 0;
int idx = 0, a[max_int] = {0, 0, 0, 0};
int size = (int)dartResult.size();
// 2. 로직 수행
for(int i=0; i < size; i++){
char cur = dartResult[i];
// 1) 거듭 제곱 진행합니다.
if(cur == 'S' || cur == 'D' || cur == 'T'){
a[idx] = pow(a[idx], cur);
}
// 2) 2배를 해줍니다.
else if(cur == '*'){
/*
첫번째 게임인 경우 - 현재 점수 * 2
두번째, 세번째 게임인 경우 - 현재와 바로 전 점수 * 2
*/
int start_idx = idx == 1 ? 1 : idx - 1;
for(int i=start_idx; i<=idx; i++){
a[i] = a[i] * 2;
}
}
// 3) 현재 점수를 -1배 합니다.
else if(cur == '#'){
a[idx] = a[idx] * -1;
}
// 4) 현재 숫자를 검사합니다.
else{
// 아스키코드에서 숫자를 추출합니다.
int num = cur - '0';
// 만약 10인경우 (길이 2인 문자열)
if(cur == '1'){
if(i < size - 1 && dartResult[i + 1] == '0') {
num = 10;
}
}
idx++;
a[idx] = num;
if(num == 10) i += 1;
}
}
// 3. 결과 합산
for(int i=1; i<=3; i++) {
answer += a[i];
}
// 4. 출력
return answer;
}
/*
시간 복잡도: O(n)
공간 복잡도: O(n)
사용한 알고리즘: 거듭제곱
사용한 자료구조: 배열
*/
class Solution {
/*
거듭 제곱
3제곱 까지 이기 때문에
num * num * num 해도 되고
반복문 써도 되고
분할해서 DP 써도 되고
*/
public int pow(int num, char c){
int result = num;
int a = 0;
if(c == 'S') a = 1;
else if(c == 'D') a = 2;
else a = 3;
for(int i=2; i<=a; i++) {
result = result * num;
}
return result;
}
public int solution(String dartResult) {
// 1. 입력 및 초기화
int answer = 0;
int idx = 0, a[] = new int[4];
int size = (int)dartResult.length();
// 2. 로직 수행
for(int i=0; i < size; i++){
char cur = dartResult.charAt(i);
// 1) 거듭 제곱 진행합니다.
if(cur == 'S' || cur == 'D' || cur == 'T'){
a[idx] = pow(a[idx], cur);
}
// 2) 2배를 해줍니다.
else if(cur == '*'){
/*
첫번째 게임인 경우 - 현재 점수 * 2
두번째, 세번째 게임인 경우 - 현재와 바로 전 점수 * 2
*/
int start_idx = idx == 1 ? 1 : idx - 1;
for(int j=start_idx; j<=idx; j++){
a[j] = a[j] * 2;
}
}
// 3) 현재 점수를 -1배 합니다.
else if(cur == '#'){
a[idx] = a[idx] * -1;
}
// 4) 현재 숫자를 검사합니다.
else{
// 아스키코드에서 숫자를 추출합니다.
int num = cur - '0';
// 만약 10인경우 (길이 2인 문자열)
if(cur == '1'){
if(i < size - 1 && dartResult.charAt(i+1) == '0') {
num = 10;
}
}
idx++;
a[idx] = num;
if(num == 10) i += 1;
}
}
// 3. 결과 합산
for(int i=1; i<=3; i++) {
answer += a[i];
}
// 4. 출력
return answer;
}
}
'''
시간 복잡도: O(n)
공간 복잡도: O(n)
사용한 알고리즘: 거듭제곱
사용한 자료구조: 배열
'''
'''
거듭 제곱
3제곱 까지 이기 때문에
num * num * num 해도 되고
반복문 써도 되고
분할해서 DP 써도 되고
'''
def pow(num, c):
result = num
a = 0
if c == 'S': a = 1
elif c == 'D': a = 2
else: a = 3
for i in range(2, a+1):
result = result * num
return result
def solution(dartResult):
# 1. 입력 및 초기화
answer = 0
idx = 0
a = [0 for _ in range(4)]
size = len(dartResult)
# 2. 로직 수행
i = 0
while i < size:
cur = dartResult[i]
# 1) 거듭 제곱 진행합니다.
if cur == 'S' or cur == 'D' or cur == 'T':
a[idx] = pow(a[idx], cur)
# 2) 2배를 해줍니다.
elif cur == '*':
'''
첫번째 게임인 경우 - 현재 점수 * 2
두번째, 세번째 게임인 경우 - 현재와 바로 전 점수 * 2
'''
start_idx = 0
if idx == 1: start_idx = 1
else: start_idx = idx - 1
for j in range(start_idx, idx + 1):
a[j] *= 2
# 3) 현재 점수를 -1배 합니다.
elif cur == '#':
a[idx] = a[idx] * -1
# 4) 현재 숫자를 검사합니다.
else:
# 아스키코드에서 숫자를 추출합니다.
num = ord(cur) - ord('0')
# 만약 10인경우 (길이 2인 문자열)
if cur == '1':
if i < size - 1 and dartResult[i + 1] == '0':
num = 10
idx += 1
a[idx] = num
if num == 10:
i = i + 1
i = i + 1
# 3. 결과 합산
for i in range(1, 4):
answer += a[i]
# 4. 출력
return answer
/*
시간 복잡도: O(n)
공간 복잡도: O(n)
사용한 알고리즘: 거듭제곱
사용한 자료구조: 배열
*/
/*
거듭 제곱
3제곱 까지 이기 때문에
num * num * num 해도 되고
반복문 써도 되고
분할해서 DP 써도 되고
*/
function pow(num, c){
let result = num;
let a = 0;
if(c == 'S') a = 1;
else if(c == 'D') a = 2;
else a = 3;
for(let i=2; i<=a; i++) {
result = result * num;
}
return result;
}
function solution(dartResult) {
// 1. 입력 및 초기화
let answer = 0;
let idx = 0;
let a = [0, 0, 0, 0];
let size = dartResult.length;
// 2. 로직 수행
for(let i=0; i < size; i++){
let cur = dartResult[i];
// 1) 거듭 제곱 진행합니다.
if(cur == 'S' || cur == 'D' || cur == 'T'){
a[idx] = pow(a[idx], cur);
}
// 2) 2배를 해줍니다.
else if(cur == '*'){
/*
첫번째 게임인 경우 - 현재 점수 * 2
두번째, 세번째 게임인 경우 - 현재와 바로 전 점수 * 2
*/
let start_idx = idx == 1 ? 1 : idx - 1;
for(let j=start_idx; j<=idx; j++){
a[j] = a[j] * 2;
}
}
// 3) 현재 점수를 -1배 합니다.
else if(cur == '#'){
a[idx] = a[idx] * -1;
}
// 4) 현재 숫자를 검사합니다.
else{
// 아스키코드에서 숫자를 추출합니다.
let num = cur - '0';
// 만약 10인경우 (길이 2인 문자열)
if(cur == '1'){
if(i < size - 1 && dartResult[i + 1] == '0') {
num = 10;
}
}
idx++;
a[idx] = num;
if(num == 10) i += 1;
}
}
// 3. 결과 합산
for(let i=1; i<=3; i++) {
answer += a[i];
}
// 4. 출력
return answer;
}