알고리즘 공부/위클리 챌린지

프로그래머스 위클리 챌린지 10주차 - java

철매존 2021. 10. 13. 00:36
728x90
반응형

문제 설명

1. 좌표평면상의 선분들이 주어진다.

2. 선분들이 만나는 좌표들의 정수값들만 고려한다.

3. 만나는 곳은 * 나머지는 . 으로 이루어진 최소 크기의 도형을 RETURN하면 된다.

풀이 과정

 1. 이게 왜 level2문제일까....? 생각보다 난이도가 높았다. 차근차근 하나씩 구해주자. 이거 클래스 써서 하려 했더니 코드가 진짜 말도안되게 더러워져서 절차적으로 풀었다.

( 교점 구하기 )

 2. 먼저 선들이 만나는 점을 구한다. 고등학교 때에 배운 일차함수 방정식을 쓰면 된다. <- 참고로 이거 각 선들에 대해 long을 꼭 써줘야 한다. 왜냐면 int값을 벗어나는 값이 들어올 수 있음...여기서 시간을 엄청 버렸다.

 3. 좌표를 구할 때에 정수인지 확인하려면 어떻게 해야 할까? 나는 처음에 double형과 long형 두 개를 구해서 같은 경우 진행하도록 하였는데, 이랬더니 당연히 시간초과가 났다....

같이 코딩 공부하던 누나에게 물어봤는데 이럴때는 A/B를 구해야 할 때에 A%B가 0이 되는지로 판단하면 된다고 한다!! 이걸 잘 활용하도록 하자.

 4. 추가적으로 만약 접점을 구할 때에 나누는 값이 0이 되면 터져버리므로 그게 0이 되면 걍 안구하면 된다. 어차피 못구한다.

 5. 도형의 크기는 최소한으로 해야 하기 때문에, 각 값들을 얻을 때에 왼쪽, 오른쪽, 위, 아래 모든 값들을 최소와 최대를 사용하여 받아준다.

 6. 그리고 얻게 된 x와 y를 arraylist에 넣어준다.

 

( 도형 구하기 - 먼저 점찍기 )

 7. 아까 구했던 최소와 최대를 통해 얻은 상하좌우 값들을 통해 범위를 구하여, 이를 이용해 .을 찍어준다.

- 참고로 나는 최소값을 (0, 0)으로 두어서 풀었다. 예를 들어

ex) (-4, -4) (4, 4) (2, 4) 이런 값들이 있으면 (0, 0) (8, 8) (6, 8) 이런식으로다.

 8. 그리고 위에서 arraylist에 저장되어 있는 좌표를 가져와 답을 구하면 된다.

( 도형 별찍기 )

 9. 좌표값들을 하나씩 꺼내주면서 answer의 (Y축의최대값-좌표의 Y축)의 인덱스에 존재하는 (좌표의 X축-Y축의최소값) 을 *로 바꾸어 주면 된다.

 10. 이렇게 하면 값을 구할 수 있을 것이다... 왠만한 3단계 문제들보다 어려웠던 이유는 long과 integer에 대한 개념을 확실히 잡아두지 않으면 쉽지 않게 느껴질 수 있을 것이다. 내가 그랬다...

 

 

어마어마한 꿀팁을 주자면 본인이 시간초과가 떴다고 했을때 그게 진짜 시간때문에 생긴 문제인지 다시 생각해 보는게 좋다.

아마 여기서 나는 시간초과의 경우 Integer를 long으로 잘 변경하고 double을 사용해서 시간낭비하지 않으면 해결될 것이다.

코드

반응형