[코드트리 조별과제] +1 -1 테크닉: 가장 많이 겹치는 구간 문제 풀이(Python)

코드트리.. 싸피 같이 한 오빠한테 추천받아서 알고 있긴 했는데, 제휴대학이 아니어서ㅠ 혜택도 못 받고 그래서.. (+뭔가 네트워크 이슈..? 내가 로그인하는데 장애가 있었어서) 한동안 못했다가...! 이번에 조별과제 이벤트를 한다는 소식을 듣고 호다닥ㅎ

짜자잔 이 이벤트랍니다~

 

 

코드트리 방학 조별과제 이벤트가 뭐예요?

1. 학교 이메일이 있으면 참여할 수 있는 무료 이벤트 !
2, 이벤트 참여 기간 동안 모든 코드트리 콘텐츠를 무료로 학습할 수 있어요 (30만원 상당)
3. 우승학교는 2024년이 끝날때까지 코드트리 모든 커리큘럼 무료 사용
4. 5000포인트 모으면 간식차 1대 적립
5. 모든 추첨권으로 경품 추첨에 참여 가능(개인전)

6. 주간레포트를 작성해야 계속 이벤트 참여 가능 !

 

 

이 중에서 참여기간동안 모든 코드트리 콘텐츠를 무료로 학습할 수 있다는 것이 아주아주... 굿인 이벤트..😋

 

 

그래서 이벤트 참여하기 눌러놓고... 이전에 하다 만 진단테스트부터 해봤는데ㅠ 아니 진짜 너무 좋은 것 같다ㅠ

 

진단테스트 끝나고 설명해주는 이... 개념이 너무 좋음🤦‍♀️

저 그거 모르는 거 어케 아셨어요... (당연함 문제 틀림)

 

아무튼 잡설그만하고 이 멋진 코드트리를 찬양하며, 조별과제 레포트를 작성해봅니다^___^

 

왜냐!

같은 학교 참여자 중 10%는 레포트를 내야지 이 이벤트를 계속 해나갈 수 있음! (그 주의 월~일 동안 작성된 공개 게시글만 인정)

만약 이게 충족이 안되어 우리학교가 떨어지더라도, 레포트 제출자는 교육자료를 제공받을 수 있음!

 

정말... 잘 짠 이벤트라고 생각합니다.... 이.. 학습동기를 아주 제대로 자극하는 듯... 함께 으쌰해야 하고, 안되면 나라도 하게 만드는 아이디어... 누가 기획했는지 몰라도 칭찬의 박수 드립니다👏👏👏 아주 굿인 아이디어

 

우리 학교는 총원 2명이므로 제가 한 번 열심히 해보겠습니다

익명의 누군가여... 화이팅 ^__^

 

 

매주 공부한 내용을 바탕으로 레포트를 작성하라니, 진단테스트 끝나고 배운 +1/-1 테크닉에 대해 이야기해볼까 합니다!

 

+1 / -1 Technique

진단테스트 끝나고 이런 식으로 개념을 설명해주고, 관련 문제를 풀어볼 수 있도록 구성되어있더라구요

 

+1 / -1 테크닉은 여러가지 구간이 주어지고, 그 구간들을 탐색할 때 시간을 줄여줄 수 있는 테크닉입니다!

 

 

구간의 시작을 +1로, 끝을 -1로 표시해서 현재 내가 구간 몇 개와 겹쳤는지를 확인하는 것을 더 빠르게 할 수 있는 거죠! 

느낌 오시나요???!??!

 

저같은 경우, 몇개의 구간이 겹쳤는지를 알기 위해.. 전체 구간을 배열로 선언해두고, 각 구간에 해당하는 곳에 +1을 하면 된다는 아주 나이브한 생각을 했었는데요.

역시나..... 시간초과.....😂

 

매 구간마다 반복하면서 +1을 하려니 얼마나 오래걸리겠어요... 근데 그걸 반복문이 아니라 시작과 끝으로만 표시하자!가 이 테크닉의 핵심입니다 (누적합 같은 느낌!)

 

구간의 양 끝점만 바라보자는 거죠!

 

 

문제와 풀이가 있으면 이 테크닉을 이해하는게 편할 거예요, 기본 예제를 함 보시죠

 

문제) 가장 많이 겹치는 구간

일직선 위에 n개의 구간이 주어졌을 때, 구간이 가장 많이 겹치는 부분에서 몇 개의 구간이 겹치는지를 구하는 프로그램을 작성하세요.

 

입력 형식

첫 번째 줄에 구간의 개수 n이 주어집니다.

두 번째 줄부터 n개의 줄에 걸쳐 각 줄에 각 구간을 나타내는 정보 (x1​,x2​) 값이 공백을 사이에 두고 주어집니다.

단, 주어지는 x값들은 모두 다름을 가정해도 좋습니다.

• 1 ≤ n ≤ 100,000
• 1 ≤ x1​ < x2​ ≤ 200,000

출력 형식

첫 번째 줄에 가장 많이 겹치는 구간의 횟수를 출력합니다.

입력예시	출력예시
3 2 16 4 6 7 10	2

 

 

풀이 (Python)

n=int(input())
li=[]
for _ in range(n):
    a,b=map(int,input().split())
    li.append([a,1])
    li.append([b,-1])

li.sort()

ans,tmp=0,0
for _,x in li:
    tmp+=x
    if tmp>ans:
        ans=tmp

print(ans)

 

저는 이렇게 풀었습니다.

 

li 리스트에 구간의 각 끝점을 넣어주고, 시작점은 +1, 끝점은 -1을 넣어줬어요

 

그 다음, 리스트를 정렬하여 순서대로 점이 위치하게끔 만들었고,

리스트의 내용을 탐색하면서 +1 -1을 진행합니다

이때 그 값이 최대인 경우(구간이 가장 많이 겹친 횟수)를 찾는 것이므로 최대를 비교하며 ans에 정답을 넣고 있어요!

 

 

코드트리에서는 문제를 풀고, 해설 또한 제공하는데요, 그 안에서 나랑 뭐가 다르고 어떤지에 따라 배울 수 있어서 참 좋습니다🥺💖

 

배운 점

1. 현재 점이 있을 수 있는 범위가 1~ 200,000로 작기 때문에, check라는 200,000까지 표현하는 배열을 나타내서, 그 안에 인덱스로 확인하는게 나을 수도 있다! (checked[i]+=x 꼴 이용)

2. 나 같은 경우, 단순히 배열에 넣어서 정렬했는데, 이때 어떤 구간의 끝점과 시작점이 겹치는 경우 예상치 못한 문제를 마주할 수도 있겠다!

하지만 지금 같은 경우는 같은 점일 경우 끝점이 시작점보다 먼저나오므로 ([3,-1]<[3,1]이니까요) 문제가 발생하지 않았던 듯!

 

 

이 외에도 관련 문제들을 풀며 배울 수 있었습니다...😉

이렇게 배워놓으면 또 코테에서 써먹는단 말이지...

 

최근에 문제 풀다 몇 번 본 유형인데 테크닉을 알게 되니 좋네요!

근 한달간 이제 코드트리 조별과제 레포트로 찾아뵙겠습니다😆