Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- re_lunchu
- softeer
- 스마트팩토리
- 백준
- JavaScript
- 비전공자
- 그리디
- 프로그래머스
- Algorithm
- 소프티어
- 파이썬
- 힙큐
- Python
- 딥러닝
- 자바
- heapq
- cim
- Baekjoon
- MES
- 탐욕법
- Java
- programmers
- 알고리즘
- GAN
- alogorithm
- 자바스크립트
- 토이프로젝트
- 현대
- cs공부
- 현대자동차
Archives
- Today
- Total
eaz_coding
[Programmers] 시소 짝꿍(Python, Java) 본문
문제
요약
시소의 중심으로부터 2, 3, 4 거리에 앉을 수 있다.
시소에서 무게 비율과 거리의 곱이 같은 경우는 몇개인가?
문제
https://school.programmers.co.kr/learn/courses/30/lessons/152996
풀이
Python
풀이1(시간초과)
하나씩 순회하며 확인하는 코드는 시간초과가 발생했다.
값이 몇개씩 있는 경우를 빼서 확인해야 할 것 같다.
def solution(weights):
answer = 0
weights.sort()
for i in range(len(weights)-1):
for j in range(i+1, len(weights)):
if weights[i] == weights[j]:
answer += 1
elif weights[i]/weights[j] in (2/3, 2/4, 3/4):
answer += 1
elif weights[j] > weights[i] * 2:
break
return answer
풀이2(정답)
Counter를 이용해서 개수를 확인하고 set로 중복되는 값을 제거했다.
반복문을 두개 쓸 필요 없이 해당 값에 비율을 곱해서 있는지 없는지 확인했다.
같은 숫자가 여러개인 경우는 nC2로 n*(n-1)/2.
from collections import Counter
def solution(weights):
answer = 0
counter = Counter(weights)
weights = set(weights)
for k, v in counter.items():
if v >= 2:
answer += v*(v-1)//2
for w in weights:
if w * (2/3) in weights:
answer += counter[w] * counter[w*(2/3)]
if w * (2/4) in weights:
answer += counter[w] * counter[w*(2/4)]
if w * (3/4) in weights:
answer += counter[w] * counter[w*(3/4)]
return answer
Java
위의 파이썬 코드를 자바로 그대로 바꾼 코드이다.
사실 이것보다 단순한 자바 풀이가 있지만, 자바 언어도 익힐겸 그대로 바꾸면서 stream, for 반복문 등을 써보았다.
이 문제에서 아주 사소한 것에서 계속 오답이 발생했는데 Long으로 둔 Map의 value값을 Integer로 두면 오답처리가 된다.
이유는 Integer의 범위 때문에. Integer의 표현 범위는 -2,147,483,648 ~ 2,147,483,647이다.
최대 길이만큼 모두 같은 수라고 했을 때, 100,000 * 99,999 / 2 = 4,999,950,000로 범위를 넘어서게 된다. 따라서 Integer가 아닌 Long으로 둬야 한다.
확실히 파이썬 보다 신경써야 할 게 많다.
import java.util.*;
class Solution {
public Map<Double, Long> Counter(int[] lst) {
Map<Double, Long> dict = new Hashtable<Double, Long>();
for (int i: lst) {
dict.put((i * 1.0), dict.getOrDefault((i * 1.0), (long)0) + 1);
}
return dict;
}
public long solution(int[] weights) {
long answer = 0;
Map<Double, Long> counter = Counter(weights);
answer += counter.values().stream()
.filter(v -> v >= 2)
.mapToLong(v -> v * (v - 1) / 2)
.sum();
for (Double k : counter.keySet()) {
if (counter.containsKey(k*2/3)) {
answer += counter.get(k) *counter.get(k*2/3);
}
if (counter.containsKey(k*2/4)) {
answer += counter.get(k) * counter.get(k*2/4);
}
if (counter.containsKey(k*3/4)) {
answer += counter.get(k) * counter.get(k*3/4);
}
}
return answer;
}
}
'eaz_algorithm' 카테고리의 다른 글
[Programmers] 방금그곡 (Python, Java) (1) | 2024.06.03 |
---|---|
[Programmers] 배달(Python, Java) (0) | 2024.06.03 |
[Programmers] 숫자 카드 나누기(Python, JavaScript) (0) | 2024.05.29 |
[Programmers] 호텔 대실 (0) | 2024.05.27 |
[Programmers] 연속된 부분 수열의 합 (0) | 2024.05.24 |