그로블

문제 설명

카카오TV에서 유명한 크리에이터로 활동 중인 죠르디는 환경 단체로부터 자신의 가장 인기있는 동영상에 지구온난화의 심각성을 알리기 위한 공익광고를 넣어 달라는 요청을 받았습니다. 평소에 환경 문제에 관심을 가지고 있던 "죠르디"는 요청을 받아들였고 광고효과를 높이기 위해 시청자들이 가장 많이 보는 구간에 공익광고를 넣으려고 합니다. "죠르디"는 시청자들이 해당 동영상의 어떤 구간을 재생했는 지 알 수 있는 재생구간 기록을 구했고, 해당 기록을 바탕으로 공익광고가 삽입될 최적의 위치를 고를 수 있었습니다.
참고로 광고는 재생 중인 동영상의 오른쪽 아래에서 원래 영상과 동시에 재생되는 PIP(Picture in Picture) 형태로 제공됩니다.

다음은 "죠르디"가 공익광고가 삽입될 최적의 위치를 고르는 과정을 그림으로 설명한 것입니다.

• 그림의 파란색 선은 광고를 검토 중인 "죠르디" 동영상의 전체 재생 구간을 나타냅니다.
  • 위 그림에서, "죠르디" 동영상의 총 재생시간은 02시간 03분 55초 입니다.
• 그림의 검은색 선들은 각 시청자들이 "죠르디"의 동영상을 재생한 구간의 위치를 표시하고 있습니다.
  • 검은색 선의 가운데 숫자는 각 재생 기록을 구분하는 ID를 나타냅니다.
  • 검은색 선에 표기된 왼쪽 끝 숫자와 오른쪽 끝 숫자는 시청자들이 재생한 동영상 구간의 시작 시각과 종료 시각을 나타냅니다.
  • 위 그림에서, 3번 재생 기록은 00시 25분 50초 부터 00시 48분 29초 까지 총 00시간 22분 39초 동안 죠르디의 동영상을 재생했습니다. 1
  • 위 그림에서, 1번 재생 기록은 01시 20분 15초 부터 01시 45분 14초 까지 총 00시간 24분 59초 동안 죠르디의 동영상을 재생했습니다.
• 그림의 빨간색 선은 "죠르디"가 선택한 최적의 공익광고 위치를 나타냅니다.
  • 만약 공익광고의 재생시간이 00시간 14분 15초라면, 위의 그림처럼 01시 30분 59초 부터 01시 45분 14초 까지 공익광고를 삽입하는 것이 가장 좋습니다. 이 구간을 시청한 시청자들의 누적 재생시간이 가장 크기 때문입니다.
  • 01시 30분 59초 부터 01시 45분 14초 까지의 누적 재생시간은 다음과 같이 계산됩니다.
    • 01시 30분 59초 부터 01시 37분 44초 까지 : 4번, 1번 재생 기록이 두차례 있으므로 재생시간의 합은 00시간 06분 45초 X 2 = 00시간 13분 30초
    • 01시 37분 44초 부터 01시 45분 14초 까지 : 4번, 1번, 5번 재생 기록이 세차례 있으므로 재생시간의 합은 00시간 07분 30초 X 3 = 00시간 22분 30초
    • 따라서, 이 구간 시청자들의 누적 재생시간은 00시간 13분 30초 + 00시간 22분 30초 = 00시간 36분 00초입니다.

[문제]

"죠르디"의 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그 중에서 가장 빠른 시작 시각을 return 하도록 합니다.

[제한사항]

• play_time, adv_time은 길이 8로 고정된 문자열입니다.
  • play_time, adv_time은 HH:MM:SS 형식이며, 00:00:01 이상 99:59:59 이하입니다.
  • 즉, 동영상 재생시간과 공익광고 재생시간은 00시간 00분 01초 이상 99시간 59분 59초 이하입니다.
  • 공익광고 재생시간은 동영상 재생시간보다 짧거나 같게 주어집니다.
• logs는 크기가 1 이상 300,000 이하인 문자열 배열입니다.
  • logs 배열의 각 원소는 시청자의 재생 구간을 나타냅니다.
  • logs 배열의 각 원소는 길이가 17로 고정된 문자열입니다.
  • logs 배열의 각 원소는 H1:M1:S1-H2:M2:S2 형식입니다.
    • H1:M1:S1은 동영상이 시작된 시각, H2:M2:S2는 동영상이 종료된 시각을 나타냅니다.
    • H1:M1:S1는 H2:M2:S2보다 1초 이상 이전 시각으로 주어집니다.
    • H1:M1:S1와 H2:M2:S2는 play_time 이내의 시각입니다.
• 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11:12:78, 123:12:45 등)
• return 값의 형식
  • 공익광고를 삽입할 시각을 HH:MM:SS 형식의 8자리 문자열로 반환합니다.

[입출력 예]

입출력 예에 대한 설명

입출력 예 #1
문제 예시와 같습니다.

입출력 예 #2

01:00:00에 공익광고를 삽입하면 26:00:00까지 재생되며, 이곳이 가장 좋은 위치입니다. 이 구간의 시청자 누적 재생시간은 다음과 같습니다.

• 01:00:00-11:00:00 : 해당 구간이 1회(2번 기록) 재생되었으므로 누적 재생시간은 10시간 00분 00초 입니다.
• 11:00:00-21:00:00 : 해당 구간이 2회(2번, 4번 기록) 재생되었으므로 누적 재생시간은 20시간 00분 00초 입니다.
• 21:00:00-26:00:00 : 해당 구간이 1회(4번 기록) 재생되었으므로 누적 재생시간은 05시간 00분 00초 입니다.
• 따라서, 이 구간의 시청자 누적 재생시간은 10시간 00분 00초 + 20시간 00분 00초 + 05시간 00분 00초 = 35시간 00분 00초 입니다.
• 초록색으로 표시된 구간(69:59:59-94:59:59)에 광고를 삽입해도 동일한 결과를 얻을 수 있으나, 01:00:00이 69:59:59 보다 빠른 시각이므로, "01:00:00"을 return 합니다.

입출력 예 #3

동영상 재생시간과 공익광고 재생시간이 같으므로, 삽입할 수 있는 위치는 맨 처음(00:00:00)이 유일합니다.

1. 동영상 재생시간 = 재생이 종료된 시각 - 재생이 시작된 시각(예를 들어, 00시 00분 01초부터 00시 00분 10초까지 동영상이 재생되었다면, 동영상 재생시간은 9초 입니다.) 

풀이

처음에 바로 생각했던 풀이는 간단했다.

1. HH:MM:SS 형태로 주어진 시간을 second단위로 바꾼다

2. 누적 시간 배열을 만들어서 시간당 보고 있는 시청자 수를 계산한다.

3. 광고 시간대로 잘라서 누적 시청자가 제일 많은 시작점을 찾는다.

def solution(play_time, adv_time, logs):

    #99h 59m :59s -> 359999s
    cct = [0 for i in range(360000)]
    timestamp = [[] for i in range(len(logs))]

    #second 단위로 변환
    for i in range(len(logs)):
        for time in logs[i].split('-'):
            time = time.split(':')
            time = ((int(time[0]) * 60) + int(time[1]))*60 + int(time[2])
            timestamp[i].append(time)
    play_time = play_time.split(':')
    play_time = ((int(play_time[0]) * 60) + int(play_time[1]))*60 + int(play_time[2])
    adv_time = adv_time.split(':')
    adv_time = ((int(adv_time[0]) * 60) + int(adv_time[1]))*60 + int(adv_time[2])
    
    if play_time == adv_time: return "00:00:00"
    
    #누적 시간 계산
    for i in timestamp:
        for j in range(i[0], i[1]+1):
            cct[j] += 1
    
    #최대 누적 재생시간 구하기
    maxx, insert = 0, 0
    for i in range(play_time - adv_time + 1):
        if cct[i] == 0:
            continue
        tmp = 0
        for j in range(i, i+adv_time+1):  
            tmp += cct[j]
        if maxx < tmp: 
            maxx, insert = tmp, i    

    h, m, s = str(insert//3600).rjust(2,'0'), str((insert%3600)//60).rjust(2,'0'), str((insert%3600)%60).rjust(2,'0')

    return ':'.join([h,m,s])

하지만 마지막 누적 시청자를 찾는 부분에서 시간 초과 문제가 발생하였다.

확인해보니 최대 누적 시간을 계산하는 과정 중에 시간 소요가 발생했다.

그렇기 때문에 for 문을 통해 전체 시간 길이를 돌면서 하나씩 확인하는 방식이 아니라 누적 시간을 계산할 때, 시청자 누적 수 뿐만 아니라 이전에 발생한 시청자 수도 같이 합해서 끝나는 시간에서 시작하는 시간을 빼는 방식으로 시간을 계산하였다.

이와 같이 누적 시청자 수를 구해서 만약 2초에서 4초 사이에 광고가 나간다면 4초의 누적 시청자수(10) - 1초의 누적 시청자 수 (2)를 해주면 2, 3, 4초 동안의 누적 시청자 수인 8이 나온다.

누적 시간 계산은 logs를 돌면서 시청 시작 부분은 +1을 끝까지 해주고 시청 종료 부분은 끝까지 -1을 먼저 해줘서 시청자 수를 구한 다음 다시 전체 시간을 돌면서 누적 시청자 수를 구하는 방식으로 하였다.

def time2second(time):
    time = time.split(':')
    return ((int(time[0]) * 60) + int(time[1]))*60 + int(time[2])

def solution(play_time, adv_time, logs):

    play_time = time2second(play_time)
    adv_time = time2second(adv_time)
    cct = [0 for i in range(play_time+1)]

    #second 단위로 변환
    for i in range(len(logs)):
        time = logs[i].split('-')
        s = time2second(time[0])
        e = time2second(time[1])
        cct[s] += 1
        cct[e] -= 1
    
    if play_time == adv_time: return "00:00:00"
    
    #누적 시간 계산
    for i in range(1, len(cct)):
        cct[i] += cct[i-1]
    for i in range(1, len(cct)):
        cct[i] += cct[i-1]

    #최대 누적 재생시간 구하기
    maxx, insert = cct[adv_time-1], 0
    for i in range(1, play_time - adv_time + 2):
        tmp = cct[i+adv_time-1] - cct[i-1]
        if maxx < tmp: 
            maxx, insert = tmp, i    

    h, m, s = str(insert//3600).rjust(2,'0'), str((insert%3600)//60).rjust(2,'0'), str((insert%3600)%60).rjust(2,'0')

    return ':'.join([h,m,s])

테스트 1 〉	통과 (1.65ms, 10.6MB)
테스트 2 〉	통과 (7.33ms, 10.5MB)
테스트 3 〉	통과 (15.13ms, 11.2MB)
테스트 4 〉	통과 (207.86ms, 27.9MB)
테스트 5 〉	통과 (290.96ms, 34.1MB)
테스트 6 〉	통과 (137.01ms, 21.4MB)
테스트 7 〉	통과 (456.72ms, 41.1MB)
테스트 8 〉	통과 (434.63ms, 45.9MB)
테스트 9 〉	통과 (590.75ms, 54.3MB)
테스트 10 〉	통과 (631.43ms, 54.6MB)
테스트 11 〉	통과 (622.49ms, 52MB)
테스트 12 〉	통과 (639.43ms, 49.7MB)
테스트 13 〉	통과 (639.43ms, 54.5MB)
테스트 14 〉	통과 (455.07ms, 41MB)
테스트 15 〉	통과 (47.93ms, 15.1MB)
테스트 16 〉	통과 (438.52ms, 40.8MB)
테스트 17 〉	통과 (629.12ms, 54.5MB)
테스트 18 〉	통과 (542.11ms, 42.2MB)
테스트 19 〉	통과 (1.75ms, 10.5MB)
테스트 20 〉	통과 (1.47ms, 10.4MB)
테스트 21 〉	통과 (139.29ms, 20.3MB)
테스트 22 〉	통과 (141.34ms, 20.3MB)
테스트 23 〉	통과 (593.26ms, 47.1MB)
테스트 24 〉	통과 (486.74ms, 40.9MB)
테스트 25 〉	통과 (104.82ms, 19.6MB)
테스트 26 〉	통과 (60.80ms, 14.9MB)
테스트 27 〉	통과 (65.75ms, 17.3MB)
테스트 28 〉	통과 (57.01ms, 16.9MB)
테스트 29 〉	통과 (56.14ms, 16.6MB)
테스트 30 〉	통과 (51.41ms, 14.1MB)
테스트 31 〉	통과 (53.68ms, 14.9MB)

ID, PW 입력폼이 나오고 페이지 소스를 보면 힌트를 확인할 수 있다.

<!-- Hint : Login 'admin' Password in 0~9999 -->

ID는 'admin'이라고 알려주고 Password는 0~9999 사이라고 한다. Burp suite를 이용해서 간단히 풀어줄 수 있다.

Burp Suite Proxy탭에서 오른쪽 버튼을 눌러서 Send to Intruder을 해준다.

자동으로 Target은 설정이 되고

Positions탭에서 Clear로 초기화해준 뒤 pw만 잡아서 Add를 해준다.

Payloads 탭에서 type을 Number로 설정하고 Number range를 설정해준다.

Options 탭에서 Grep부분에 Authkey를 추가해준다. 1번에서 6번까지 문제를 풀면서 정답에 Authkey 가 포함되는 것을 알았기 때문에 추가해줄 수 있었다. Password Incorrect!를 추가해서 Grep되지 않는 값을 찾아도 괜찮다.

Start Attack을 누르면 이와 같이 하나씩 시도하면서 결과를 알려준다.

AuthKey로 정렬하고 확인하다 보면 Authkey가 Grep되는 값을 찾을 수 있다.

ID: admin, PW: 7707이다. 그런데 사실 Burp Suite로 하면 너무 느려서 python으로 정답을 확인한 뒤 범위를 다시 지정하고 공격을 수행하였다.

import requests

URL="http://suninatas.com/challenge/web08/web08.asp"

session=requests.Session()
 
for password in range(10000) :

    login_data={"id":"admin", "pw":password}
    req=session.post(URL, data=login_data)

    key = req.text.find("Authkey")
    
    if (key!=-1):
        print(req.text[key:key+50])

이런식으로 파이썬을 이용해 짜주면 훨씬 금방 코드를 짤 수 있다.

백만년전에 찍은 것 같은 아이유 사진과 함께 Do U Like girls?라는 문구가 보인다.

페이지 소스를 확인해보면 힌트와 스크립트가 보인다.

    <script>
        function noEvent() {
            if (event.keyCode == 116 || event.keyCode == 9) {
                alert('No!');
                return false;
            }
            else if (event.ctrlKey && (event.keyCode = 78 || event.keyCode == 82)) {
                return false;
            }
        }
        document.onkeydown = noEvent;
    </script>
    
<!-- Hint : Faster and Faster -->
<!-- M@de by 2theT0P -->

그리고 밑을 확인해보지 않았었는데 내려보면 Yes라는 버튼과 사진 하나가 더 나온다.

힌트의 Faster and Faster은 빠르게 Yes  버튼을 눌러야 된다는 의미인 것 같다. 실제로 Yes를 눌러보면 너무 느려서 실패했다고 나온다.

스크립트 코드를 확인해보면 event.keycode가 116이거나 9일 때 No라는 경고문이 뜨는데 여기서 116은 f5(새로고침)이고 9는 tab이다. 새로고침해서 탭으로 빠르게 누르는 것을 방지하는 듯 하다.

또한 event.keycode가 78 or 82이고event.ctrlKey가 true일때도 false를 return한다. 여기서 78은 'n', 87는 'r'이다. ctrl+n은 새로운 창 생성이고 ctrl+r은 새로고침이다. 이 두 동작도 막힌 것을 알 수 있다.

        <div align="center">
            <input type="submit" value="YES">
        </div>

Yes를 누르게 되면 type에 지정된 대로 서버로 데이터를 보내게 된다.

<form method="post" action="./web07_1.asp" name="frm">

해당 폼을 보면 frm이라는 이름을 가지고 있다. 그러므로 개발자도구 콘솔창에서 document.frm.submit()를 재빠르게 입력해주면 폼이 넘어갈 수 있을 것이다.