문제 주소
https://school.programmers.co.kr/learn/courses/30/lessons/152996
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 2 ≤ weights의 길이 ≤ 100,000
- 100 ≤ weights[i] ≤ 1,000
- 몸무게 단위는 N(뉴턴)으로 주어집니다.
- 몸무게는 모두 정수입니다.
입출력 예
| weights | result |
| [100,180,360,100,270] | 4 |
제출 코드
import java.util.*;
class Solution {
public long solution(int[] weights) {
long answer = 0;
Map<Integer,Long> values = new HashMap<>();
Map<Integer,Long> origins = new HashMap<>();
for(int i=0;i<weights.length;i++){
int element = weights[i];
long count = 0;
count = origins.getOrDefault(element,0L);
count++;
origins.put(element,count);
count = values.getOrDefault(element*2,0L);
count++;
values.put(element*2,count);
count = values.getOrDefault(element*3,0L);
count++;
values.put(element*3,count);
count = values.getOrDefault(element*4,0L);
count++;
values.put(element*4,count);
}
List<Map.Entry<Integer,Long>> list = new ArrayList<>(values.entrySet());
for(Map.Entry<Integer,Long> entry : list){
long count = entry.getValue();
long combination = 0;
if(count<2){
continue;
}else{
combination = count*(count-1)/2;
}
answer+=combination;
}
//아예 같은 수인 것 배제
list = new ArrayList<>(origins.entrySet());
for(Map.Entry<Integer,Long> entry : list){
long count = entry.getValue();
long same = 0;
if(count<2){
continue;
}else{
same = count*(count-1);//(count*(count-1)/2)*2 -> element*2에서 센 경우 *3과 *4 에서 배제
}
answer-=same;
}
return answer;
}
}풀이 설명
1) 조합으로 나올 수 있는 값들의 쌍을 계산함
나올 수 있는 값을 모두 등록해두고
중복되는것의 개수의 쌍을 구하면 됨
nC2 = n*(n-1)/2 만큼 해주면 된다
count가 2개다 → 쌍은 1개
3개 → 3개
4개 → 6개
3!/2!*1! → 3 개
2) 이미 원래 값이 같아서 발생하는 중복을 제거함
그런데 100 100 100 150 150이 있었다고 하면
100 100 100
→ 200,300,400
다 같다고 나와서 중복이 발생함
애초부터 값이 같았던 경우에 200 에서도 300에서도 400에서도 count가 되니까 그걸 걸러주기 위해서
origins HashMap을 도입했음
origins에 이미 들어있으면 그 count만 올리고 저기는 안 올려줌
100 100 100 과 150 150 이 있었다고 하면
통으로 계산하면 5*4/2 = 10개 이렇게 나옴
이 10개를 나눠보면
근데 100 100 100 끼리 쌍 → 3개
150 150 끼리 쌍 → 1개
100과 150끼리 쌍 → 3*2개 이렇게 구성되어 있음
근데
100끼리 이미 쌍을 구해줬으니까 그만큼을 나중에 빼줌
100끼리 쌍 하는 갯수 : 3*2/2 에다가 300,400에서 겹치는 만큼 빼줘야 하니까 *2
150끼리 쌍 하는 갯수 2*1/2 * 2
그러면 중복없이 값이 잘 나온다
풀이과정
처음에는 정말 단순하게 for 문을 두번 돌려서 풀었다
a:b = a:b
가 되면 시소 짝꿍이라고 하면 될 것 같음
둘을 나눠서 4/2, 1, 3/2 , 4/3 중의 하나가 되면 되네
그러니까 시간초과가 남
import java.lang.Math;
class Solution {
public long solution(int[] weights) {
long answer = 0;
for(int i=0;i<weights.length;i++){
for(int j=i+1;j<weights.length;j++){
double divided = Math.max((double)weights[i],(double)weights[j]);
double divider = Math.min((double)weights[i],(double)weights[j]);
divided = divided/divider;
if(divided==1||divided==2||divided==1.5||divided==4.0/3.0){
answer++;
}
}
}
return answer;
}
}
테스트 1 〉 통과 (0.08ms, 71.2MB)
테스트 2 〉 통과 (0.11ms, 82.6MB)
테스트 3 〉 통과 (0.13ms, 83.4MB)
테스트 4 〉 통과 (606.27ms, 99.5MB)
테스트 5 〉 통과 (1902.04ms, 102MB)
테스트 6 〉 통과 (5214.70ms, 87.8MB)
테스트 7 〉 통과 (7639.28ms, 105MB)
테스트 8 〉 실패 (시간 초과)
테스트 9 〉 실패 (시간 초과)
테스트 10 〉 실패 (시간 초과)
테스트 11 〉 실패 (시간 초과)
테스트 12 〉 실패 (시간 초과)
테스트 13 〉 실패 (시간 초과)
테스트 14 〉 실패 (시간 초과)
테스트 15 〉 실패 (시간 초과)
테스트 16 〉 통과 (0.07ms, 71.6MB)
테스트 17 〉 통과 (0.11ms, 72.5MB)
break문을 걸어봤더니 테스트 8번은 통과가 되었지만 아직 느렸다
class Solution {
public long solution(int[] weights) {
long answer = 0;
Arrays.sort(weights);
for(int i=0;i<weights.length;i++){
double divider =(double)weights[i];
for(int j=i+1;j<weights.length;j++){
double divided =(double)weights[j];
divided = divided/divider;
if(divided==1||divided==2||divided==1.5||divided==4.0/3.0){
answer++;
}//앞이 반드시 뒤보다 작아
if(divided>2){
break;
}
}
}
return answer;
}
}테스트 1 〉 통과 (0.57ms, 63.9MB)
테스트 2 〉 통과 (0.56ms, 77.2MB)
테스트 3 〉 통과 (0.54ms, 72.5MB)
테스트 4 〉 통과 (238.26ms, 78.6MB)
테스트 5 〉 통과 (728.38ms, 79.2MB)
테스트 6 〉 통과 (1934.05ms, 88.4MB)
테스트 7 〉 통과 (2651.61ms, 78.7MB)
테스트 8 〉 통과 (5352.56ms, 79.7MB)
테스트 9 〉 실패 (시간 초과)
테스트 10 〉 실패 (시간 초과)
테스트 11 〉 실패 (시간 초과)
테스트 12 〉 실패 (시간 초과)
테스트 13 〉 실패 (시간 초과)
테스트 14 〉
테스트 15 〉
테스트 16 〉 통과 (0.57ms, 72.2MB)
테스트 17 〉 통과 (0.56ms, 82.9MB)
그래서 for문으로는 할 방법이 없을 것 같아서
달리기 경주 문제, 의상 문제를 떠올리고 HashMap을 써야겠다고 생각하게 되었다
import java.util.*;
class Solution {
public long solution(int[] weights) {
long answer = 0;
Map<Integer,Integer> values = new HashMap<>();
for(int i=0;i<weights.length;i++){
int element = weights[i];
int count = 0;
count = values.getOrDefault(element*2,0);
count++;
values.put(element*2,count);
count = values.getOrDefault(element*3,0);
count++;
values.put(element*3,count);
count = values.getOrDefault(element*4,0);
count++;
values.put(element*4,count);
}
List<Map.Entry<Integer,Integer>> list = new ArrayList<>(values.entrySet());
for(Map.Entry<Integer,Integer> entry : list){
int count = entry.getValue();
int combination = 0;
if(count<2){
continue;
}else{
combination = count*(count-1)/2;
}
answer+=combination;
System.out.println(entry.getKey()+","+entry.getValue()+":"+combination);
}
return answer;
}
}
이렇게 하니까 중복이 안 걸러져서 더 세어졌다
테스트 1
입력값 〉 [100, 180, 360, 100, 270]
기댓값 〉 4
실행 결과 〉 실행한 결괏값 6이 기댓값 4과 다릅니다.
출력 〉
400,2:1
720,2:1
200,2:1
1080,2:1
300,2:1
540,2:1
그래서
origins에 이미 들어있으면 그 count만 올리고 저기는 안 올려줌
100 100 100 과 150 150 이 있다고 치자 넷 다 300을 만들 수가 있어
근데 100 100 100 끼리 쌍 → 3개
150 150 끼리 쌍 → 1개
100과 150끼리 쌍 → 3*2개 이렇게 나온단말이지…?
실제로는 10개
통으로 계산해도 5*4/2 = 10개 이렇게 나온다고
100끼리 이미 쌍을 구해줬잖아?
200 이랑 400에서도 중복되니까…
여기서 원래 같은것들끼리 구한 쌍의 개수를 빼줌
100끼리 쌍 하는 갯수 : 3*2/2 에다가 300,400에서 겹치는 만큼 빼줘야 하니까 *2
150끼리 쌍 하는 갯수 2*1/2 * 2
import java.util.*;
class Solution {
public long solution(int[] weights) {
long answer = 0;
Map<Integer,Integer> values = new HashMap<>();
Map<Integer,Integer> origins = new HashMap<>();
for(int i=0;i<weights.length;i++){
int element = weights[i];
int count = 0;
count = origins.getOrDefault(element,0);
count++;
origins.put(element,count);
count = values.getOrDefault(element*2,0);
count++;
values.put(element*2,count);
count = values.getOrDefault(element*3,0);
count++;
values.put(element*3,count);
count = values.getOrDefault(element*4,0);
count++;
values.put(element*4,count);
}
List<Map.Entry<Integer,Integer>> list = new ArrayList<>(values.entrySet());
for(Map.Entry<Integer,Integer> entry : list){
int count = entry.getValue();
int combination = 0;
if(count<2){
continue;
}else{
combination = count*(count-1)/2;
}
answer+=combination;
//System.out.println(entry.getKey()+","+entry.getValue()+":"+combination);
}
//아예 같은 수인 것 배제
list = new ArrayList<>(origins.entrySet());
for(Map.Entry<Integer,Integer> entry : list){
int count = entry.getValue();
int same = 0;
if(count<2){
continue;
}else{
same = count*(count-1);//(count*(count-1)/2)*2 -> element*2에서 센 경우 *3과 *4 에서 배제
}
answer-=same;
//System.out.println(entry.getKey()+","+entry.getValue()+"same:"+same);
}
return answer;
}
}테스트 1 〉 통과 (0.15ms, 75.3MB)
테스트 2 〉 통과 (0.30ms, 74.8MB)
테스트 3 〉 통과 (0.29ms, 77MB)
테스트 4 〉 통과 (14.31ms, 78.7MB)
테스트 5 〉 통과 (27.98ms, 81.7MB)
테스트 6 〉 통과 (30.28ms, 96.6MB)
테스트 7 〉 통과 (35.41ms, 93.6MB)
테스트 8 〉 통과 (51.28ms, 98.1MB)
테스트 9 〉 통과 (81.64ms, 99.9MB)
테스트 10 〉 통과 (77.60ms, 108MB)
테스트 11 〉 통과 (74.73ms, 96.9MB)
테스트 12 〉 실패 (79.57ms, 96.6MB)
테스트 13 〉 실패 (60.42ms, 110MB)
테스트 14 〉 실패 (72.11ms, 95.2MB)
테스트 15 〉 실패 (57.14ms, 112MB)
테스트 16 〉 통과 (0.11ms, 79.7MB)
테스트 17 〉 통과 (0.14ms, 68.9MB)내 생각에 이제 로직은 빈틈이 없는데
왜 실패가 나올까 찾아보다가 int 대신 long을 써줘야 한다는 것을 깨닫고 long으로 바꿔줌
import java.util.*;
class Solution {
public long solution(int[] weights) {
long answer = 0;
Map<Integer,Long> values = new HashMap<>();
Map<Integer,Long> origins = new HashMap<>();
for(int i=0;i<weights.length;i++){
int element = weights[i];
long count = 0;
count = origins.getOrDefault(element,0L);
count++;
origins.put(element,count);
count = values.getOrDefault(element*2,0L);
count++;
values.put(element*2,count);
count = values.getOrDefault(element*3,0L);
count++;
values.put(element*3,count);
count = values.getOrDefault(element*4,0L);
count++;
values.put(element*4,count);
}
List<Map.Entry<Integer,Long>> list = new ArrayList<>(values.entrySet());
for(Map.Entry<Integer,Long> entry : list){
long count = entry.getValue();
long combination = 0;
if(count<2){
continue;
}else{
combination = count*(count-1)/2;
}
answer+=combination;
}
//아예 같은 수인 것 배제
list = new ArrayList<>(origins.entrySet());
for(Map.Entry<Integer,Long> entry : list){
long count = entry.getValue();
long same = 0;
if(count<2){
continue;
}else{
same = count*(count-1);//(count*(count-1)/2)*2 -> element*2에서 센 경우 *3과 *4 에서 배제
}
answer-=same;
}
return answer;
}
}이렇게 제출하고 통과함
테스트 1 〉 통과 (0.12ms, 71.3MB)
테스트 2 〉 통과 (0.30ms, 77.4MB)
테스트 3 〉 통과 (0.30ms, 68.7MB)
테스트 4 〉 통과 (19.99ms, 87.1MB)
테스트 5 〉 통과 (23.47ms, 110MB)
테스트 6 〉 통과 (27.91ms, 91.2MB)
테스트 7 〉 통과 (40.35ms, 93.1MB)
테스트 8 〉 통과 (42.54ms, 86MB)
테스트 9 〉 통과 (58.81ms, 90.3MB)
테스트 10 〉 통과 (71.56ms, 98.7MB)
테스트 11 〉 통과 (67.62ms, 98.5MB)
테스트 12 〉 통과 (75.64ms, 106MB)
테스트 13 〉 통과 (66.64ms, 109MB)
테스트 14 〉 통과 (70.26ms, 94.8MB)
테스트 15 〉 통과 (60.47ms, 111MB)
테스트 16 〉 통과 (0.12ms, 72.5MB)
테스트 17 〉 통과 (0.14ms, 76.2MB)'Coding Test' 카테고리의 다른 글
| [백준] 수들의 합 (0) | 2024.03.30 |
|---|---|
| [프로그래머스] 테이블 해시 함수 (0) | 2024.03.27 |
| [프로그래머스] 프로세스 (1) | 2024.03.25 |
| [프로그래머스] 기능개발 (0) | 2024.03.25 |
| [프로그래머스] 의상 (0) | 2024.03.25 |