___  ___    _ _    _  _ _____   _____
 / __|/ _ \  | | |  | || |_ _\ \ / / __|
| (_ | (_) | |_  _| | __ || | \ V /| _|
 \___|\___/    |_|  |_||_|___| \_/ |___|

 --- A GOPHER-LIKE INTERFACE FOR HIVE BLOCKCHAIN ---

[JS 알고리즘 문제] #2 Isograms

BY: @cheonmr | CREATED: March 24, 2018, 1:08 p.m. | VOTES: 5 | PAYOUT: $0.18 | [ VOTE ]

[문제]

“isogram”은 동일한 문자가 없는 단어를 말한다.

오직 문자만을 포함하는 문자열이 “isogram” 인지 아닌지를 결정하는 프로그램을 작성하라.

단, 대/문자는 무시하고, 빈 문자열(empty string)은 “isogram”이다.

function isIsogram(str){

    // your code

}

[예제]

isIsogram( "Dermatoglyphics" ) == true

isIsogram( "aba" ) == false

isIsogram( "moOse" ) == false // -- ignore letter case

[알고리즘]

[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;
     }
}

TAGS: [ #kr-dev ] [ #kr ] [ #kr-newbie ] [ #developer ] [ #javascript ]

Replies

@steemitboard | March 24, 2018, 5:07 p.m. | Votes: 0 | [ VOTE ]

Congratulations @cheonmr! You have completed some achievement on Steemit and have been rewarded with new badge(s) :

[IMAGE: https://steemitimages.com/70x80/http://steemitboard.com/notifications/firstpayout.png] You got your First payout

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

> Upvote this notification to help all Steemit users. Learn why here!

@kdj | March 25, 2018, 1:05 p.m. | Votes: 0 | [ VOTE ]

위 알고리즘은 O(N)으로 보이지만, arr.includes(letter) 때문에 N^2입니다. O(N) 으로 줄일 수 있는 방법이 있습니다.
한가지 더 말씀드리면 arr.includes(letter) 면 isogram 이 아니겠지요?

@cheonmr | March 27, 2018, 12:33 a.m. | Votes: 0 | [ VOTE ]

안녕하세요! O(N) 으로 줄일 수 있는 방법이 있다는 게 정확히 무슨 말인가요? 그리고, str에서 반복되는 문자가 있는지 나중에 length로 확인하기 위해, array로 추가하는 방식으로 작성한 것입니다. 위와 같이 해서, 답은 풀렸는데, 혹시 이게 잘못된 해결법일까요?

@kdj | March 27, 2018, 2:17 a.m. | Votes: 0 | [ VOTE ]
  1. 알고리즘을 배우기 전에 시간복잡도에 대해서 알아야 합니다.
    문자열길이가 100이라면 N 과 N^2 이 차이가 미미하지만 길이가 1억이라면 후자의 알고리즘 복잡도라면 컴퓨터가 풀 수 없을 수도 있습니다. (이 문제의 경우는 아니지만 ^^)
    알고리즘은 맞고/틀리고도 있지만 제한된 시간에 답이 나오고 안 나오고 있습니다.

  2. 알파벳과 같이 한정된 갯수에 대한 있다/없다 등을 처리하기 위해서는 비트마스크를 씁니다.
    비둘기집의 원리에 의하면 소문자의 모든 갯수보다 문자열이 크다면 적어도 하나의 문자가 중복되어있을 겁니다.

@cheonmr | March 28, 2018, 4:29 a.m. | Votes: 0 | [ VOTE ]

아 그렇군요! 좋은 내용 감사드립니다! 현재는 기초적인 알고리즘부터 정리하는 단계라 아직 시간복잡도나 비트마스크 관련해서는 공부를 못했습니다. 이런 부분들을 알고리즘을 공부하면서 동시에 공부하는게 좀 더 나을까요?

[ BACK TO TRENDING ] [ BACK TO MENU ]
CMD>