생코에서 잼는 문제를 봣음니다.


(ㄴㅂㄷㄱㄷㄱ) #1

정수 배열 arr = [a, b, c, d] 가 있으면

out = [bcd, acd, abd, abc] 를 구하는 문제인데

나눗셈 사용 불가이고, O(n) 이어야 한다고 함니다.

으음…

근데 질문자가 답변을 받아보고는 리플 비공개 처리를 해두었더군요… 글삭 ㅎㄷㄷ

내용이 궁금해서 골똘히 10초 생각하다

저는 댈감이라 관두고 구글을 찾아보앗음니다

재밋네요

혹시 생코에서 답변 비공개 처리되서 저처럼 궁금햇던 분 계실까봐 공유해봄니다


(하하아하) #2

배열의 i번째가 아닐때에만 곱하는건…O(n^2)일까요?


(ㄴㅂㄷㄱㄷㄱ) #3

그럴듯요? for 루프 두번 돈다면…


(P.노우렛지Δ) #4

인성이?


(L) #5

전형적인 DP문제로군요


(Sexydove) #6

어…혹시 1~n중 i기준으로 양쪽쪼개서 for문돌려서 서로 곱하면 O(n)인가요…?


(L) #7

1~n 중 i를 하나 잡아야 하는데 이 때 모든 i에 대해 계산하려면 n번 돌아야겠죠.
각 i마다 왼쪽, 오른쪽을 하나씩 곱해야 하니 배열에서 n-1개의 원소를 봐야겠죠(i번째 뺀 나머지).
n(n-1)이니 O(n^2)입니다.


(바보털) #8

왼쪽으로 곱해나간거 저장하고 오른쪽으로 곱해나간거 저장한 다음에 두개 곱하는거 말씀하시는거 아닐까요? 이건 O(n)


(L) #9

아 그건 그렇겠네요


(프로책팔이) #10

이거 leetcode 에 있었던거 같은데?

그리고 갓갓


(myyh1234) #11

이거 코딩도장에 올려도 되나요?
간단하지만 재밌어 보이는 문제네요


(ㄴㅂㄷㄱㄷㄱ) #12

전 문제에 대한 저작권이 없어서 ㅠㅜ


(ㄷㅅㅂㄱ) #14
var arr = [1,2,3,4];
var str = arr.join("");
var output = [];
for(var i=0;i<arr.length;i++) {
  output.push(Number(str.replace(arr[i],'')));
}
console.log(output);
// 결과
[234, 134, 124, 123]

(ㄷㅅㅂㄱ) #15

풀고나서 stackoverflow 들어가보니 이걸 원하는게 아니였네요.ㅎㅎ;


(ㄴㅂㄷㄱㄷㄱ) #16

이방법으로도 잘하면 풀수 잇을거 같네요 ㄷㄷ