4개의 댓글이 있습니다.
-
-
Being -
- 문자열과 어떤 정수 사이에 일대일 대응을 만든 것뿐인데 무슨 의미가 있을까요? 잘 생각해보시면 부분문자열을 취한것이나 다를 바 없습니다.
- 시간복잡도 분석을 할 때에는 어떤 계산 모델을 가정하는데요, 이를테면 곱셈은 상수시간이 드는 연산으로 정의하는 식입니다. 우리가 사용하는 실제 시스템에서도 그렇기는 하지만 중요한 가정이 있지요. 32비트정수, 64비트 정수 같은 것에 대해서 상수 시간이 드는 것이지, 임의의 길이를 가지는 정수의 곱셈이 상수 시간이라고 말할 수는 없는 것입니다.
- 자명하게 쉬운 문제는 아니니 해법에 대해서는 조금 더 고민해보시기를 권합니다. 떠오르지 읺으신다면 다른 쉬운 문제를 먼저 해결해보시는 편이 좋겠습니다.
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
gwpark
NAMING 처음에 문제 읽고
O(n^2)으로는 안풀리겠구나라고 생각했습니다.
그래서 생각한게 문자열을 정수로 만들어버리자는 것입니다.
이렇게 하면 O(n)으로 풀 수 있겠다라고 생각했습니다.
a가 0, b가 1, c가 2, ... z가 25라고 놓고
26진수처럼 취급해서요.
예를 들자면,
clclc가 있을 때
c c
EXP = 1
LEFT = 2
RIGHT = 2 => 수치가 동일하므로 조건 성립 (길이 1)
cl lc
EXP = EXP * 26 = 26
LEFT = (LEFT * 26) + 11 = 63
RIGHT = (11 * EXP) + RIGHT = 288 => 조건 미성립
clc clc
EXP = EXP * 26 = 676
LEFT = (LEFT * 26) + 2 = 1640
RIGHT = (2 * EXP) + RIGHT = 1640 => 조건 성립 (길이 3)
............
이렇게 하게 되면 이론상 O(n)으로가 나오지만
실제로 문제가 되는 부분은 LEFT와 RIGHT를 저장할 수 있는
마땅한 데이터 타입을 찾기가 힘들다는 것입니다.
400,000자가 들어올 경우 26^400000을 감당할 수 있는
변수가 있을리가...
그래서 java.math.BigDecimal을 썼습니다.
거의 무한대까지 확장 가능한 것으로 알고 있거든요.
근데 이건 연산 속도가 헬이라서 답은 나올진 몰라도
시간초과가 나와버리네요 ㅠㅠ
제 질문은...
(1) 너무도 단순하고 간단하지만, 이런 기법이 알고리즘으로서의 가치가 있을까요?
(2) 과연 제가 이 알고리즘이 time complexity가 O(n)이라고 주장한다면 타당할까요?
(3) 이 문제를 O(nlogn) 또는 O(n)으로 효율적으로 풀 수 있는 알고리즘엔 무엇이 있나요?
답변 부탁드립니다. 감사합니다.
10년 전