문제
레벨2 문제라서 그리 어렵지 않으리라 생각했다. 출제자 입장에서는 문자열을 잘 파싱하는지, 그리고 구현하려는 내용을 정확히 구현하는지를 살펴보려는 문제였다.
처음에는 2017년 문제이기도 하고, Java와 C++로만 풀 수 있어서, Python 등에서 주어지는 특정한 함수를 직접 구현할 수 있는지를 살펴보는 문제라고 생각했다. 심장은 수학문제는 아닐거라고 외쳤지만, 코테용 주언어가 C++/JAVA가 아닌 탓에 어떻게든 C++/JAVA의 로직 구현 대신 수학으로 해결보고자 앞에 노트를 펴두고 이것저것을 많이 끄적거렸다.
처음 발견했던 것은 어차피 무조건 두 명 간의 거리로만 조건이 주어지므로, 2명의 거리가 0일 때, 1일 때, 2일 때, … 등등에 특정한 점화식이 도출될 것이라 생각했었다. 하지만 노트에 한참 쓰다보니 두 개의 조건을 동시에 고려해야하는 점을 간과했단 사실을 깨달았다. 이에 빠르게 접고 다른 방향으로 풀이를 생각했다.
맨 처음에 얼핏 생각했다가 접은 모든 경우를 만들기를 다시 생각했다. 처음에는 8!인 40320, 그리고 for loop 내부에서 조건에 해당하는지를 살펴보면서 사용될 시간복잡도까지 고려했을 때 대략 O(10^5) 정도가 나오리라고 생각했다. 심지어 조건이 여러개가 들어오니, 막연하게 10^5보다 더 크겠지 생각하고 접었었다.
그러나 반드시 효율성 테스트까지 있는 것은 아니기에 제출 후 채점하기
를 눌러보니 정확성 테스트밖에 없었다!!
처음에는 자바로 풀기 시작했는데, 생각해보니 C++에는 순열을 만들어주는 함수 next_permutation이 있었던 게 생각나서 C++로 풀기 시작했다.
풀이
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int ascii(char n) {
return int(n)-int('A');
}
int solution(int n, vector<string> data) {
int answer = 0;
vector<int> defaultLine = {ascii('A'), ascii('C'), ascii('F'), ascii('J'),
ascii('M'), ascii('N'), ascii('R'), ascii('T')};
do
{
int check = 0;
for(int i=0;i<n;i++)
{
int first = ascii(data[i][0]); // N
auto firstLoc = find(defaultLine.begin(), defaultLine.end(), first) - defaultLine.begin();
int second = ascii(data[i][2]); // F
auto secondLoc = find(defaultLine.begin(), defaultLine.end(),second) - defaultLine.begin();
int diff = int(abs(firstLoc - secondLoc) - 1);
int targetDiff = int(data[i][4]-48); // 0
if(data[i][3] == '=')
if(diff != targetDiff) check++;
else if(data[i][3] == '>')
if(diff <= targetDiff) check++;
else if(diff >= targetDiff) check++;
}
if(check == 0) answer++;
}while(next_permutation(defaultLine.begin(), defaultLine.end()));
return answer;
}
순열의 최초 값으로 문제에서 제시한 캐릭터들의 순서대로 defaultLine에 줄을 일단 세워주고 시작했다.
이제 next_permutation으로 순열을 만들어주면서, 조건(data)의 첫번째 인덱스 값을 first에, 그리고 값의 현 순열에서의 위치를 firstLoc에 받아주었고, 두번째 값도 마찬가지로 second와 secondLoc에 넣어주었다.
그 다음 두 위치의 절대값에 1을 빼서(=>둘 사이에 있는 다른 캐릭터의 수 이므로) diff에 넣어주고, data에서 주어진 조건거리값을 targetDiff에 넣어주었다.
targetDiff를 구하는 데(int targetDiff = int(data[i][4]-48);
)에서 의도하지 않은 값이 들어와 한참을 헤맸었다. 처음엔 int(data[i][4])
로만 구해주었기 때문에, string vector에 char로 들어가있는 숫자가 아스키 값으로 나오고 있었다. 원래는 중간중간 cout으로 찍어주는 편이지만, next_permutation을 쓰는 중이었어서 출력 초과 에러가 계속 나와서 체크를 못했던 탓이었다. (다음에는 값이 이상하면 바로바로 찍어보자! 눈버깅은 한계가 있다!!) 이 부분을 찾고, ‘0’의 아스키코드값인 48을 빼주어서 해결했다.
이후 data에서 주어진 조건operation(=, >, <)을 받아와서 조건을 나누어주니 코드가 잘 돌아가주었다.
처음에는 int check 대신 bool 값을 사용하고 싶었는데, 두 개 이상의 조건을 만족시키는지 여부를 bool 값으로 체크해주고, 조금이라도 코드를 빨리 돌리기 위해서 bool 값이 false(=하나라도 조건을 불만족 시킴)면 break 해주는 부분을 작성하며 자꾸 에러가 나서 int check으로 바꾸었다.