ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [알고리즘] 백준 선긋기 - 2170
    알고리즘 2022. 11. 4. 13:35
    728x90

    1. 문제

    선 긋기

    2. 접근

    1. 처음에는 선을 오름차순 정렬을 해서, 총길이에 집중하고 끝나는 부분과 그 다음 선의 시작 부분에 대해서만 판단을 했단

    2. 그런데 생각해보니까, 선들의 끝나는 부분을 기준으로 다음 선의 시작과 끝 중 위치한곳을 판단하면 될거 같았다.

    3. for문으로 이전 선의 끝나는 부분을 체크하고 이전 선이 다음선의 시작보다 먼저 끝나면 시작과 끝을 재설정해준다

     

    3. 풀이

    틀린 풀이

    import sys
    input = sys.stdin.readline
    
    n = int(input())
    
    line = []
    for i in range(n):
        # x y 지표로 리스형식으로 들어감 -> 2차원 배열
        line.append(list(map(int, input().split())))
    
    line.sort()
    total = 0
    
    #total = line[0][1] - line[0][0]
    print("start: ", total)
    
    for i in range(1, n-1):
        if line[i][1] >= line[i+1][0]:
            total = total + (line[i+1][1] - line[i][1])
            print("if: ", total)
        else:
            total += (line[i][1] - line[i][0])
            print("else: ", total)
    
    total += line[0][1] - line[0][0]
    print("total: ", total)

     

     

    맞는 풀이

    import sys
    input = sys.stdin.readline
    
    n = int(input())
    
    line = []
    for i in range(n):
        # x y 지표로 리스형식으로 들어감 -> 2차원 배열
        line.append(list(map(int, input().split())))
    
    line.sort()
    total = 0
    
    end = line[0][1]
    start = line[0][0]
    
    for i in range(1, n):
        if end >= line[i][1]:
            continue
        elif line[i][0] <= end < line[i][1]:
            end = line[i][1]
        elif end < line[i][0]:
            total += end - start
            end = line[i][1]
            start = line[i][0]
    
    total += end - start
    print(total)

     

Designed by Tistory.