문제 개요
4개의 상품을 판매하고 있으며, i번째 상품의 가격이 배열 cost[i]에 저장되어 있다고 가정해 봅시다. 그리고 실제 판매가 이루어진 순서는 문자열 items에 담겨 있습니다. 우리가 해야 할 일은 이 정보를 바탕으로 총 판매 금액을 계산하는 것입니다.
문자열 items에는 1부터 4까지의 정수가 포함되며, 중복된 숫자가 있을 수도 있고 어떤 순서로든 배치될 수 있습니다.
예를 들어, 입력이 cost = {10, 15, 10, 5}, items = "14214331"이라면 출력 결과는 75가 됩니다.
계산 과정을 살펴보면 다음과 같습니다. 판매된 상품은 차례대로 1, 4, 2, 1, 4, 3, 3, 1이며, 각 가격(10 + 5 + 15 + 10 + 5 + 10 + 10 + 10)을 모두 더하면 총 75원이 됩니다.
해결 접근 방식
이 문제는 매우 간단한 반복문 하나로 해결할 수 있습니다. 알고리즘은 다음과 같습니다.
- 총합을 저장할 변수
total을 0으로 초기화합니다. - 문자열
items의 길이만큼 반복하면서, 각 문자를 숫자로 변환한 뒤 해당 인덱스의 가격을total에 더합니다. - 반복이 끝나면
total을 반환합니다.
의사 코드로 표현하면 다음과 같습니다.
total := 0
for i := 0 부터 items 크기 미만까지 1씩 증가하면서:
total := total + cost[items[i] - '0' - 1]
return total여기서 items[i] - '0'은 문자형 숫자를 정수 값으로 변환하는 역할을 하고, 배열 인덱스는 0부터 시작하므로 추가로 1을 빼주어야 올바른 상품 가격에 접근할 수 있습니다.
C++ 구현 예제
아래는 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
#define N 100
int solve(int cost[], string items) {
int total = 0;
for(int i = 0; i < items.size(); i++)
total += cost[items[i] -'0' - 1];
return total;
}
int main() {
int cost[] = {10, 15, 10, 5};
string items = "14214331";
cout<< solve(cost, items);
return 0;
}입력
{10, 15, 10, 5}, "14214331"출력
75
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 문자열 items의 길이입니다. 문자열의 각 문자를 한 번씩만 방문하면 되기 때문에 매우 효율적입니다. 공간 복잡도 또한 별도의 자료구조 없이 총합 변수 하나만 사용하므로 O(1)입니다.