① C 또는 C++로 답안을 작성하시는 응시자께서는 검정시스템에 제출 시, Language에서 C++를 선택하신 후 제출해 주시기를 바랍니다. ② Main 부분과 User Code 부분으로 구성되어 있습니다. A. Main 부분 : 수정할 수 없는 코드이며, 채점 시 주어지는 코드 그대로 사용됩니다. B. User Code 부분 : 실제 응시자가 작성해야 하는 코드이며, 제출 시에는 코드 내에 라이브러리 함수뿐 아니라 표준 입출력 함수도 포함되어서는 안됩니다. C. 서버에서는 Main 부분과 User Code 부분은 별도의 파일로 분리되어 컴파일이 됩니다. (main.cpp /solution.cpp 또는 Solution.java/UserSolution.java) ③ Local PC에서 프로그래밍할 시 유의 사항 A. 2개의 파일을 생성하셔야 합니다. (main.cpp/solution.cpp 또는 Solution.java/UserSolution.java) B. Main 부분의 코드를 main.cpp 또는 Solution.java에 복사해서 사용하시기 바랍니다. C. sample_input.txt를 사용하시기 위해서는 Main 부분의 코드 내에 표준 입력을 파일로 전환하는 코드(주석처리 되어 있음)의 주석을 풀어서 사용하시면 됩니다. D. User Code 부분의 코드를 작성하신 후 서버에 제출하실 때, 디버깅을 위한 라이브러리 함수뿐 아니라 표준 입출력 함수를 모두 삭제 또는 주석 처리해 주셔야 합니다. ④ 문제 내에 제약조건을 모두 명시하지 않으므로 주어지는 코드를 분석하셔야 합니다. ⑤ 코드는 개발 언어에 따라 상이할 수 있으므로, 작성할 언어를 기준으로 분석하셔야 합니다.
[문제 설명] 엑셀과 유사하게 간단한 수식을 지원하는 Table Calculator를 구현하고자 한다. Table Calculator 의 Table은 99개의 row 와 26개의 column으로 구성되며 각 영역을 cell 이라고 부른다. [Fig. 1]과 같이 row index 는 숫자로, column index 는 알파벳 대문자로 나타내며, 각 cell 의 주소값은 column index와 row index를 순서대로 붙인 문자열로 나타낸다.
Table Calculator 는 각 cell 에 해당하는 값 또는 수식의 리스트를 받아 정확한 값을 계산하여 저장해야 한다. 수식이 주어지지 않는 cell 의 값은 0으로 간주한다. [Fig. 2]는 10개 cell 에 대한 입력에 따른 결과값의 예를 나타낸다.
아래 설명을 참조하여 Table Calculator 가 제공해야 하는 다음의 API들을 작성하라.
updateCell() 을 호출하는 과정에서 특정 cell 의 값을 결정하지 못하는 경우가 발생할 수 있으며, 이러한 cell 을 미결정 cell 이라 한다. 미결정 cell 은 다음과 같이 2가지 type 이 있다. [Type 1. 순환 참조] 순환 참조란 수식의 참조 값이 맞물려 있는 경우를 말한다. 순환 참조는 [Fig. 3]과 같이 2 가지 경우로 발생할 수 있다.
- Case 1 : 자기 자신을 참조하는 경우 * A1 cell 의 경우 자기 자신을 참조 하기 때문에 특정 값으로 결정할 수 없다. - Case 2 : 2 개 이상의 cell 이 서로 순환하여 참조하는 경우 * B2, C2 cell 의 경우 서로 순환(B2→C2→B2)하여 참조하고 있기 때문에 특정 값으로 결정할 수 없다. * A4, C4, E3 cell 의 경우 서로 순환(A4→E3→C4→A4)하여 참조하고 있기 때문에 특정 값으로 결정할 수 없다. [Type 2. 순환 참조 확장] 어떤 cell 이 Type 1 의 순환 참조 cell 들 중 하나 이상을 참조하는 경우, 그 cell 또한 미결정 cell 이다. [Fig. 3]에서 B5의 경우, [Type 1] 미결정 cell 인 A4 를 참조하기 때문에 미결정 cell 이다. 미결정 cell 여부는 수식의 연산을 처리하기 전에 결정된다. [Fig. 3]의 C5와 같이 수식에서 [Type 1] 미결정 cell 인 B2를 제거할 수 있는 경우에도 C5는 미결정 cell 이다. [Fig. 3]의 D5와 같이 하나 이상의 [Type 2] 미결정 cell 을 참조해도 미결정 cell 이다. 이와 같이 updateCell() 을 통해 cell 의 수식을 변경한 후 미결정 cell 이 하나 이상 존재하는 경우, [Fig. 4]는 9번의 updateCell() 함수 수행 후, 10번째 updateCell(4, 4, “=A1+B5”, value) 함수를 호출한 이후의 예제를 나타낸다.
이는 [Type 1]과 [Type 2] 에 해당하는 미결정 cell 과 정상적으로 계산 가능한 cell 을 포함하는 예제이다. 각 cell 의 값은 아래와 같은 근거로 결정된다. - A1 : [Case 1]과 같은 미결정 cell - B2, C2 : [Case 2]와 같은 미결정 cell - A4, C4, E3 : [Case 2]와 같은 미결정 cell - E5 : [Type 1] 미결정 cell 인 A1 을 참조하기 때문에 [Type 2] 미결정 cell - B5 : 39 - D1 : -5 - E1 : 39 - (-5) = 44 - A1, B2, C2, A4, C4, E3, E5 : 미결정 cell 이 총 7개이므로 각 cell 의 값을 7로 저장 - 나머지 cell : 수식이 존재하지 않기 때문에 0 저장 - 미결정 cell 이 존재하기 때문에 false를 리턴 그리고 updateCell(3, 0, “10”, value) 가 호출되면 [Fig. 5] 와 같이 표가 갱신된다.
- C4, E3 : 이제 미결정 cell 이 아니므로 값 계산 - A1, B2, C2, E5 : 미결정 cell 이 총 4개이므로 각 cell 값을 4로 저장 - 미결정 cell 이 존재하기 때문에 false를 리턴 여기서 updateCell(0, 3, “=E1-10”, value) 가 호출되면 [Fig. 6]과 같이 표가 갱신된다.
- D1, E1 : [Case 2] 와 같은 미결정 cell - A1, B2, C2, D1, E1, E5 : 미결정 cell이 총 6개이므로 각 cell 의 값을 6으로 저장 - 미결정 cell 이 존재하기 때문에 false를 리턴 [Fig. 7]은 입력으로 주어지는 equation의 다양한 형태를 나타낸다.
[제약 사항] 1. 입력되는 Table 의 크기는 가로 26 x 세로 99 이다. 2. updateCell() 함수의 "row" 파라미터는 0 이상 98 이하의 정수이다. 3. updateCell() 함수의 "col" 파라미터는 0 이상 25 이하의 정수이다. 4. cell 주소값의 row index 는 1 이상 99 이하의 정수이다. 5. cell 주소값의 column index 는 ‘A’ 에서 ‘Z’까지의 알파벳 대문자 한 문자이다. 6. updateCell() 함수의 "equation" 파라미터는 아래 중 하나이다. a. 1 이상 10000 이하의 양의 정수 b. -10000 이상 -1 이하의 음의 정수 c. 0 또는 -0 d. 수식 - 수식은 반드시 ‘=’ 기호로 시작한다. - 수식에 사용되는 항의 최대 개수는 25 개이다. - 수식의 각 항에는 특정 cell 의 주소값 또는 정수 값이 주어진다. (이때 정수값의 범위는 -10000 이상 10000 이하이다.) - 연산자는 '+', '-' 만 허용한다. 곱셈, 나눗셈, 괄호 등의 기호는 입력되지 않는다. - [Fig. 7]의 A4, B2와 같이 첫 번째 항이 '-' 로 시작하는 경우도 있다. - 수식 문자열은 빈 칸 없이 모두 붙여져 있다. - '+', '-' 연산자 2 개가 연속해서 입력되는 경우는 없다. (예: E1--200, 200+-100, 1++2, 1-+A1) 7. [Fig. 7]의 D3, D4와 같이 수식이 주어지지 않는 cell은 0으로 저장한다. 8. [Fig. 7]의 D2와 같이 수식이 주어지지 않은 cell(D4)을 참조하는 경우, 그 cell을 0 으로 간주한다. 9. [Fig. 7]의 B3과 같이 한 cell 안에 동일한 cell 을 여러 번 참조할 수 있다. 10. 동일한 cell 에 대해서 updateCell() 함수가 여러 번 호출될 수 있다. 11. 각 cell 을 계산하는 모든 과정 중의 값과 결과 값은 100000007로 나눈 나머지 값을 저장한다. (예: A3+B3-C3+D3 → (((((A3+B3)%100000007) - C3) % 100000007) + D3) % 100000007) 12. 수식의 연산 처리 순서는 결과 값에 영향을 주지 않는다. 13. 미결정 cell 여부는 수식의 연산을 처리하기 전에 결정된다. ([Fig. 3]의 C5 참조) 14. 하나의 Test case 에서 updateCell() 함수는 최대 2000 번 호출된다. [입력 / 출력] 입출력은 제공되는 Main 부분의 코드에서 처리하므로 User Code 부분의 코드에서는 별도로 입출력 함수를 사용해서는 안 된다. Sample input에 대한 정답 출력 결과는 아래와 같은 형태로 보여진다.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
댓글