[Lv.2] 시소 짝꿍 : Java

프로그래머스

 

 

 

이해하기

처음 접근했던 방법은 다음과 같다.

• 조합을 사용해서 가능한 쌍들을 전부 list에 저장한다.
  • {100, 180}, {100, 360}, {100, 100}, {100, 270}, {180, 360}, {180, 100}, {180, 270}, {360, 100}, {360, 270}, {100, 270}
• check 함수를 사용하여 균형 여부를 확인한다.
  • 둘이 몸무게가 같다면 return true
  • 둘의 몸무게가 {2, 3}, {2, 4}, {3, 4}, {3, 2}, {4, 2}, {4, 3} 거리 배열과 곱했을 때 균형을 이룬다면 return true
  • 다 아니면 return false

결과는 테스트 3/17 통과 - 14개에서 시간 초과가 떴다.

다시 문제를 보니 weights 길이가 최대 100,000이라 조합의 과정도 오래 걸리고 이를 하나하나 확인하는 것도 오래 걸렸던 것 같다.

 

 

오늘의 참고 블로그는 여기⬇️

[Java] 시소 짝꿍 - Lv2 프로그래머스

 

이 분의 풀이는 다음과 같다.

• Map을 활용하여 중복여부 체크
• 정렬을 활용하여 뒤에 오는 값들을 2/3, 1/2, 3/4 계산

너무 쉬운 접근이라 신기했다.

 

 

문제풀이

import java.util.*;

class Solution {
    public long solution(int[] weights) {
    	long answer = 0;
        Arrays.sort(weights);
        Map<Double, Integer> map = new HashMap<>();
        for(int i : weights) {
    		double a = i*1.0;
    		double b = (i*2.0)/3.0;
    		double c = (i*1.0)/2.0;
    		double d = (i*3.0)/4.0;
    		if(map.containsKey(a)) answer += map.get(a);
    		if(map.containsKey(b)) answer += map.get(b);
    		if(map.containsKey(c)) answer += map.get(c);
    		if(map.containsKey(d)) answer += map.get(d);
    		map.put((i*1.0), map.getOrDefault((i*1.0), 0)+1);
        }
        
        return answer;
    }
}

 

        Arrays.sort(weights);

 

정렬해주면 {100, 100, 180, 270, 360} 순이 된다.

 

        for(int i : weights) {
    		double a = i*1.0;
    		double b = (i*2.0)/3.0;
    		double c = (i*1.0)/2.0;
    		double d = (i*3.0)/4.0;

 

이 부분이 신박했는데, i가 예를 들어 100이라면 a = 100, b = 66.667, c = 50, d = 75가 된다.

 

    		if(map.containsKey(a)) answer += map.get(a);
    		if(map.containsKey(b)) answer += map.get(b);
    		if(map.containsKey(c)) answer += map.get(c);
    		if(map.containsKey(d)) answer += map.get(d);

 

만약 map에 a, b, c, d 가 포함되어 있다면 균형을 이루는 값이 있다는 것이니 answer += map.get() 해준다.

앞에서 예를 든 100은 첫번째 인덱스의 100이기에 아직 든 것이 없어서 map 비교가 불가하겠지만 360을 가지고 예를 들어볼 수 있다.

 

i = 360이면 a = 360, b = 240, c = 180, d = 270 이고, map에는 100, 180, 270이 들어있을 것이다.

그렇다면 360과 균형을 이룰 수 있는 값 중 180, 270 두 값이 이미 map에 있기에 결과적으로 answer += 2 가 된다.

360과 균형을 이루는 값이 2개 존재한다는 것이다.

 

map.put((i*1.0), map.getOrDefault((i*1.0), 0)+1);

 

이 부분은 map의 value를 설정하는 것인데, weights에 해당 값이 몇 개 있는지 체크하는 것이다.

예를 들어 100은 2번 나타나니 (100, 2) 가 되고, 나머지는 1번씩 나타나니 (180, 1), (270, 1), (360, 1)이 될 것이다.

 

 

 

접근이 아주 잘못되지는 않았다고 생각한다!

오히려 이 문제를 스스로 생각해 낸 로직으로 풀이해 볼 수 있다는 것 자체가 많이 성장했다고 느껴진다 ㅋㅋ

 

하지만 반성할 점으로 문제를 제대로 읽자...를 들 수 있을 것 같다.

시간 초과의 이유를 파악하는 것도 중요!