코드스테이츠 SEB 21일차 TIL - 리액트 state & props / 알고리즘 문제 풀이

자율학습 코딩봇 2021. 8. 17. 21:51

지난 주 금요일에 이어서 오늘은 리액트의 State와 props에 관해서 과제형태로 수행하는 스프린트를 진행했다. 그래서 사실 오늘은 크게 새롭게 배운 내용이 없어서 블로그에 포스팅하기가 애매했는데 일단 그래도 적어보려고 달려왔다.

그리고 사실 내일 시험이 있는데 부트캠프 과정 내에서 Hiring Assessment라고 지난 시간동안 학습한 내용들이 제대로 숙지되었고 다음 간계로 넘어가도 되는지 점검하는 시험으로 설명되고 있다. 6월쯤에 대학에서 마지막 기말시험을 보고 이제 인생에서 시험을 볼 건 먼 미래일줄 알았는데... ㅎ. 단 2개월만에 다시 시험 준비하는 사람이 되어있다.

내일 시험을 앞두고 오늘은 리액트를 활용한 state와 props 과제를 수행하는 데에 있어서 6시간이나 부여되었다. 나 같은 경우에는 어제 휴일에 미리 페어와 만나서 과제를 풀어서 오늘은 자습할 시간을 벌었다. 그래서 어느 정도 리액트는 손에 익은 듯 하여 알고리즘 공부를 보강하는 의미에서 리액트를 잠깐 보고 알고리즘 문제를 다시 보았다.

프로그래머스 - '모의고사'

알고리즘 문제를 찾아보던 중에 프로그래머스에 알고리즘 문제들이 올라와있는 것을 알게되어서 최근엔 여기서 공부를 좀 하고 있는데 문제이름이 '모의고사'다. 그래서 어찌되었든 간에 관련 문제를 아래와 같이 가져와봤다.

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

시험은 최대 10,000 문제로 구성되어있습니다.
문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

좌 answers / 우 return

[1,2,3,4,5]	[1]
[1,3,2,4,2]	[1,2,3]

이 문제를 처음 봤을 때 든 기분은 굉장히 로직이 어려운 문제는 아닌데 귀찮은 문제라고 생각이 들었다. 알고리즘 효율 측면에서는 반복문을 2회만 돌려서 풀 수도 있을 것 같긴 했는데 이게 그렇게 귀찮은 경우가 아닐 수 없다. 그래서 그냥 반복문을 4번 정도 활용하는 방향으로 생각을 고쳐먹었다. 어차피 최대 1만개의 문제라고 하는데 단순 정수 모임에 1만개에 대한 반복문 4번이면 앵간한 컴퓨터라면 연산 가능할거야! (믿고 있다고!)

우선은 위 문제에서 가장 먼저 확인해야되는 것은 각 수표자 친구들이 문제를 찍는 패턴이다. 각 수포자들마다 문제를 찍어주는 패턴의 차이가 발생하므로 답안과 대조할 때의 패턴을 파악해야 한다. 그리고 문제를 풀 당시에 일단은 문제를 빠르게 패스하기 위해서는 내가 시각적으로 파악이 유의한 방향으로 우선 코드를 작성하는 방향으로 진행되어야 한다. 괜히 알고리즘 효율을 지나치게 걱정해서 코드가 어떻게 진행될지 감조차 잡히지 않으면 나중에 코드 엎어야 한다.

앞서 언급했던 반복문 2회 방식에서는 이 패턴과 답안을 바로 대조하는 방식이 적용되어야 하는데 이건 아무리 생각해도 조건문을 여기저기 붙여서 해야되므로 나중에 꼬이면 나도 길을 잃기 쉬울 듯하여 반복문을 여러번 쓰더라도 눈으로 쉽게 쫓아갈 수 있는 방향을 택했다.

눈으로 쉽게 쫓을 수 있는 방법은 먼저 각 수포자 친구들이 답안을 작성하는 패턴에 맞추어 제출했을 답안을 확보하는 것이다. 이 문제에서 정답이 순서대로 들은 배열 answers가 주어지므로 answers의 길이는 즉 문제의 길이고 수포자 친구들이 제출하는 문제의 총 수를 의미한다. 그래서 그에 맞게만 패턴을 반복해주면 된다.

이러한 수포자 친구들이 제출한 답안을 확보하는 함수 코드 내용은 아래와 같다.

function solution(answers) {
    
    let patternFirst = [1, 2, 3, 4, 5]; // 1번의 패턴
    let patternSecond = [2, 1, 2, 3, 2, 4, 2, 5]; // 2번의 패턴
    let patternThird = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]; // 3번의 패턴
    
    
    // 아래 수포자들의 답안을 확보할 함수 선언
    const getAnswersOfTester = (pattern, answers) => {
        let numOfLoop = parseInt(answers.length / pattern.length); // 패턴을 full로 반복할 횟수
        let restOfLoop = answers.length % pattern.length; // 패턴을 full 반복하고 남은 문제 객수
        let answersOfTester = []; // 답안이 담길 변수
        
        // 반복문을 통해서 full 패턴을 위 numOfLoop 횟수만큼 배열에 채움
        for (let i = 0; i < numOfLoop; i++) {
            answersOfTester = [...answersOfTester, ...pattern];
            }
        // full 패턴 횟수가 아닌 남은 잔여 문제만큼의 찍기 내용을 배열에 채워줌
        answersOfTester = [...answersOfTester, ...pattern.slice(0, restOfLoop)];
          
        return answersOfTester;
    }
    
    
    // 각 수포자들의 답안을 위 함수를 활용하여 할당
    let answersOfFirst = getAnswersOfTester(patternFirst, answers);
    let answersOfSecond = getAnswersOfTester(patternSecond, answers);
    let answersOfThird = getAnswersOfTester(patternThird, answers);
    
}

각 수포자마다 패턴에서의 최대길이가 다르다. 1번은 1, 2, 3, 4, 5 순서로 반복되는 패턴을 가지고 있고 2번은 2, 1, 2, 3, 2, 4, 2, 5 순서로 반복되는 총 8개 길이의 패턴을 가지고 있다. 때문에 이러한 점을 고려해 getAnswersOfTester 함수 내에서 각 패턴의 길이로 answers의 길이를 나누고 그 결과 값을 parseInt를 통해 정수처리하여 풀 패턴으로 반복을 돌릴 길이를 뽑았다. ~~(생각해보니 이 정도면 각 수포자들마다 최대 1만개의 풀 반복문이 돌아간 것이 아니라서 나름 개꿀?)~~ 그리고 풀 패턴 반복 외에도 문제 길이가 11문제라면 1번은 2회 패턴 반복하고 남는 나머지 값이 1이 생긴다. 그렇기에 이에 대한 풀 패턴으로 제외하고 남는 나머지 값도 뽑고 그에 맞춰 패턴에 slice를 활용하여 answers의 길이 만큼 제출했을 각 수포자들의 답안을 확보할 수 있었다.

이렇게 한번 확보만 되면 굉장히 쉬워진다. 그냥 답안과 수포자들의 제출안을 비교하여 제점해주면 된다.

	
    // 각 수포자들의 점수를 담을 변수
    let scoreOfFirst = 0;
    let scoreOfSecond = 0;
    let scoreOfThird = 0;

	// 채점 반복문
    for (let i = 0; i < answers.length; i++) {
        if (answers[i] === answersOfFirst[i]) {
            scoreOfFirst += 1
        };
        if (answers[i] === answersOfSecond[i]) {
            scoreOfSecond += 1
        };
        if (answers[i] === answersOfThird[i]) {
            scoreOfThird += 1
        };
    }
    
    // 최고점수
    let highestScore = Math.max(scoreOfFirst, scoreOfSecond, scoreOfThird)
    
    // 최고 성적 수포자를 담을 배열
    let bestTester = []
    
    // 최고점수와 수포자들의 점수를 대조하여 최고 성적 수포자 배열에 추가
    if (highestScore === scoreOfFirst) {
        bestTester.push(1)
    }
    if (highestScore === scoreOfSecond) {
        bestTester.push(2)
    }
    if (highestScore === scoreOfThird) {
        bestTester.push(3)
    }

위 코드 구간에서는 filter 메소드 혹은 reduce 메소드를 활용하여 제출한 답안의 정답 여부와 점수를 뽑아볼 수도 있다. 다만 배열 메소드를 사용할 시에는 시간복잡도에서 영향이 생길 것으로 생각했다.

(요 문제 내에서 시간복잡도 적용은 나도 정확한 계산이 안되기 때문에 누군가 아는 사람이 있다면 알려주면 좋겠다.)
시간복잡도 개념으로 보통 전체 배열을 1회 루프하는 반복문에서의 Big O(n)이라는 알고리즘의 효율 개념이 생기는데 위와 같이 1회 반복문 안에서 조건문 검증을 3회 진행하는 것은 중요하지 않다. 그렇지만 배열 메소드를 활용하게 되면 각 수포자들의 제출답안 마다 배열 메소드를 활용하게 되는데 이는 n * n * n 의 시간소요가 발생된다. (n은 최대 배열 길이를 의미) 즉 Big O(n^3)이 된다. 거기다가 내가 각 수포자들의 답안 전문을 뽑는데 사용한 반복문이 있는데 위의 것은 패턴길이만큼 나눈 값만 반복되어서 정확하게 Big O(n^3)가 성립되지는 않지만 배열 메소드는 그 자체만으로 시간복잡도를 증진시킨다. (애초에 배열을 한번 싹 돌도록 설계되었기 때문) 그래서 우선은 최대한 반복문을 여러번 사용하지 않는 방향으로 채점부분은 코드를 작성하였다.

전체 코드는 아래와 같다.

function solution(answers) {
    
    let patternFirst = [1, 2, 3, 4, 5];
    let patternSecond = [2, 1, 2, 3, 2, 4, 2, 5];
    let patternThird = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
    
    const getAnswersOfTester = (pattern, answers) => {
        let numOfLoop = parseInt(answers.length / pattern.length);
        let restOfLoop = answers.length % pattern.length;
        let answersOfTester = [];
        
        for (let i = 0; i < numOfLoop; i++) {
            answersOfTester = [...answersOfTester, ...pattern];
            }
        answersOfTester = [...answersOfTester, ...pattern.slice(0, restOfLoop)];
          
        return answersOfTester;
    }
    
    let answersOfFirst = getAnswersOfTester(patternFirst, answers);
    let answersOfSecond = getAnswersOfTester(patternSecond, answers);
    let answersOfThird = getAnswersOfTester(patternThird, answers);
    
    let scoreOfFirst = 0;
    let scoreOfSecond = 0;
    let scoreOfThird = 0;

    for (let i = 0; i < answers.length; i++) {
        if (answers[i] === answersOfFirst[i]) {
            scoreOfFirst += 1
        };
        if (answers[i] === answersOfSecond[i]) {
            scoreOfSecond += 1
        };
        if (answers[i] === answersOfThird[i]) {
            scoreOfThird += 1
        };
    }
    
    let highestScore = Math.max(scoreOfFirst, scoreOfSecond, scoreOfThird)
    let bestTester = []
    
    
    if (highestScore === scoreOfFirst) {
        bestTester.push(1)
    }
    if (highestScore === scoreOfSecond) {
        bestTester.push(2)
    }
    if (highestScore === scoreOfThird) {
        bestTester.push(3)
    }
    
    
    return bestTester;
}