You are viewing a single comment's thread from:
RE: [JS 알고리즘 문제] #2 Isograms
안녕하세요! O(N) 으로 줄일 수 있는 방법이 있다는 게 정확히 무슨 말인가요? 그리고, str에서 반복되는 문자가 있는지 나중에 length로 확인하기 위해, array로 추가하는 방식으로 작성한 것입니다. 위와 같이 해서, 답은 풀렸는데, 혹시 이게 잘못된 해결법일까요?
안녕하세요! O(N) 으로 줄일 수 있는 방법이 있다는 게 정확히 무슨 말인가요? 그리고, str에서 반복되는 문자가 있는지 나중에 length로 확인하기 위해, array로 추가하는 방식으로 작성한 것입니다. 위와 같이 해서, 답은 풀렸는데, 혹시 이게 잘못된 해결법일까요?
알고리즘을 배우기 전에 시간복잡도에 대해서 알아야 합니다.
문자열길이가 100이라면 N 과 N^2 이 차이가 미미하지만 길이가 1억이라면 후자의 알고리즘 복잡도라면 컴퓨터가 풀 수 없을 수도 있습니다. (이 문제의 경우는 아니지만 ^^)
알고리즘은 맞고/틀리고도 있지만 제한된 시간에 답이 나오고 안 나오고 있습니다.
알파벳과 같이 한정된 갯수에 대한 있다/없다 등을 처리하기 위해서는 비트마스크를 씁니다.
비둘기집의 원리에 의하면 소문자의 모든 갯수보다 문자열이 크다면 적어도 하나의 문자가 중복되어있을 겁니다.
아 그렇군요! 좋은 내용 감사드립니다! 현재는 기초적인 알고리즘부터 정리하는 단계라 아직 시간복잡도나 비트마스크 관련해서는 공부를 못했습니다. 이런 부분들을 알고리즘을 공부하면서 동시에 공부하는게 좀 더 나을까요?