Q12 기둥과 보 설치

domybest·2021년 4월 15일
0

실전 문제

목록 보기
11/34

풀이 코드

알고리즘

어려웠다.. 문제를 풀면서 항상 느끼는거지만 아이디어, 구현 방법 자체는 어렵지 않은데 자잘한 부분들에서 놓치는 것들 때문에 시간을 엄청나게 잡아 먹는 것 같다. 50분만에 풀어야 한다고들 말하지만 4시간 정도가 걸렸다. 잘 정리해서 꼭 복습하도록 하자.
사실 문제에서 모든 힌트를 줬다. 문제를 잘 해석해야 하는 문제인 것 같다.

**1. 한 포인트에서 기둥과 보가 동시에 있을 수 있기 때문에 기둥 배열과 보 배열을 따로 관리하기로 한다.
**2. 기둥과 보의 삽입, 삭제 연산 후 기둥과 보가 규칙에 부합하는지 확인하는 함수를 만들어야 겠다.
**3. (x, y) 좌표로 주어지지만 2차원 배열에서는 x좌표가 열이고 y좌표가 행에 해당한다는 것 주의
**4. x나 y에 +1이나 -1을 하면 절대 index 범위를 벗어나서는 안된다는 점 주의
**5. 좌표에서 점에 대해 연산을 하기 때문에 프로그래밍 시에는 n + 1 만큼 배열을 생성해야 한다는 점
**
시간을 많이 잡아 먹었던 주의사항 5가지이다. 이를 기억하고 실수없이 구현해야만 빠른 시간내에 문제를 해결할 수 있다.

기둥과 보에서 안정성에 부합하는지 확인할 규칙은 다음과 같다.
<기둥>

  1. 바닥 위에 있다. 즉, y 좌표가 0이다.
  2. 보의 한쪽 끝부분 위에 있다.
  3. 다른 기둥 위에 있다.
    쉽게 해석하면 어딘가의 '위'에 있거나 바닥위에 있어야 한다. 이를 구현으로 정리하면
  4. y = 0인가?
  5. (x-1, y)에 보가 있는가? 이 때 x-1은 0 이상이다.
  6. (x, y)에 보가 있는가?
  7. (x, y-1)에 기둥이 있는가? 이 때 y-1은 0 이상이다.
    이 중 하나만 만족하면 해당 좌표에서 기둥은 안정성 있다고 할 수 있다.

<보>

  1. 한쪽 끝부분이 기둥 위에 있다.
  2. 양쪽 끝부분이 '동시에' 다른 보와 연결되어 있다.
    받쳐주고 잡아주는 무언가가 있어야 한다라는 의미이다. 이를 구현으로 정리하면
  3. (x, y-1)에 기둥이 있는가? 이 때 y-1은 0 이상이다
  4. (x+1, y-1)에 기둥이 있는가? 이 때 x+1은 n이하이고 y-1은 0 이상이다
  5. (x-1, y)와 (x+1, y)에 동시에 보가 있는가? 이 때 x-1은 0이상이고 x+1은 n이하이다.
    역시 이 중 하나만 만족한다면 해당 좌표에서 보는 안정적이라고 할 수 있다.
    안정성 판별에 관한 함수는 작성했다.

이제 삽입과 삭제를 구현해야 한다. 삽입은 해당 좌표에서 안정성을 체크하고 안정성이 있는 것으로 판별되면 삽입을 한다. 삭제 역시 마찬가지다.
이때 결과 리스트에 삽입과 삭제 연산 역시 동시에 수행되어야 한다.

결과 리스트는 속성으로 x, y, a를 가지는 Result 클래스를 원소로 가지는 ArrayList를 사용한다. 그리고 문제에서 주어진 정렬에 관련된 compareTo 함수를 오버라이딩한 것이 Result 클래스이다.
<정렬 규칙>

  1. x를 기준으로 오름차순
  2. x가 같으면 y를 기준으로 오름차순
  3. 둘 다 같으면 기둥이 먼저 오도록 정렬

마지막으로 리턴 값은 2차원 배열로 반환하라고 했으므로 2차원 배열에 모든 결과 리스트를 삽입한다.

돌아보면 문제가 어렵진 않으면서 어려웠다고 느껴진다. 침착하고 빠른 판단력과 꼼꼼한 구현 능력이 더 필요할 것 같다.

profile
기억할 때 까지 반복!

0개의 댓글