구글 코딩 잼 연습 - Store Credit 솔류션
[출처: https://code.google.com/codejam/contest/351101/dashboard#s=p0]
사용된 언어는 Java 입니다 ^^
풀어야 될 문제는 다음과 같네요.
Problem
You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).
Input
The first line of input gives the number of cases, N. N test cases follow. For each test case there will be:
- One line containing the value C, the amount of credit you have at the store.
- One line containing the value I, the number of items in the store.
- One line containing a space separated list of I integers. Each integer P indicates the price of an item in the store.
- Each test case will have exactly one solution.
Output
For each test case, output one line containing "Case #x: " followed by the indices of the two items whose price adds up to the store credit. The lower index should be output first.
Limits
5 ≤ C ≤ 1000
1 ≤ P ≤ 1000
Small dataset
N = 10
3 ≤ I ≤ 100
Large dataset
N = 50
3 ≤ I ≤ 2000
Sample
첫번째 예제를 보면 100만원 (= C) 를 가계에 들고 갔는데 5만원, 75만원, 25만원 상품들이 있어요. 그러면 여기서 정확하게 2개만 사고 100만원 어치를 살려면 75만원 25만원 어치를 사야하겠죠? 75 더하기 25는 100만원 이니까요. 그 다음 예제도 마찬가지에요. 200만원을 가계에 가져 갔는데 150만원, 24만원, 79만원, 50만원, 88만원, 345만원, 3만원 가치의 상품들이 있어요. 그러면 150만원 그리고 50만원 상품 2개를 사면 딱 200만원 어치를 살수 있겠죠.
입력 단위에서 처음에 있는 숫자 3은 총 시뮬레이션 해야할 케이스 구요. 그러니까 여기 예제에서는 케이스가 3가지 묵음으로 있는거죠. 예를 들어 첫번째 예제 같은 경우는 100 이 Credit (C) 이고 그 다음 3 이란건 number of items (I) 즉 그 다음줄에 나올 총 상품의 합계를 말하고 그 다음 마지막 줄에는 5, 75, 25 이렇게 상품의 가격이 (P) 가 나오는거죠.
출력 예제을 보면 알수 있듯이 각 케이스마다 첫번째 상품의 인덱스 그리고 두번째 상품의 인덱스가 필요합니다. 그래서 Array of String 를 리턴할 computeCreditScore 란 함수를 만들었어요. 기대하는 가격 expected 와 여러가지 상품의 가격을 가지고 있는 Array of String 인 list 를 함수의 입력으로 보내면 답을 메인으로 리턴하는 함수에요.
Big-O 퍼포먼스는 우선 멤인에서 케이스 만큼 돌리니까 O(N) 에다가 computeCreditScore 함수 안에서 M + (M - 1) + (M - 2) ... 이런식으로 찾는데 까지 돌리니까 실제로는 O(N * M) 보다는 조금 크겠지만 그래도 O(N * M) 이라고 할수 있겠네요.
package com.google.practice;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
public class StoreCredit {
private static final String INPUT = "A-large-practice.in";
private static final String OUTPUT = "A-large-practice.out";
public static void main(String[] args) throws NumberFormatException, IOException {
StoreCredit sc = new StoreCredit();
BufferedReader br = new BufferedReader(new FileReader(INPUT));
BufferedWriter bw = new BufferedWriter(new FileWriter(OUTPUT));
int numRun = Integer.parseInt(br.readLine());
for(int i=0; i < numRun; ++ i) {
int expected = Integer.parseInt(br.readLine());
int size = Integer.parseInt(br.readLine());
String[] listInput = br.readLine().split(" ");
int[] answer = sc.computeCreditStore(expected, size, listInput);
bw.write("Case #" + (i+1) + ": " + answer[0] + " " + answer[1]);
bw.write("\n");
}
bw.close();
br.close();
}
public int[] computeCreditStore(int expected, int size, String[] list) {
int lastIndex = size - 1;
boolean found = false;
int iLeft = 0;
int iRight = 1;
while(!found && iLeft < lastIndex) {
int sum = Integer.parseInt(list[iLeft]) + Integer.parseInt(list[iRight]);
if(sum == expected) {
found = true;
}
else {
++ iRight;
}
if(!found && iRight > lastIndex) {
++ iLeft;
iRight = iLeft + 1;
}
}
return new int[] {iLeft + 1,iRight + 1};
}
}