Happy Programmer

배열에 담긴 각 문자열을 숫자로 바꾸기 위해 .map(Number) 처리를 해주고

해당 배열을 for문으로 접근해 각각을 제곱한 다음 sum이라는 변수에 더하고

최종적으로는 sum%10으로 10으로 나눈 나머지를 출력한다.

const input = require('fs').readFileSync('/dev/stdin').toString().split(" ").map(Number)
let sum = 0

for(let i = 0 ; i < input.length ; i++){
    sum += input[i]**2
}

console.log(sum%10)

const input = '0 4 2 5 6'.split(" ").map(Number)
let sum = 0

for(let i = 0 ; i < input.length ; i++){
    sum += input[i]**2
}

console.log(sum%10)

const input = Number(require('fs').readFileSync('/dev/stdin').toString().trim())
for(i = 1 ; i <= input ; i++){
    console.log('*'.repeat(i))
}

//8개월 전 초반에 시도했던 코드로 .trim이 없어 불편하다.
const input = require('fs').readFileSync('/dev/stdin').toString().split(" ").map(Number)
let a = ''
for(i = 0 ; i < input[0] ; i++){
    a = a+ '*'
    console.log(a)
}

const input = Number('5')
for(i = 1 ; i <= input[0] ; i++){
    console.log('*'.repeat(i))
}

const [a, b] = require('fs').readFileSync('/dev/stdin').toString().split(" ").map(Number)

console.log(Math.abs(a-b))

const [a, b] = '-2 5'.split(" ").map(Number)

console.log(Math.abs(a-b))

const [a,b] = require('fs').readFileSync('/dev/stdin').toString().split(" ").map(Number)

let result
if(a>b){
    result = '>'
}
else if(a===b){
    result = '=='
}
else if(a<b){
    result = '<'
}
console.log(result)

const [a,b] = '10 2'.split(" ").map(Number)

let result
if(a>b){
    result = '>'
}
else if(a===b){
    result = '=='
}
else if(a<b){
    result = '<'
}
console.log(result)

입력값이 10의 1000제곱이기 때문에 number type에서는 감당할 수 없고

큰 수는 모두 BigInt를 사용해야만 한다.

그렇기 때문에 일반적으로 BigInt값으로 변환해서 써야 하기 때문에

기존의 .map(Number) 대신 .map(BigInt)를 사용했다.

BigInt의 형태는 1n 2n 3n 등 뒤에 n이 붙어있는 형태로

원하는 출력 형태인 숫자와는 다른 모습을 가지고 있기 때문에

String으로 감싸는 등 문자열로 바꿔줘야 n이 제거된다.

또한 BigInt는 +, -, *, **, %연산을 정상적으로 처리하지만

나누기 연산(/)은 제대로 처리하지 못하는데

MND를 참고하자면 아래의 설명과 같이 소수점이하가 사라진다는 것을 알 수 있다.

마지막으로 백준 문제를 풀면 주의해야 하는 점이 있는데 바로 .trim()이다.

백준에서는 input값을 지 멋대로 넣어주기 때문에 '12 23'과 같은 형태로 들어올 것이라고 기대하지만

' 12 34' 또는 '12 34 '처럼 앞뒤에 마음대로 공백이 들어올 수 있고 

그런 경우 input이 이상하게 들어와서 ["", "a", "b"] 형태로 배열이 되어버리고

구조분해할당 또는 a = input[0]과 같은 형태로 값을 받을 경우 엉망이 되는 것을 모르고 

오답이라는 메세지만 반복해서 받으며 포기하고 싶어질 수 있다.

.trim()으로 앞뒤 공백을 제거하는 것을 잊지말자.

const [a,b] = require('fs').readFileSync('/dev/stdin').toString().trim().split(" ").map(BigInt)
console.log(String(a/b))
console.log(String(a%b))

const [a,b] = '1000 100'.split(" ").map(BigInt)
console.log(String(a/b))
console.log(String(a%b))

풀이

A/B는 이전 A+B, A-B와 같이 연산을 해결하면 되는 문제로 

반올림을 요구하거나 소숫점 몇번째 자리까지만 구하라는 출력 형태가 있지 않기 때문에

단순히 입력값을 받아 A/B로 처리하면 해결할 수 있는 문제다.

const [a, b] = require('fs').readFileSync('/dev/stdin').toString().split(' ').map(Number)
console.log(a/b);

const [a, b] = '1 2'.split(' ').map(Number)
console.log(a/b);

풀이

A-B는 또한 A+B와 마찬가지로 단순히 a-b의 연산을 처리해주면 되는 문제로

a-b를 console.log로 출력했다.

이번에도 구조분해 할당을 통해 a,b값을 나눠 출력했다.

또한 이전에는 설명을 까먹었는데 split(' ')을 통해 공백을 제거하고 배열화 했으며

.map(Number)를 통해 각각 Number() 처리를 진행해 string type에서 number type으로 변경했다.

일반적인 백준의 숫자로 된 내용들은 모두 .map(Number)를 사용하는 것이 편리하다.

const [a, b] = require('fs').readFileSync('/dev/stdin').toString().split(' ').map(Number)
console.log(a - b);

const [a, b] = '1 2'.split(' ').map(Number)
console.log(a - b);

A+B는 단순히 a+b의 연산을 처리해주면 되는 문제로

출력을 요구했기 때문에 a+b를 console.log로 출력했다.

다만 입력값을 받아올 때 구조분해할당을 사용해 [a,b]형태로 받아왔다는 것이 차이가 있으며

일반적으로는 const input = xxxx 형태로 받은 다음 input을 다시 가공하는 방식을 사용하기도 한다.

const [a, b] = require('fs').readFileSync('/dev/stdin').toString().split(' ').map(Number)
console.log(a + b);

const [a, b] = '1 2'.split(' ').map(Number)
console.log(a + b);

핵심만 먼저 말하자면 객체의 키/값 추가는 O(NlogN)정도의 시간복잡도를 가진다고 한다.

(정확하지는 않고 O(N)이상의 시간복잡도를 가진다고만 알아둬도 괜찮다)

문제를 풀던 도중 효율성에서 100점을 맞지 못했다.

시간복잡도를 생각하며 문제를 풀었다고 생각했는데 의아했고

다른 방식으로 문제를 풀어 제출했더니 100점이 나왔다.

사실 여기서 중요한 것은 100점이 나왔다는 것이 아니라

더 좋은 시간복잡도를 가지고 있는데 100점이 나오지 않았던 코드였다.

(코드는 하단에 있다)

분명 sort를 사용한 문제는 시간복잡도 O(NlogN)이 나올거고

객체를 사용한 문제는 시간복잡도 O(N)이 나올거라고 생각했는데

아래와 같은 코드 작성을 통해 시간을 계산해봐도 문제는 객체일 수 밖에 없었다.

(sort를 사용한 것이 훨씬 더 빨랐으며 100만단위 규모(문제 사이즈)에서 12배가량 빨랐다)

function solution(A) { //내가 생각하는 O(NlogN)
    let arr = A.sort((a,b) => a-b)
    let start = A.indexOf(1) 
    if(arr.indexOf(1) === -1){
        return 1
    }
    else{
        for(let i = start ; i < arr.length ; i++){
            if(arr[i+1] > arr[i]+1){
                return arr[i]+1
            }
        }
        return arr[arr.length-1]+1
    }
}

function solutionTwo(A) { //내가 생각했던 O(N)
    let obj = {}
    for(let i = 0 ; i < A.length ; i++){
        obj[A[i]] = 1
    }
    for(let i = 1 ; i <= 100000 ; i++){
        if(obj[i] === 0) return i
    }
}
let arr = []
for(let i = 10000000; i > -10000000 ; i--){ //정렬이 우세해서 비정렬 상태로 만들었다
    arr.push(i)
}
let befor = Date.now()
solution(arr)
let after = Date.now()
let beforT = Date.now()
solutionTwo(arr)
let afterT = Date.now()

console.log(after-befor, afterT-beforT)

객체의 시간복잡도를 검색해도 객체 자체에 대한 이야기는 나오지 않았고

오히려 공식문서 등에서는 시간복잡도에 대한 언급조차 되지 않았다.

외국인들이 쓴 칼럼을 봐도 객체 짱짱맨!! 같은 찬양글만 보였을 뿐이고

나와 같은 궁금증을 가진 사람은 없는 것 같았다.

도움의 손길을 찾아보다가 문득 얼마 전 멘토님이 보내주셨던 리뷰에서

부담없이 질문해도 괜찮다는 말씀이 생각났고

질문을 드리니 생각해보지 않았던 말씀을 해주셨다.

시간복잡도 계산에서 조건동일에 대한 부분을 언급하는 것을 본 기억이 없었는데(좀 당연하기도 하지만)

처리갯수(N)과 관련되지 않은 다른 부분에서 동작마다 시간이 다를 수 있다는 것이 새로웠고

그 뒤에 말씀해주신 객체에 값을 추가할 때 정렬된다는 놀라운 사실을 알려주셨다.

결국 객체에 값을 할당하고 읽는 작업에는 우리가 생각하는 O(1)의 시간이 소모되지만

키 자체를 추가하면 재정렬이 계속 들어가기 때문에 O(N?/정렬시간)*O(N/for문 1회)이 진행된 것이었다.

그래서 평소에는 대규모 데이터를 처리하면서 고정된 몇개의 키를 사용했기 때문에 시간복잡도 정렬문제를 겪지 않았고

그로 인해 객체를 맹신하게 된 것이었고

이번에는 모든 값들이 다 달랐기 때문에(내가 만든 수치지만) 정렬을 N번 진행해버리는 참사가 벌어진 것이었다.

대규모 데이터에서 소규모 키 변동인 경우에는 객체가 유리하고

대규모 데이터에서 서로 다 다른 값인 경우에는 객체가 불리한 것이라고 마무리할 수 있다.

(배열에 넣고 정렬때리면 NlogN이지만 정렬해가며 추가하는 것은 N*정렬이기 때문에)

@멘토님의 대화를 보던 중 생각난 포인트 하나 더 추가