프로그래머스 [Lv. 2] 예상 대진표 {언어 : JavaScript}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12985

프로그래머스

정답 코드

function solution(n,a,b) {
    let answer = 0;
    let visited = Array(n).fill(1).map((e, i) => e + i);
    let lenQ = n
    while (lenQ != 1) {
        answer += 1;
        let idx = 0;
        let isBreak = false;
        while (idx < lenQ/2) {
            const first = visited[idx*2];
            const second = visited[idx*2+1]
            if ((first == a && second == b) || (first == b && second == a)) {
                isBreak = true;
                break;
            };
            if (first == a || second == a) {
                visited[idx] = a;
            } else if (first == b || second == b) {
                visited[idx] = b;
            } else {
                visited[idx] = first;
            };
            idx += 1;
        };
        if (isBreak) {
            break;
        };
        lenQ /= 2;
    };
    return answer;
}

풀이 방법

1. visited에 1부터 N까지 저장한다.
2. first와 second가 a와 b 즉 a 와 b가 만날 때까지 반복시킨다.
3. 반복할 때마다 경기 수가 반토막 나기 때문에 lenQ를 2로 나눈다.
4. 편의상 a와 b를 제외하고 앞 사람이 이기게 했다. 다른 사람의 승패는 관심 없음 
5. 결과적으로 경기가 2개 일떄 끝나게 했지만 혹시 몰라서 1이 되면 반복문이 종료하게 했다.
6. answer에 경기가 시작할 때마다 더해줬으므로 반환하면 답이 된다.

느낀점

• 처음에 q를 사용해서 경기가 시작하면 shift를 통해 빼주고 끝나면 push를 통해 넣어줬다.
  • 이 방식의 문제점은 시간복잡도가 O (N log N) 일 것이다. 그래서 시간초과가 발생했다.
• push 와 shift를 사용하지 않고 푸는 방법을 고안했고 그 결과는 다음과 같다.