Skip to content

Instantly share code, notes, and snippets.

@walkingtospace
Last active August 29, 2015 14:01
Show Gist options
  • Save walkingtospace/58ac6cba402262441a53 to your computer and use it in GitHub Desktop.
Save walkingtospace/58ac6cba402262441a53 to your computer and use it in GitHub Desktop.
두 문자열 서로 permutation matching 인지 판별 문제
/*
Question : Given two strings, write a method to decide if one is a permutation of the other.
가정:
문자열은 아스키코드로 구성
extra memory 사용가능.
해법:
간단한 인덱스테이블을 생성 0으로 초기화
첫번째 문자열의 아스키코드를 인덱스로 사용하여(0~126) 인덱스 테이블에 저장할때마다 해당 인덱스의 value ++1 씩 증가.
두번째 문자열의 아스키코드를 마찬가지로 인덱스로 활용, 저장할때마다 --1씩 감소.
감소 연산 후 해당 인덱스의 value < 0일때 return false;
인덱스 테이블을 0->128까지 검사, 모두 0이면 두 문자열은 서로 순열set 중의 1개 이므로 return true;
time complexity:
문자열의 길이가 n일때: O(2n+128)->O(n)
*/
int rangeException = 0;
bool checkPermutation(const char s1[], const char s2[]) {
int len1 = strlen(s1);
int len2 = strlen(s2);
char indexTable[128];
if(len1 != len2) return false;
if(len1 == 0 || len2 == 0) return false;
memset(indexTable, 0, sizeof(indexTable));
for(int i=0; i<len1 ; i++) {
int temp = (int)s1[i];
if(temp > 126) throw rangeException;
indexTable[temp]++;
}
for(int i=0; i<len2 ; i++) {
int temp = (int)s2[i];
if(temp > 126) throw rangeException;
indexTable[temp]--;
}
for(int i=0; i<128; i++) {
if(indexTable[i] != 0) return false;
}
return true;
}
@walkingtospace
Copy link
Author

어..저건 제가 코드에서 의도를 제대로 드러내지 못한것 같은데, 문자열입력을 아스키코드라 가정했기 때문에, 아스키코드 테이블 크기가 0~126까지 이기 때문에 temp>126 을 error condition으로 지정했습니다. 지적하신대로 문자열 자체의 범위 에러 체크도 주어야 맞겠네요. 그리고 exception처리시 직접 에러 유형의 정의하지말고 std나 있는 정의 쓰라고 저번에도 지적해주셨는데..좀 찾아보고 앞으로는 그렇게 해야겠네요 두분다 감사합니다.

@coderiff
Copy link

저도 C++을 잘을 모르지만 custom exception을 정의하려고 해도 std::exception를 상속해서 하는게 맞지 않나 싶은데요. 한 번 관련해서 찾아보시는 것이 좋을 듯...
그런데 여기는 comment에 대해서 notification기능이 없는게 약간 아쉽네요.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment