기본기부터시작하는 IT생활

백준 1474번

• 이 문제는 다 풀어놓고 js 특유의 입력값을 받는 방식을 잘못설정하여 한참을 헤맸던 문제이다...

https://www.acmicpc.net/problem/1475

맨처음 제출한 코드

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split(' ');

//입력값 가공
let target = [];
for(let i = 0;i < input[0].length;i++){
    target.push(input[0][i]);
}


//각각의 번호가 몇번필요한지 종합할 배열 생성
let numbers = [0,0,0,0,0,0,0,0,0,0];
for(let i = 0; i < target.length; i++){
    numbers[Number(target[i])]++;
}

//6과 9는 하나로 생각해도 되므로 둘을 합친뒤 /2 그리고 반올림
let sixNine = Math.ceil(((numbers[6] + numbers[9])/2));
numbers[6] = sixNine;
numbers[9] = sixNine;

let set = Math.max(...numbers);

console.log(parseInt(set));

처음 이 문제를 보았을때 떠올린 풀이방법은 위 아래와 같다.

1. 입력받은값을 배열로 변환한다.

2. 필요한 0~9의 개수를 저장할 배열을 만든다.

3. 입력받은값을 for문을 통하여 2에서 만든 배열에 각 숫자에 해당하는 index를 ++ 해준다.

4. 6과 9는 서로 바꾸어 쓸 수 있으므로 둘을 합친뒤 / 2 그리고 반올림을 해준다.(반올림 하는 이유는 6과 9의 합이 홀수

    경우 .5 가 생기지만 이는 세트 하나를 더 챙겨야하기 때문)

5. 2에서 만든 배열의 최댓값을 구해주면 끝

나는 위 코드를 만들고 모든 반례가 정상적으로 정답이 나오지만 코드를 제출할때마다 입구컷을 당하는 상황을 보고 정신이 나가는줄 알았다..코드는 아무리 봐도 잘못된 부분이 없었고 이 근거로 어떠한 반례를 찾을 수가 없었다. 

정답으로 제출한 코드

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim();

let word = input.toString();

let target = [];
for(let i = 0;i < word.length;i++){
    target.push(word[i]);
}

let numbers = [0,0,0,0,0,0,0,0,0,0];
for(let i = 0; i < target.length; i++){
    numbers[Number(target[i])]++;
}

let sixNine = Math.ceil(((numbers[6] + numbers[9])/2));
numbers[6] = sixNine;
numbers[9] = sixNine;

let set = Math.max(...numbers);

console.log(set);

기존코드가 입구컷을 당하는 문제는 입력값을 받는 방식에 있었다. js는 입력값을 받는것이 다른 언어들에 비해 어렵다. 백준을 처음 시작한만큼 아직 입력값을 받는데 익숙치 않아서 많이 헤맸던거 같다.

기존코드가 입구컷을 당하는 이유는 입력값을 받는 부분에서 .trim() 을통해 공백을 지워주지 않아 숫자형으로 처리해야하는 데이터에 오류가 발생했던거 같다. 제출할때는 따로 출력값을 볼 수 없어 확신할 수 없지만 그것이 코드제출에서 입구컷을 당한 이유에 가장 가능성이 높아보인다. 

• 백준 2563번 문제는 색종이가 여러번 겹쳤을경우 해당 겹친부분을 여러번 계산하여 결과값이 음수가 되는 현상을 해결하지 못하여 오래 해멨던 문제이다.

https://www.acmicpc.net/problem/2563

맨 처음 제출한 코드

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let paperNum = +input[0];
let paperXy = [];
let result = 100 * paperNum;
let sameRec = 0;

for(let i = 1; i< input.length;i++){
    paperXy.push(input[i].trim().split(' '));
    paperXy[i-1][0] = parseInt(paperXy[i-1][0]);
    paperXy[i-1][1] = parseInt(paperXy[i-1][1]); 
}

//겹치는 부분 계산후 결과값에서 감소
const checkArea = (leftRec,rightRec) => {
    if((leftRec[0] + 10) > rightRec[0]){
        let bottom = (leftRec[0]+10) - rightRec[0];
        let left = 0;
        if(leftRec[1] > rightRec[1]){
            left = (rightRec[1]+10) - leftRec[1];
        }
        else{
            left = (leftRec[1] + 10) - rightRec[1];
        }
        result -= bottom*left;
    }
}

//겹치는지 확인후 겹쳤을경우 checkArea 함수 호출
for(let i = 0; i < paperXy.length; i++){
    for(let j = i+1; j < paperXy.length; j++){
    	//같은 위치의 도형일경우 인덱스에서 제거
        if((paperXy[i][0] == paperXy[j][0]) && (paperXy[i][1] == paperXy[j][1])){
            paperXy.splice(j,1);
            sameRec++;
            j--;
        }
        else if(paperXy[i][0] > paperXy[j][0]){
            checkArea(paperXy[j],paperXy[i]);
        }
        else{
            checkArea(paperXy[i],paperXy[j]);
        }
    }
}

console.log(result - (sameRec*100));

위 코드를 작성하면서 내가 생각했던 풀이 방식은 아래와 같다.

일단 색종이가 서로 겹치지 않았을경우의 최댓값을 결과값으로 정해놓는다.

예를들어 색종이 4장을 놓는다면 결과값이 400으로 정해놓는것이다.

그 이후 이중포문을 활용하여 사각형끼리 겹치는 부분이 있는지 확인한다.

이때 완전히 겹치는 도형이 들어올 수 있다.

이럴경우 이 겹치는 도형을 제거하지 않을경우 결과값을 중복감소하여 데이터 오류로 이어질 수 있기때문에 이를 조건문을 통해 인덱스에서 제거해주고 sameRec 이라는 변수를 증가시켜 나중에 결과값에 적용시켜주었다.

이렇게하면 될줄 알았지만 하나의 반례를 넘지 못했다.

4

1 1

1 2

2 1

2 2

위 반례에서 4개의 사각형이 서로 겹치는 구조인데 위 코드로는 중복된 구역을 계산하여 결과값에서 감소만 시키기때문에 결과값이 음수가 나온다. 따라서 위 방법으로는 문제를 풀지 못한다는걸 알았다. 이때 맨땅에 헤딩하는 식으로 좌표값을 일일히 계산해야하는건가 라는 생각에 머리가 아찔했다. 

정답으로 제출한 코드

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let paperNum = +input[0];
let paperXy = [];

//색칠
let filled = false;
let result = 0;

//큰사각형
let wholeRec = new Array(101);

//큰 사각형에게 2차원배열을 추가
for(let i = 0;i<wholeRec.length;i++){
    wholeRec[i] = new Array(101);
}

//2차원배열안을 채움
for(let i = 0; i < wholeRec.length; i++){
    for(let j = 0;j < wholeRec.length;j++){
        wholeRec[i][j] = [i,j,filled];
    }
}

//입력받은값 가공
for(let i = 1; i< input.length;i++){
    paperXy.push(input[i].trim().split(' '));
    paperXy[i-1][0] = parseInt(paperXy[i-1][0]);
    paperXy[i-1][1] = parseInt(paperXy[i-1][1]); 
}

//입력받은 사각형에해당되는 범위 색칠
for(let i = 0; i < paperXy.length; i++){
    let x = paperXy[i][0];
    let y = paperXy[i][1];
    for(let j = x; j < x+10; j++){
        for(let k = y; k < y+10; k++){
            wholeRec[j][k][2] = true;
        }
    }
}

//색칠이 되어있을경우(true 일경우) result++
for(let i = 0; i < wholeRec.length; i++){
    for(let j = 0;j < wholeRec.length;j++){
        if(wholeRec[i][j][2]){
            result++;
        }
    }
}
console.log(result);

머리를 싸매고 고민에 고민을 하던중 이 문제를 색칠놀이 라고 생각하면 어떨까 라는 아이디어가 떠올랐다.

일단 문제에서 큰 사각형의 크기를 100 * 100으로 지정해놓았으므로 위 크기를 가지는 이중배열을 만들고 각 칸에 boolean false값을 저장한다.

그 다음 입력받은 사각형의 범위를 true로 바꾸는 방식이면 복잡한 계산을 거치지 않고 겹치는 부분도 색칠위에 색칠을 하는것이므로 까다롭게 생각해줄 필요가 없다고 생각했다.

겹치는부분은 상관하지않고 그저 입력받은 사각형 범위를 모두 색칠만 해주면 되는것이다. 

백준 1312번

• 1312번 문제는 처음에 풀이방법을 완전히 잘못잡아 한참 헤맸던 문제이다. 

https://www.acmicpc.net/problem/1312

맨 처음으로 작성한 코드

let fs = require('fs');
let input = fs.readFileSync('./input.txt').toString().split(' ');

let num = Number(input[0]) / Number(input[1]);
let target = Number(input[2]);

let left = Math.floor(num * Math.pow(10,target));
let right = Math.floor(num * Math.pow(10, target-1));


let result = Math.floor(left - right*10);
console.log(result);

처음엔 이 문제가 굉장히 쉽다고 생각했다. 내가 생각한 문제의 풀이방법은 아래와 같다.

입력이 25 7 5 일경우

25 / 7 = 3.571428571428571 

이때 5번째 소수점을 구해야하는것이므로 한 변수는 10^5를 곱하고 나머지 한변수에는 그보다 하나 낮은 10^4를 곱하여

357142 - (35714 * 10) 의 형태를 만들어서 계산하면 원하는 답인 2가 나온다.

하지만 위 방법으로 수많은 반례를 마주했다. 이 문제는 부동소수점으로부터 시작된다. 위 방법에대한 반례는 아래와 같다.

입력이 1 3 19 일경우

1 / 3 = 0.3333333333333333 이라는 무한 소수가 생성된다. 

이때 위 방법대로 계산하게 되면 3 이 아닌 0이라는 값을 얻게된다. 

이는 컴퓨터가 계산하면서 미세한 오차가 발생하기 때문이다.

하나의 예시로 계산하는 중간과정에서 left와 right의 값을 출력해보면 아래와 같은 상태가된다.

즉, 위 풀이방법과 같이 한번에 나눠서 계산을 하고자 하면 넘치는 무한소수로인해 제대로된 데이터를 얻어낼 수 없게된다. 풀이방법이 처음부터 틀렸다는것을 모르고 많은 시간을 저 방대한 양의 데이터를 어떻게 처리할지 고민했다..

정답으로 제출한 코드

• 문제 해결방안의 핵심 키는 나머지연산에 있다. 한번에 나누는것이 아닌 하나씩 차례대로 갉아먹는 느낌으로 처리하는 것이다. 우리가 높은 수의 나눗셈을 수기로 계산한다고 생각해보자. 우리는 10자리를 구하고 그 나머지를 나누어 1의자리를 구하고,또 그것을 나누어 첫번째 소수를 구하고,또 반복하며 2번째,3번째 소수 등등 순차적으로 구해나간다. 그것이 이 문제 풀이법의 핵심이다. 아래는 필자가 작성한 정답코드이다.

let fs = require('fs');
let input = fs.readFileSync('./input.txt').toString().split(' ');

let target = Number(input[2]);
let left = Number(input[0]);
let right = Number(input[1]);
let result = left;

for(let i = 0; i < target; i++){
    result %= right;
    result *= 10;    
}

console.log(Math.floor(((result/10)/right)*10));

하나의 예시를 잡고 천천히 코드를 따라가보자. 

아까의 반례였던 1 3 19를 예시로 들겠다.

1 % 3 = 1이다.

여기서 몫은 0 나머지가 1인것이다.

우린 1의자리의 숫자를 구한것이다. 이제 소수점 첫번째자리를 구하려면 *10을 해준뒤 다시 나누어주면된다.

10 % 3 = 1

몫은 3, 나머지는 1

이때 소수점 첫번째 자리가 3인것이다. 이 작업을 총 19번 반복해주면 된다.

19번의 반복이 끝나면 이제 우리는 나머지가 아닌 몫을 구해주면된다.

하지만 필자는 반복문에서 *10을 한채 마무리되기떄문에 19번의 반복이 끝났을때  result의 값이 10이된다.

따라서 이를 10을 다시 나눠준뒤 3과 나누어주면 0.333333.. 이 될것이다. 이때 소수점 첫번째 자리가 19번째 소수이므로 *10을 해주고 Math.floor를 사용하여 나머지 소수를 버려주면 우리가 원하는 값을 얻을 수 있다.

느낀점

• 해당 문제를 풀면서 방향을 잘못잡았다는걸 몰랐을때 많이 당황스러웠고 어떤 방법을 써도 항상 데이터의 오차로인한 문제가 발생하는걸 막을 수 없었다. 그래서 부동소수점에대한 많은 구글링을 하는 도중에 toFixed() 를 사용해도 100번째 소수점까지 밖에 처리를 못한다는것을 알았을때 무언가 잘못되었다는걸 알았다. 찾아야되는 물건이 들어있는 박스를 한번에 뒤집어놓고 그안에서 물건을 찾으려 했다는걸 알았고 하나씩 천천히 꺼내면서 찾아보면 어떨까 하는 생각이 들었다. 그 결과 데이터의 오차는 없었고 보다 깔끔한 코딩을 할 수 있었다. 이 문제로부터 데이터를 처리하는 순서에대한 중요성을 알게된거 같다.