오늘은 코포가 터져버리는 바람에 앳코더에서 연습을 했다.

총 6문제 중 A,B,C,D를 풀었고, E,F를 못풀어 아쉬움이 많지만, 그래도 내 실력을 최대한 발휘했다.

A번

그냥 문자열 안에 다른 문자가 있는지 묻는 문제이다.

쉽게 O(n)으로 풀 수 있다.

B번

빨간 공, 파란공이 무한히 있는데, 파란공 n개, 빨간공 m개로 배열할 것이다. t번째 공까지 포함해서 처음부터 t번째 공까지의 파란 공의 개수를 구하라는 문제이다.

t가 10^18이니 O(n)으로도 벅찰 것이다.

우리는 항상 파란 공, 빨간 공이 규칙적으로 놓인다는 것을 안다.

파란공 n개, 빨간공 m개가 놓일 때 한 주기가 반복된다고 가정하자.

한 주기당 파란 공은 n개씩 놓인다. 그렇다면 t보다 작은 정수 중 (n+m)으로 나누어지는 최대의 수를 tM이라고 할때, 해는 이렇다.

tM/(n+m) + (t%(n+m)>n ? n:t%(n+m))

실제 프로그램을 짤 땐 tM을 굳이 안 구해도 된다.

이유는 (정수/정수)는 나머지를 버리고 그의 정수 부분만 뽑아내기 때문이다.

C번

임의의 수 t가 어떤 수 a,b에 대해 [t0.08]=a와 [t0.1]=b를 만족하는 t를 찾으라는 문제이다.

t가 최대가 될수 있는 경우는 100*100=10000이기 때문에 완전탐색으로 풀 수 있다.

D번

문자열을 입력받고, 각 퀴리에 따라 변형한 문자열을 출력하라는 문제이다.

deque 자료구조를 써서 구현을 하였다.

자세한 구현은 이렇다.

1번 쿼리 :
    
    상태 변수 r을 만들어준다. 이때 r은 뒤집어져 있는가를 확인하는 역할을 한다.
    
    r은 0,1중 하나이므로 상황에 따라 바꾸어 준다.
    
2번 쿼리 :
    
    r에 따라 deque 자료구조의 앞,뒤 중 알맞은 곳에 삽입하면 된다.
    
출력 :
    
    이것도 r에 따라 시작의 여부가 결정된다.
    
    r=0 : 
        
        뒤집어져 있지 않다는 뜻. 그러므로 앞에서부터 출력.
        
    r=1 : 
        
        뒤집어져 있다는 뜻. 그러므로 뒤에서부터 출력.

---