알고스팟 zeroone 문제 파이썬으로 풀기

0과 1로 이루어진 순열의 어떤 구간에서 최대값과 최소값이 일치하는지를 구하는 문제이다.

최대값과 최소갑이 일치한다는 것은 그 구간이 0이나 1 둘중 하나의 숫자로만 구성되어 있다는 것이고, 일치하지 않는다는 것은 0과 1이 섞여져 있다는 것이다.

#zeroone
import sys
 
 
numlist = sys.stdin.readline()
num2 = []  # 일치하는지 안일치하는지 알아보기 위한 리스트
value = 0
num2.append(value)  # 첫 값을 넣어줌
for j in range(len(numlist)-1):  # 앞의 값이 현재값과 일치하면 똑같은 수를, 아니면 1 더한 수를 넣음
    if numlist[j] != numlist[j+1]:
        value += 1
    num2.append(value)  
case = int(sys.stdin.readline())
for i in range(case):
    i1, j1 = map(int, sys.stdin.readline().split()) # 구간을 정하는 수
    if i1 > j1:  # 앞이 더 크면 서로 바꿈
        i1, j1 = j1, i1
    if num2[i1] == num2[j1]:
        print("Yes")
    else:
        print("No")

코드만 보면 어떤 방식으로 작동하는지 잘 감이 안잡힐 수도 있기 때문에, 내가 코드를 작성할 시 참고했던 것들을 첨부하겠다.

출처: https://iyaacs.tistory.com/1

출처: https://blog.naver.com/hiyaku0317/220318170340

즉 내가 짠 코드는 입력받은 수열에서 현재값과 그 다음값을 비교해 같으면 같은 값을 다른 수열에 넣고, 다르면 +1 한 값을 수열에 넣는 방식이다. (예: 입력수열이 011110001010101 이면 011112223456789 가 된다)

문제에서 나온 예시도 잘 돌아간다.

정답.

 

느낀점:

1. 처음 생각한 방법은 구간 내에서 count함수로 0과 1의 갯수를 새서 그 값을 구간의 길이랑 비교해 같으면(구간의 길이=0갯수 or 1갯수면 구간이 0이나 1로만 이루어져있다는 것) yes 아니면 no를 출력하게 했지만 시간초과가 났다. 그다음 생각한 방법은 0과 1을 세는 변수를 만들고 구간에서 한 요소씩 보면서 0이면 0을 세는 변수값을 증가시키고, 1이면 1을 세는 변수값을 증가시키는 방법을 썻는데 또 시간초과가 났다. 그래서 인터넷에서 위에 쓴 방식을 찾아서 쓰게 되었는데, 이것도 질문을 받을때마다 실행하게 해서 시간초과가 났고, 처음에 한번만 실행하게 고쳤다. count함수를 쓰거나 0이나 1을 세서 변수에 저장하는 방식이 시간을 꽤 많이 잡아먹는거 같다.

2. 

이런 방식도 있다곤 하는데 누적합을 어떻게 구하는지 이해가 잘 가지 않는다. 입력을 받을때 str값이 아니라 int로 받고 합을 구하는 거 같은데 그렇게 하면 매번 타입을 바꾸는데 시간이 오래 걸릴거 같다.