1172: 킹콩 영준이와 종욱이의 대도시 파괴 프로젝트

Link : judge.koreatech.ac.kr/problem.php?id=1172

---

1. 문제

• 킹콩 영준이와 종욱이의 취미는 도시를 망가트리는 것이였다.
  
  그러던 어느날 평소와 같이 도시를 망가트리는 종욱이를 보고 있던 영준이의 머리속에 기가막힌 아이디어가 떠올랐다.
  이제껏 건물을 하나하나 부수는 것 대신, 건물을 밀어서 손쉽게 망가트리자고 제안한 것이였다.
  이를 들은 종욱이는 너무나 기쁜 나머지 흔쾌히 승락하였고 그렇게 도시를 망가트리기로 하였다.
  
  영준이가 제안한 내용은 다음과 같다.
  도시의 건물은 항상 일렬로 구성되어 있으므로 영준이와 종욱이가 각자 건물을 왼쪽(L)과 오른쪽(R) 방향으로 밀어 넘어뜨리면 훨씬 손쉽게 도시를 망가뜨릴 수 있다는 것이였다. 이때 밀린 건물들은 매 사이클 마다 지정된 방향으로 한칸씩 움직이며 쓰러진다고 한다. 단 건물이 서로 마주 보는 방향으로 오고 그 사이에 1개의 건물이 서있을때 그 건물은 쓰러지지 않는다고 한다.
  

  

  모든 건물이 쓰러지고 더이상 쓸어질게 없는 도시의 모습은 어떤 모습이 되겠는가?
  (망가지지 않은 도시는 나중에 영준이와 종욱이가 친히 다시 방문하기로 하였다.)

---

2. 문제의 조건

• 1 <= T <= 100
• 1 <= s <= 50,000
• s는 R, L이 여러번 주어질 수 있다.

 

---

3. 문제 접근

• 시간 복잡도
  
  시간제한 1초에 케이스가 500만개이므로 약 O(N^1.19)시간 내에 풀어야합니다.

 

• 아이디어
  
  1->N까지 탐색 순서대로 탐색하는 방법은 L이나 R 이후 무슨 문자가 올 지 몰라서 시도조차 못해보았습니다.
  그래서 선택한 방법이 L과 R이 있는 지점을 stack에 추가하여 분류하자 입니다.
  
  ..R..R..R..R..L..L..L..L
  일경우 2, 5, 8, 11, 14, 17, 20, 23으로 (s, idx) s생략 stack에 쌓이고
  
  ..RRR.LLL..RRR..LLL
  일 경우 ('R',2), ('R',3), ('R',4), ('L',6), ('L',7), ('R',8), ('R',11), ('R',12), ('L',16), ('L',17), ('L',18) 의 위치가 stack 에 쌓이게됩니다.
  
  맨 처음 스택 (s, idx)일 경우 R<->L 사이인 경우에만 신경을 써주시면 됩니다.
  
  즉, O(N)에 해결할 수 있게 됩니다.

 

---

4. 풀이 방법

• 현재 진행중인 점 pos를 0으로 지정합니다.
• save 에서 원소를 꺼내옵니다.
• 원소를 꺼낸 후 save의 개수가 0이면 마지막 점입니다
  마지막이 R로 끝났을 경우, 현재의 점부터 끝점까지 전부 R로 메꿉니다.
  
  마지막이 L로 끝났을 경우, 이전 진행중인 pos점부터 현재 위치까지 전부 L로 메꿉니다.
• 마지막 점이 아닌 저장된 스택이 더 있을 경우에
  꺼낸스택이 'R'이고 다음스택이 'L'일 경우,
  
  채워야 할 케이스는 각각 1개입니다.
  point = (L의 위치 - R의 위치 - 1) // 2
  
  point = (3 - 0 - 1) // 2 = 1
  (파이썬은 기본적으로 for i in range(a, b) 하면 a <= x < b 입니다.)
  
  여기서 2가지의 케이스에 주의하여 생각하시길 바랍니다.
  1. (R 0, L 3)
  

  R

  R

  L

  L

  R부터 현재 꺼낸 (R의 위치 + 1)부터 (R의 위치 + point + 1)만큼 'R'로 채우고
                             (0 + 1)                   (0 + 1 + 1)
  
  L부터 (L의 위치 - point)부터 (L의 위치)만큼 'L'로 채웁니다.
              (3 - 1)                        (3)
  
  point = (4 - 0 - 1) // 2 = 1.5 => int => 1
  2. (R 0, L 4)
  

  R

  R

  .

  L

  L

  R부터 현재 꺼낸 (R의 위치 + 1)부터 (R의 위치 + point + 1)만큼 'R'로 채우고
                        (0 + 1)                (0 + 1 + 1)
  L부터 (L의 위치 - point)부터 (L의 위치)만큼 'L'로 채웁니다.
          (4 - 1)                      (4)
  그리고 pos를 L까지 옮겨주고 L을 처리하였으니 save.pop(0)으로 한번 제거해줍니다.
• 만약 R과 L사이가 아닐 경우 (R -> R 이거나 L -> L 이거나 L -> R이거나)
  현재스택이 L인지 R인지 비교 후
  L이라면 이전 완료된 pos점부터 현재 스택까지 L로 채우고
  R이라면 현재 시점부터 다음 저장되어있는 원소 위치까지 R로 채웁니다.

 

---

5. 소스코드

• cjw-git.tistory.com/72

 

---

 

cjw.git@gmail.com