규도자 개발 블로그

[SWEA/12741/파이썬3(python3)] 두 전구 본문

알고리즘/풀이

[SWEA/12741/파이썬3(python3)] 두 전구

규도자 (gyudoza) 2021. 9. 29. 06:40

[SWEA/12741/파이썬3(python3)] 두 전구

문제

두 개의 전구 X와 Y가 있다. 당신은 0초에서부터 시작하여 100초간 두 전구가 언제 켜지는지를 관찰하였다. 관찰 결과, 전구 X는 관찰 시작 경과 후 A초에서부터 관찰 시작 경과 후 B초까지에만 켜져 있었다. 전구 Y는 관찰 시작 경과 후 C초에서부터 관찰 시작 경과 후 D초까지에만 켜져 있었다. 당신이 두 전구를 관찰하던 100초 중 두 전구가 동시에 켜져 있던 시간은 몇 초일까?

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 네 개의 정수 A, B, C, D (0 ≤ A < B ≤ 100, 0 ≤ C < D ≤ 100)가 공백 하나를 사이로 두고 순서대로 주어진다.

3
1 3 5 7
0 5 2 4
0 5 1 6

출력

각 테스트 케이스마다, 두 전구가 동시에 켜져 있던 시간이 몇 초인지를 한 줄에 하나씩 출력한다.

#1 0
#2 2
#3 4

풀이

case_count = int(input())
ontimes = []

for case_number in range(1, case_count + 1):
    seconds = list(map(int, input().split()))
    A = [0] * (max(seconds))
    B = [0] * (max(seconds))
    on = 0
    for second in range(seconds[0], seconds[1]):
        A[second] = 1
    for second in range(seconds[2], seconds[3]):
        B[second] = 1
    for a, b in zip(A, B):
        if a and b:
            on += 1
    ontimes.append(on)

for index, ontime in enumerate(ontimes):
    print('#', end='')
    print(index+1, ontime)

설명

풀면서 스트레스 엄청나게 받았던 문제이다. 근데 문제 내적으로 스트레스 받았던 게 아니라 문제 외적으로 스트레스를 받았다. 분명히 정답인데 정답처리가 안됐으니까. 이걸 굳이 포스팅으로 남겨놓는 이유는 다른 문제들 처럼 좋은 문제들이었거나 그냥 맨날 풀면 습관적으로 남겼거나 그런 게 아니라 그냥 스트레스를 줘서 그렇다.
 요지는 이러하다. 이 문제를 실제로 제출하면 테스트케이스가 총 5만 개가 들어오는데 기존의 방식대로 한 for문 안에 입력 -> 출력이라는 형태를. 같이 담아두면 아무런 로직을 더하지 않아도 입력과 출력에만 시간초과가 뜬다. 그래서 생각한게 "아 정답만 한 배열에 때려박고 for문이 끝나면 형식대로 출력하자"여서 저렇게 제출했는데 전에는 저렇게 제출했어도 제한시간 초과가 떴었다. 아무래도 사이트에서도 문제를 인지하고 바꾼 것 같은데 아무튼... 2번째 방법까지 실패한 나는 아 다음에는 로직을 바꿔보자 해서 이케이케 저케저케 어케어케든 해봤는데 다 오류가 뜨는 것이다. 말을 로직으로 풀어서 조건문으로도 풀어보고, 들어온 애들을 이진수화시켜서 and연산시킨다음에 1의 갯수를 세는 방법 등등 많은 시도를 해봤는데 전~~~부 제한시과 초과가 뜨더라. 입출력만 해봐도 제한시간에 걸리는데 참 부단한 노력이었다. 근데 또 제출이력에 보면 파이썬으로 제출한 정답이 있어서 포인트를 써서라도 그 정답을 보고 싶었는데 정답보기는 또 막혀있는 문제니까 뭐 방법이 없었다. 그래서 사이트에 오류 제보 넣고 기다리고 있다가 오늘 다시 시도해봤는데 통과가 잘 되더라. 물론 아직도 for문 안에 출력을 그대로 넣으면 시간초과가 뜨지만 전에는 1600개만 통과됐다고 뜨고 지금은 36000개가 통과됐다고 뜨는거 보니 뭔가 조치가 이뤄진 것 같다. 아무튼 문제는 쉬웠는데 이러저러한 이유로 스트레스를 많이 받아서 기념으로 남겨두려고 한다.
 문제를 푼 로직은 간단하다. 시간의 흐름을 배열로, 그 시간에 전구의 전원 여부를 1과 0으로 표현한 뒤에 두 전구가 모두 켜져있었던 시간을 센 뒤에 반환한다. 2번째 테스트케이스인 0 5 2 4를 예로 들면

A = [1, 1, 1, 1, 1]
B = [0, 0, 1, 1, 0]

이런 형태의 배열 두 개가 만들어진다. 두 배열에 동시에 1이 들어있는 인덱스는 2개이므로 2초가 정답인 것이다. 사람의 언어로 이해해보자면 2초에서 4초까지 켜져있었다고 보면 될 것이다. 나도 말하면서 생각이 드는데 왜 2초에서 4초면 2, 3, 4니까 3초가 아니냐는 의문이 생길수도 있겠다는 생각이 들었다. 그럴땐 '초사이'를 생각하면 될 것 같다. 2초에 켜서 4초에 껐으면 2초와 3초사이, 3초와 4초사이에만 불이 켜져있었지 4초 이후로는 전구가 켜져있지 않으므로 전구가 켜져있던 시간은 엄밀히 2초간이 되는 것이다. 뭐 아무튼 짜증나는 문제였다.

 

 

부단한 노력의 흔적...ㅠㅠ



다른 풀이를 봤는데 훨씬 더 간단히 풀리는 문제였다. 시간초과났던 건 순전히 내가 쓴 코드의 퍼포먼스 문제였다... 라기보단 성능차이가 또 그렇게 많이 나진 않는다. 혹시나 싶어서 이 코드로도 입출력 한번에 해봤는데 시간초과 나더라... 근데 이게 훨씬 더 맞는 답 같아서 남겨놓는다.

case_count = int(input())
ontimes = []

for case_number in range(1, case_count + 1):
    A, B, C, D = list(map(int, input().split()))
    on = min(B, D) - max(A, C)
    on = on if on > 0 else 0
    ontimes.append(on)

for index, ontime in enumerate(ontimes):
    print('#', end='')
    print(index+1, ontime)

min(B, D) - max(A, C)라는 간단한 식으로 얻어지는 문제였다. 나는 참 수학적인 직관력이 너무 형편없구나... 싶었다.

Comments