Ray`s Tech Lab

https://www.acmicpc.net/problem/1806

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1 복사

10

15 5 1 3 5 10 7 4 9 2 8

예제 출력 1 복사

2

[접근방식]

1. 배열의 첫 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.

2. 배열의 두 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.

3. 배열의 세 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.

...이렇게 해서 각 단계에서 구한 길이 중 가장 짧은 놈을 고른다.

import sys

N, S = map(int, sys.stdin.readline().split())
length = []

arr = list(map(int, sys.stdin.readline().split()))

for i in range(len(arr)):
    j, sum = i + 1, arr[i]

    while(sum < S and j < len(arr)):
            sum += arr[j]
            j += 1
    if sum >= S:
        length.append(j - i)

if length:
    print(min(length))
else:
    print(0)

근데 위 코드는 시간초과가 발생한다. 왜일까?

우선 코드를 보면 난 for문에서 i를 시작점으로 설정하며 각 구간들을 구하는데, j라는 변수가 구간의 끝점역할을 한다. 따라서 구하는 구간의 합이 S이상이 되는 순간 구간의 길이인 j - i를 length리스트에 더하고 마지막에 min메소드로 가장 짧은 길이를 출력하면 그것이 정답이다. 근데 시간초과가 뜨는 이유는 다름아닌 j, sum와 관련되어 있다.

바로 매 순간 새로 측정을 시작할 때마다(즉 시작점 i가 바뀔 때마다) j를 i + 1로 세팅한 뒤, j를 늘려가면서 측정하기 때문! 이것이 시간을 잡아먹는다. 마찬가지로 sum을 매 측정마다 새로 설정해주는 것도 시간을 잡아먹는다. 왜 Why?

어떤 단계에서 합이 S이상이 되는 구간을 구했다고 할 때, 이 구간의 끝점이 있다.

다음 단계에서 합이 S이상이 되는 구간을 또 구할텐데, 이 때 새로 구하게 되는 구간의 끝점은 이전 단계에서 구한 구간의 끝점보다 같거나 클 수밖에 없기 때문! 따라서 매 측정의 단계에서 사용한 j와 sum을 그대로 재활용?하는 느낌으로 써주는 식으로 코드를 수정했다.

import sys

N, S = map(int, sys.stdin.readline().split())
length = []

arr = list(map(int, sys.stdin.readline().split()))
sum_arr, j = arr[0], 1

for i in range(len(arr)):           
    while(sum_arr < S and j < len(arr)):   
        sum_arr += arr[j]             
        j += 1
    if sum_arr >= S:                       
        length.append(j - i)
    sum_arr -= arr[i]                     

if length:                                
    print(min(length))
else:                                      
    print(0)

이런 방식?을 투포인터 알고리즘 이라 부르는 것 같다.

공부해봐야겠다..

https://www.acmicpc.net/problem/1343

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 500이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

예제 입력 1 복사

XXXXXX

예제 출력 1 복사

AAAABB

예제 입력 2 복사

XX.XX

예제 출력 2 복사

BB.BB

[내가 한 풀이]

boards = input().split('.')
answer = ''

for board in boards:
    if len(board) % 2 == 1:
        print(-1)
        break
    else:
        if len(board) >= 4:
            answer += 'AAAA' * (len(board) // 4)
        answer += 'BB' * ((len(board) % 4) // 2) + '.'
else:
    print(answer[:-1])

입력으로 받은 전체 보드판(?)을 split()메소드를 활용해 온점(.)을 기준으로 나눠서 리스트로 만든다.

이후 리스트에 대해 순회하는데, 나는 AAAA와 BB라는 폴리오미노만 갖고 있으므로 홀수칸짜리 보드판에 대해서는 폴리오미노를 덮을 수 없다. 이 경우는 2로 나눈 나머지가 1인 경우에 해당하며, 이땐 -1을 출력하고 break.

보드판이 짝수칸이라면 몇 칸인지에 관계없이 폴리오미노로 덮을 수 있는데, 2칸일 경우에만 처음부터 바로 BB를 채우고 2칸이 아니라면 그냥 무지성으로 AAAA만 신나게 깔아주다가 마지막에 2칸만큼 남으면 BB를 덮으면 된다. 어차피 if-else 이하의 코드는 순회한 보드가 짝수칸일테만 실행되므로, 4칸 이상일 때는 보드칸을 4로 나눈 몫만큼 AAAA를 덮어주고, 이후 나머지 칸에 대해 BB를 덮어준다. AAAA를 다 덮고 남은 칸은 len(board) % 4이다. 

마지막엔 출력할 차례. 순회하는 모든 보드판이 죄다 짝수칸이었다면 break문에 의해 비정상적으로 for문이 종료되지 않았으므로 마지막의 for-else문의 print가 실행된다. 이때 answer의 마지막은 온점(.)이므로 슬라이싱하여 그 전까지만 출력하면 정답이다. 

[더 쉬운 풀이]

board = input()
board = board.replace("XXXX", "AAAA")
board = board.replace("XX", "BB")
if 'X' in board:
    board = -1
print(board)

replace메소드를 활용해 처음엔 문자열 내에 등장하는 모든 XXXX를 AAAA로 바꾸고, 이후 다시 문자열 내에 등장하는 모든 XX를 BB로 바꿔주고, 마지막에 X가 남아있다면 -1을 출력하도록 한다.

replace메소드는 replace(old, new, count) 총 3개의 파라미터를 받으며 old는 현재 문자열에서 바꾸고 싶은 놈, new는 새로 바꿀 문자, count는 정수를 받으며 변경할 횟수를 의미한다. count는 optional로 입력하지 않으면 문자열 전체의 old를 new로 바꾼다.