[프로그래머스 | 파이썬 / 자바스크립트] 겹치는 선분의 길이(코딩테스트 입문/ level 0)

문제

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

프로그래머스

 

 

🐍파이썬

def solution(lines):
    answer = 0
    setArr = [0 for _ in range(200)]
    for i in lines:
        for j in range(i[0] ,i[1]):
            setArr[j + 100] += 1
    return setArr.count(2) + setArr.count(3)

1️⃣ 문제조건 중 -100 ≤ a < b ≤ 100라는 조건이 존재하기 때문에, 점 a와 b가 존재할 수 있는 200개의 공간을 만들고 모두 0으로 초기화한다.

2️⃣ for문을 돌며 a부터 b까지 배열의 값을 카운팅한다. 음수가 존재하기 때문에 100을 더해 처리한다.

(ex. -100 👉 0, -20 👉 80, 30 👉 130, 100 👉 200)

🚨 이때 중요한 것이 b 인덱스는 카운팅에 포함하지 않는다는 것이다. 선분 2, 3, 4가 겹친다고 했을 때, 겹치는 길이는 2로 처리되기 때문에 카운팅에 b를 포함하면 오답이 뜬다. 이를 해결하기 위해 카운팅 때부터 마지막 b인덱스에는 1을 추가하지 않는 방법으로 처리했다.

3️⃣ 2번 이상 카운트 된 선분은 겹치는 선분이고, 3개의 선분은 최대 3개까지만 겹칠 수 있기 때문에 2, 3을 카운트한 값을 정답으로 리턴했다.

 

 

다른 풀이 방법

def solution(lines):
    sets = [set(range(min(l), max(l))) for l in lines]
    return len(sets[0] & sets[1] | sets[0] & sets[2] | sets[1] & sets[2])

각 lines의 원소로 이루어진 set을 3개 만든 후 sets[0], sets[1] / sets[0], sets[2] / sets[1], sets[2]의 교집합을 합집합으로 더한 뒤 그 집합의 길이를 출력

ex) lines = [[0, 5], [3, 9], [1, 10]]
sets = [{0, 1, 2, 3, 4}, {3, 4, 5, 6, 7, 8}, {1, 2, 3, 4, 5, 6, 7, 8, 9}]
sets[0] & sets[1] = {3, 4}
sets[0] & sets[2] = {1, 2, 3, 4}
sets[1] & sets[2] = {3, 4, 5, 6, 7, 8}
sets[0] & sets[1] | sets[0] & sets[2] | sets[1] & sets[2] = {1, 2, 3, 4, 5, 6, 7, 8}

 

 

🐥자바스크립트

function solution(lines) {
    let answer = Array(200).fill(0);
    let cnt = 0;
    for(let i of lines){
        for(let j = i[0]; j < i[1]; j++){
            answer[j + 100]++;
            if(answer[j + 100] === 2){ cnt++; }
        }
    }
    return cnt;
}

파이썬 풀이와 동일하게 풀었다.

1️⃣ 문제조건 중 -100 ≤ a < b ≤ 100라는 조건이 존재하기 때문에, 점 a와 b가 존재할 수 있는 200개의 공간을 만들고 모두 0으로 초기화한다.

2️⃣ for문을 돌며 a부터 b까지 배열의 값을 카운팅한다. 음수가 존재하기 때문에 100을 더해 처리한다.

(ex. -100 👉 0, -20 👉 80, 30 👉 130, 100 👉 200)

🚨 이때 중요한 것이 b 인덱스는 카운팅에 포함하지 않는다는 것이다. 선분 2, 3, 4가 겹친다고 했을 때, 겹치는 길이는 2로 처리되기 때문에 카운팅에 b를 포함하면 오답이 뜬다. 이를 해결하기 위해 카운팅 때부터 마지막 b인덱스에는 1을 추가하지 않는 방법으로 처리했다.

3️⃣ 2번 이상 카운트 된 선분은 겹치는 선분이기 때문에 카운트가 2번 된 인덱스를 발견하면 cnt변수에 1을 추가한다.

 

 

다른 풀이 방법

function solution(lines) {
    let line = new Array(200).fill(0);
    lines.forEach(([a, b]) => {
        for(; a < b; a++) line[a+100]++;
    });
    return line.reduce((a, c) =>  c > 1 ? a + 1 : a, 0)
}

return line.reduce((a, c) =>  c > 1 ? a + 1 : a, 0)

현재 값이 1보다 크면 누적값+1을 수행하고, 1보다 작으면 누적값에 아무것도 더하지 않는다.

 

💡 참고

for문 생략

https://seoyun-is-connecting-the-dots.tistory.com/46

[자바 프로그래밍] 19. 반복문 - for문