[문제]
“isogram”은 동일한 문자가 없는 단어를 말한다.
오직 문자만을 포함하는 문자열이 “isogram” 인지 아닌지를 결정하는 프로그램을 작성하라.
단, 대/문자는 무시하고, 빈 문자열(empty string)은 “isogram”이다.
function isIsogram(str){ // your code}[예제]
isIsogram( "Dermatoglyphics" ) == trueisIsogram( "aba" ) == falseisIsogram( "moOse" ) == false // -- ignore letter case[알고리즘]
* 빈 문자열이면, true를 리턴하라.
* 빈 문자열이 아니라면, for문을 돌려, 인풋 str의 각 문자를 소문자로 만든다.(대/소문자가 같은 것이기 때문에, 모든 문자를 소문자로 통일한다.)
* 빈 배열을 선언하고, for문에서의 각 문자가 배열에 포함되어 있지 않으면, 배열에 추가시킨다.
* for문후에, 배열 요소의 수와 인풋 str의 문자의 수가 같으면, true를 리턴하라.(수가 같다는 것은 인풋 str안에 동일한 문자가 없다는 것을 의미한다.)
* 그렇지 않으면, false를 리턴하라.
[Solution]
function isIsogram(str){
var arr = [];
if(str === "") {
return true;
} else {
for(var i = 0; i < str.length; i++) {
var letter = str.charAt(i).toLowerCase();
if(!arr.includes(letter)) {
arr.push(letter);
}
}
}
if(arr.length === str.length) {
return true;
} else {
return false;
}
}
Congratulations @cheonmr! You have completed some achievement on Steemit and have been rewarded with new badge(s) :
Click on any badge to view your own Board of Honor on SteemitBoard.
To support your work, I also upvoted your post!
For more information about SteemitBoard, click here
If you no longer want to receive notifications, reply to this comment with the word
STOP위 알고리즘은 O(N)으로 보이지만, arr.includes(letter) 때문에 N^2입니다. O(N) 으로 줄일 수 있는 방법이 있습니다.
한가지 더 말씀드리면 arr.includes(letter) 면 isogram 이 아니겠지요?
안녕하세요! O(N) 으로 줄일 수 있는 방법이 있다는 게 정확히 무슨 말인가요? 그리고, str에서 반복되는 문자가 있는지 나중에 length로 확인하기 위해, array로 추가하는 방식으로 작성한 것입니다. 위와 같이 해서, 답은 풀렸는데, 혹시 이게 잘못된 해결법일까요?
알고리즘을 배우기 전에 시간복잡도에 대해서 알아야 합니다.
문자열길이가 100이라면 N 과 N^2 이 차이가 미미하지만 길이가 1억이라면 후자의 알고리즘 복잡도라면 컴퓨터가 풀 수 없을 수도 있습니다. (이 문제의 경우는 아니지만 ^^)
알고리즘은 맞고/틀리고도 있지만 제한된 시간에 답이 나오고 안 나오고 있습니다.
알파벳과 같이 한정된 갯수에 대한 있다/없다 등을 처리하기 위해서는 비트마스크를 씁니다.
비둘기집의 원리에 의하면 소문자의 모든 갯수보다 문자열이 크다면 적어도 하나의 문자가 중복되어있을 겁니다.
아 그렇군요! 좋은 내용 감사드립니다! 현재는 기초적인 알고리즘부터 정리하는 단계라 아직 시간복잡도나 비트마스크 관련해서는 공부를 못했습니다. 이런 부분들을 알고리즘을 공부하면서 동시에 공부하는게 좀 더 나을까요?