📍 문제 풀이
* 카카오 테크의 문제 풀이 발췌
자료구조, 반복문, 조건문 등 프로그래밍의 기초 개념들을 적절히 활용해서 푸는 문제
N명의 이름 리스트에 인덱스를 붙이고 NxN 2차원 배열에 선물을 주고 받은 횟수를 저장하는 방법으로 요구사항을 구현할 수 있다.
이름 리스트에 인덱스를 붙일 때, 언어에 따라 해시맵(HashMap) 등의 자료구조를 활용할 수 있고, 입력 사이즈가 작기 때문에 인덱스를 찾는 내장 함수를 사용하거나 반복문을 사용해 인덱스를 찾는 코드를 직접 구현해도 됩니다.
이를 위해, 각 gifts의 원소에서 선물을 준 사람 A와 받은 사람 B의 이름을 분리합니다. A의 인덱스가 i, B의 인덱스가 j라면 위에서 생성한 2차원 배열의 [i행][j열]의 값을 1 늘려 A가 B에게 보낸 선물의 수를 카운팅할 수 있습니다. gifts의 모든 기록을 저장하면 A가 B에게 준 선물의 총 수는 배열 [i행][j열]의 값, A가 모두에게 준 선물의 수는 배열 [i행]의 합, A가 모두에게 받은 선물의 수는 배열 [j행]의 합으로 구할 수 있습니다.
위 값들을 모두 구했다면 각 사람마다 자신을 제외한 N-1명에게 선물을 몇 개 받는지 카운팅하고, 그 최댓값을 갱신해 문제의 정답을 구할 수 있습니다.
📍 코드 설계
처음에는 이렇게 설계했는데
friends 이름(0행) 마다 received(1행), gave(2행) 배열 생성하기
gifts 순회하며 원소의 문자열 앞쪽이면 일치하는 이름의 2행을, 문자열 뒤쪽이면 일치하는 이름의 1행을 cnt++하여 receivedCnt, gaveCnt 채워넣기
선물 지수(presentIndex) = aGaveCnt - aReceivedCnt 계산하기
두 명의 친구를 선정하여 비교 시작
기록o : receivedCnt 비교해서 더 적게 받은 사람이 선물 받음
기록x || bReceivedCnt == aReceivedCnt : 선물 지수 비교해서 더 큰 사람이 선물 받음
문제에서 이런 입출력 예시를 괜히 주는 게 아니었다.
이 형태로 데이터를 저장한 다음, 적절하게 활용해서 정답을 도출해야 했다.
* 다른 사람 코드를 보고 개선할 부분을 찾아보았다
먼저 HashMap을 사용해 이름(String)을 인덱스(Integer)로 매핑했다.
첫 번째 정보는 이차원 배열 giftInfo로 선언했고
gifts의 각 원소값 'a b'를 통해 giftInfo[map.get(a)][map.get(b)]값을 1 늘려 a가 b에게 보낸 선물 수를 카운트했다.
선물 지수 giftFactor은 미리 구해두지 않고 giftInfo의 각 인덱스를 탐색하면서 항상 새로 구했다.
friends<=50이라서 비효율을 감수하고 직관적이고 간단하게 구현했다.
-> 선물 지수를 저장하는 배열을 만들어서 giftInfo값 저장할 때 giftFactor[giver]++, giftFactor[receiver]--로 동시에 갱신, calcGiftFactor() 없애기
giftInfo에서 i행 j열을 확인했으면 j행 i열도 확인한 것과 같으므로 visited 처리를 통해 중복 검사를 막았다.
-> visited 대신 이중 for문 조건에서 i<j인 경우만 검사하여 중복이 발생하지 않도록 하기
그리고 나머지는 문제에서 언급한 조건을 그대로 코드로 옮겼다.
-> i행 j열과 j행 i열의 값이 다른 경우와 아닌 경우로만 나누어도 되는데 0인 경우까지 고려하고 있어 조건문이 복잡해짐
📍 관련 개념 / 아이디어
(1) 인덱스를 매핑하는 방법
결론 - 데이터가 많으면 HashMap을 사용하자!!
그리고 Java 표준 라이브러리에는 배열에서 문자열 값의 인덱스를 바로 찾아주는 내장 함수가 없어서 어차피 HashMap 써야 함
1) HashMap
- 맵 검색이 빠름 : O(1)
- 메모리에 HashMap을 따로 둬야 함
Map<String, Integer> nameIdx = new HashMap<>();
for (int i = 0; i < friends.length; i++) {
nameIdx.put(friends[i], i);
}
int idx = nameIdx.get("muzi"); // 바로 O(1)에 인덱스 찾기
2) 반복문
- 구현이 단순, 추가 메모리 불필요
- 검색이 느림 : O(N)
int findIndex(String[] arr, String target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i].equals(target)) {
return i;
}
}
return -1; // 없으면 -1 반환
}
3) Java 8 Stream
- 코드가 간결
- 내부적으로 선형 탐색이라서 HashMap보다 느림 : O(N)
int idx = IntStream.range(0, friends.length)
.filter(i -> friends[i].equals("muzi"))
.findFirst()
.orElse(-1);
4) List.indexOf()
- 내부적으로 선형 탐색이라서 HashMap보다 느림 : O(N)
import java.util.*;
public class Main {
public static void main(String[] args) {
List<String> friends = Arrays.asList("muzi", "ryan", "frodo", "neo");
// 특정 이름의 인덱스 찾기
int idx1 = friends.indexOf("frodo"); // 2
int idx2 = friends.indexOf("neo"); // 3
int idx3 = friends.indexOf("apeach"); // -1 (없으면 -1 반환)
System.out.println("frodo index: " + idx1);
System.out.println("neo index: " + idx2);
System.out.println("apeach index: " + idx3);
}
}
(2) Generic Type / Raw Type
결론 - Collection은 제네릭 타입으로 선언해야 한다.
- 값을 꺼낼 때 자동으로 캐스팅 + 언박싱됨
- 형변환이 필요 없어서 편함
- 코드 가독성이 좋아짐
- 컴파일 시점에 타입이 강제되기 때문에 런타임 에러가 적음
Map map = new HashMap();
map.put("a", 1);
Object value = map.get("a"); // 반환 타입은 Object
int x = (Integer) value; // 직접 형변환 필요 -> 형변환 하지 않으면 런타임에 ClassCastExceptionMap<String, Integer> map = new HashMap<>();
map.put("a", 1);
int x = map.get("a"); // 자동 언박싱, 캐스팅 필요 없음
(3) Auto Unboxing
.intValue()는 Java 5 이하 버전에서 쓰는 방식
최근 버전에서는 자바 컴파일러가 Integer -> int으로 오토 언박싱해줌
Integer x = 10;
int y = x;
(4) Java Stream
- Java 8부터 지원
- 데이터를 선언적으로 다루는 기능
- 배열, 컬렉션을 반복문 없이 작업
- Collection (List, Map, Set)은 .stream() 메서드를 기본적으로 제공함
- Primitive Type 배열은 .stream() 메서드가 제공되지 않아서 Arrays.stream(arr)을 써서 배열을 스트림으로 바꿔야 함
List<String> names = Arrays.asList("Alice", "Bob", "Charlie");
// 1. stream() 호출
// 2. 중간 연산 (filter, map, sorted 등)
// 3. 최종 연산 (collect, forEach, sum 등)
List<String> result = names.stream()
.filter(name -> name.startsWith("A")) // A로 시작하는 것만
.map(String::toUpperCase) // 대문자로 변환
.toList(); // 리스트로 수집
System.out.println(result); // [ALICE]int[] arr = {1, 2, 3, 4};
Arrays.stream(arr) //Arrays.stream()으로 감싸야 함
.map(x -> x * x)
.forEach(System.out::println);
* 참고로 char[] 배열은 Arrays.stream()을 사용할 수 없다. error: no suitable method found for stream(char[]) 이런 에러가 발생함. 자바가 Object[] 배열로 간주하려고 시도하지만, 타입이 맞지 않기 때문.
📍 정답 코드
처음 짠 코드
import java.util.*;
class Solution {
static int[][] giftInfo;
public int solution(String[] friends, String[] gifts) {
StringTokenizer st;
//주고받은 선물 정보 저장
giftInfo = new int[friends.length][friends.length];
//선물 지수 저장
int[] giftFactor = new int[friends.length];
//맵을 사용해 friends 이름을 idx로 표현
Map<String, Integer> nameIdx = new HashMap<>();
for(int i=0; i<friends.length; i++){
nameIdx.put(friends[i], i);
}
//giftInfo에 값 입력
//gifts 배열의 'a b'를 [a의 인덱스][b의 인덱스]로 변환하여 선물 정보 저장
for(int i=0; i<gifts.length; i++){
st = new StringTokenizer(gifts[i]);
String f1 = st.nextToken();
String f2 = st.nextToken();
giftInfo[nameIdx.get(f1)][nameIdx.get(f2)]++;
}
//선물 지수 구하기
for(int i=0; i<friends.length; i++){
giftFactor[i] = calcGiftFactor(i);
}
//giftInfo의 요소를 하나씩 탐색
int[] result = new int[friends.length];
for(int i=0; i<giftInfo.length; i++){
for(int j=i+1; j<giftInfo.length; j++){
if(i==j) continue;
//0이 아니고(주고 받은 기록이 있고) 주고받은 수가 다르다면
//[a][b], [b][a] 중 더 큰 값의 행에 해당하는 사람이 선물 한 개 획득
if((giftInfo[i][j] != 0 || giftInfo[j][i] != 0)
&& giftInfo[i][j] != giftInfo[j][i]){
int val = giftInfo[i][j] > giftInfo[j][i] ? i : j;
result[val]++;
continue;
}
//0이거나 (주고 받은 기록이 없거나) 주고 받은 수가 같다면
//선물 지수가 더 큰 사람이 선물 한 개 획득
if((giftInfo[i][j] == 0 && giftInfo[j][i] == 0)
|| giftInfo[i][j] == giftInfo[j][i]){
//선물 지수가 다르다면, 선물지수 더 큰 사람이 선물 하나 획득
if(giftFactor[i] != giftFactor[j]){
int val = giftFactor[i] > giftFactor[j] ? i : j;
result[val]++;
}
}
}
}
int ans = Arrays.stream(result).max().getAsInt();
return ans;
}
//선물 지수 계산기
//선물 지수 = k가 준 선물의 수 - k가 받은 선물의 수
static int calcGiftFactor(int k){
//k가 선물을 준 수 : giftInfo의 k행 값의 합
int gaveCnt = Arrays.stream(giftInfo[k]).sum();
//k가 선물을 받은 수 : giftInfo의 k열 값의 합
int receivedCnt = Arrays.stream(giftInfo)
.mapToInt(row -> row[k])
.sum();
return gaveCnt - receivedCnt;
}
}
개선된 코드
선물 지수 계산을 일일이 하지 않고 giftFactor[giver]++, giftFactor[receiver]--로 구했다.
import java.util.*;
class Solution {
public int solution(String[] friends, String[] gifts) {
StringTokenizer st;
int[][] giftInfo = new int[friends.length][friends.length];
int[] giftFactor = new int[friends.length];
Map<String, Integer> nameIdx = new HashMap<>();
for(int i=0; i<friends.length; i++){
nameIdx.put(friends[i], i);
}
for(int i=0; i<gifts.length; i++){
st = new StringTokenizer(gifts[i]);
String f1 = st.nextToken();
String f2 = st.nextToken();
giftInfo[nameIdx.get(f1)][nameIdx.get(f2)]++;
giftFactor[nameIdx.get(f1)]++;
giftFactor[nameIdx.get(f2)]--;
}
int[] result = new int[friends.length];
for(int i=0; i<giftInfo.length; i++){
for(int j=i+1; j<giftInfo.length; j++){
if(i==j) continue;
if(giftInfo[i][j] != giftInfo[j][i]){
int val = giftInfo[i][j] > giftInfo[j][i] ? i : j;
result[val]++;
} else {
if(giftFactor[i] != giftFactor[j]){
int val = giftFactor[i] > giftFactor[j] ? i : j;
result[val]++;
}
}
}
}
int ans = Arrays.stream(result).max().getAsInt();
return ans;
}
}
다른 사람은 이렇게 풀었던데 맨 마지막에 ans 구하는 부분이 굉장히 좋은 아이디어인 것 같다.
리턴값이 받은 선물의 최댓값이기 때문에 모든 사람이 받은 선물 개수를 가지고있을 필요 없이 max값만 알아내면 된다.
첫 번째 for루프를 통해 각 행에 해당하는 사람이 더 많이 받았거나 (giftInfo[i][j] > giftInfo[j][i]) 선물 지수가 더 크면 (giftInfo[i][j] == giftInfo[j][i] && giftFactor[i] > giftFactor[j]) cnt를 1씩 늘린다.
이렇게 모든 사람을 검사하고 나서 max값을 리턴하면 된다.
import java.util.*;
class Solution {
public int solution(String[] friends, String[] gifts) {
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < friends.length; i++) {
map.put(friends[i], i);
}
int[] index = new int[friends.length];
int[][] record = new int[friends.length][friends.length];
for (String str : gifts) {
String[] cur = str.split(" ");
index[map.get(cur[0])]++;
index[map.get(cur[1])]--;
record[map.get(cur[0])][map.get(cur[1])]++;
}
int ans = 0;
for (int i = 0; i < friends.length; i++) {
int cnt = 0;
for (int j = 0; j < friends.length; j++) {
if(i == j) continue;
if (record[i][j] > record[j][i]) cnt++;
else if (record[i][j] == record[j][i] && index[i] > index[j]) cnt++;
}
ans = Math.max(cnt, ans);
}
return ans;
}
아이디어를 적용해서 내 코드도 수정해보았다.
import java.util.*;
class Solution {
public int solution(String[] friends, String[] gifts) {
StringTokenizer st;
int[][] giftInfo = new int[friends.length][friends.length];
int[] giftFactor = new int[friends.length];
Map<String, Integer> nameIdx = new HashMap<>();
for(int i=0; i<friends.length; i++){
nameIdx.put(friends[i], i);
}
for(int i=0; i<gifts.length; i++){
st = new StringTokenizer(gifts[i]);
String f1 = st.nextToken();
String f2 = st.nextToken();
giftInfo[nameIdx.get(f1)][nameIdx.get(f2)]++;
giftFactor[nameIdx.get(f1)]++;
giftFactor[nameIdx.get(f2)]--;
}
int[] result = new int[friends.length];
int ans = 0;
for(int i=0; i<giftInfo.length; i++){
int cnt = 0;
for(int j=0; j<giftInfo.length; j++){
if(i==j) continue;
if(giftInfo[i][j] > giftInfo[j][i]) cnt++;
else if(giftInfo[i][j] == giftInfo[j][i] && giftFactor[i] > giftFactor[j]) cnt++;
}
ans = Math.max(ans, cnt);
}
return ans;
}
}
그리고 나는 StringTokenizer가 더 익숙해서 썼는데
String.split("구분자")로 문자열을 구분자로 잘라서 String 배열로 쓰는 방법도 있다.
속도는 느리지만 가독성 있는 방법이라서 좋은 것 같다.
for (String str : gifts) {
String[] cur = str.split(" ");
index[map.get(cur[0])]++;
index[map.get(cur[1])]--;
record[map.get(cur[0])][map.get(cur[1])]++;
}for(int i=0; i<gifts.length; i++){
st = new StringTokenizer(gifts[i]);
String f1 = st.nextToken();
String f2 = st.nextToken();
giftInfo[nameIdx.get(f1)][nameIdx.get(f2)]++;
giftFactor[nameIdx.get(f1)]++;
giftFactor[nameIdx.get(f2)]--;
}출처
'코테' 카테고리의 다른 글
| [프로그래머스/Java] 도넛과 막대 그래프 (0) | 2025.10.05 |
|---|---|
| [백준/Java] 2823번 : 유턴 싫어 (0) | 2025.02.21 |
| [백준/Java] 2659번 : 십자카드 문제 (1) | 2025.02.20 |
| [백준/Java] 2012번 : 등수 매기기 (0) | 2025.02.19 |
| [백준/Java] 4803번 : 트리 (0) | 2025.02.18 |