1125: 좌우로 밀착 I

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

---

1. 문제

• 겁 없이 해병대에 자원한 02학번 광성이. 오늘은 입대하는 날이다.
  포항에 집결하자 광성이와 같은 훈련병들이 가슴에 번호표를 달고 어수선하게 흝어지어 있었다.
  질서정연한 것을 좋아하는 해병대 훈련 교관(DI)은 어수선하게 서 있는 훈련병들에게 소리쳤다.
  "자, 번호와 상관없이 C열 종대로 줄 맞추어 섭니다!! 실시!!!"
  쭈뼛쭈뼛 순서와 상관없이 C열로 줄 맞추어 선 광성이와 훈련병들. 해병대는 가입소 기간동안 자진하여 퇴소를 할 수 있다.
  "자자, 본격적인 훈련을 시작하기 전에 집에 갈 사람들은 좌측으로 빠집니다. 실시!!"
  중간중간 좌측으로 빠지는 훈련병들을 보며 집에 갈까 말까 갈팡질팡하던 광성이. 고민 끝에 좌측으로 빠지려던 찰나,
  "동작 그만! 좌로 밀착한 후 다시 앞으로 밀착하여 빈자리를 채웁니다!!! 실시!!"
  아뿔싸!! 늦었다!! 어서 좌로 밀착한 후 다시 앞으로 밀착하자!!!!

 

---

2. 문제의 조건

• 1 <= T <= 100
• 1 <= R, C <= 100

 

---

3. 문제 접근

• 시간 복잡도
  
  데이터가 총 1만개이므로 1초이내의 시간이라면 이 문제는 O(N^2)에 해결 해야만 합니다.

 

• 아이디어
  
  처음 데이터를 받을 때 0이 아닌 수만 받고 0인 숫자는 개수를 측정하여 한 줄이 끝날 때 뒤에 추가해줍니다.
  해당 케이스의 경우 X축이 왼쪽으로 정렬이 됩니다.
  1
  3 5
  1 0 2 3 0
  0 4 5 6 7
  8 0 0 0 9
  의  경우 1 0 2 3 0 으로 들어오는데
  0 이 아닌수를 받으면
  1 2 3 이되고 0이 2개있으므로 2번 0을 붙히면
  1 2 3 0 0 이 됩니다. 즉, 왼쪽으로 정렬이 됩니다.
  
  
  또한 주어진 데이터로 Y축으로 검사를 진행하여 0인 숫자는 개수를 측정하고 0이 아닌 수만 임시변수 v에 저장을 한 뒤 0이 안된 수는 s의 뒤에 붙혀놓습니다.
  1 2 3 0 0
  4 5 6 7 0
  8 9 0 0 0
  을 기준으로 Y축을 기준으로 읽게되면
  1 4 8
  2 5 9
  3 6 0
  0 7 0
  0 0 0
  이 됩니다.
  0 7 0 일 경우
  0 이 아닌수는 7이므로
  [7] 이 되고 0인 수는 2개가 있으므로 [7 0 0]이 됩니다. 즉 이렇게 처리를 하시면 왼쪽 -> 위로 정렬 한 형태가 나오게 됩니다.

 

---

4. 풀이 방법

• 숫자를 받을 때, 0인 수를 축척하고 X의 데이터가 끝났을 때, 0인 수만큼 0을 뒤에다 붙혀줍니다.
• 다 받고 난 뒤 Y축을 기준으로 1번과 같이 수행합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/67

---

 

cjw.git@gmail.com