프로그래머스-숫자 게임; Java

https://programmers.co.kr/learn/courses/30/lessons/12987

코딩테스트 연습 - 숫자 게임

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        Arrays.sort(A);
        Arrays.sort(B);
        boolean[] visited = new boolean[B.length];
        
        int cnt = 0;
        int Bidx = 0;   //a보다 큰 b가 있기 시작할 인덱스를 저장
        for(int a : A) {
        	for(int i = Bidx; i<B.length; i++) {
        		if(B[i] > a && !visited[i]) {
        			cnt++;
        			visited[i] = true;
        			Bidx = i+1;
        			break;
        		}
        	}
        	//남은 a보다 큰 b가 존재하지 않는다.
        	if(Bidx > B.length) {
        		break;
        	}
        }
        
        return cnt;
    }
}

 

B가 최대 승률을 가지려면, A[i]의 점수보다 높은 B 중에서 제일 작은 B[j]를 배정해줘야한다. 

A 배열을 선형탐색하면서 각 요소 A[i]보다 큰 B를 찾으면 그 B의 사용 표시(visited)와 이긴 횟수 증가해주고 다음 A[i+1]도 반복해준다. 

 

고민했던 점

1. A와 B를 순서대로 비교하는게 정답?

for문을 돌리면서 A[i] vs B[i] 비교하여 승률을 계산하는 방법이 정답일까 고민을 했는데, 정답이 아니라고 생각한다.

반례는 A가 {2, 5, 6, 8} B가 {1, 1, 3, 4}일 때 이다. 최대 승리 횟수는 1이다. 근데 순서대로 비교하면 0이 나온다.

 

2. 큐를 사용할까?

최근에 큐를 공부해서 큐가 적절할 수도 있다고 생각했다. 중간 데이터를 삭제하기 때문에 효율적이라고 생각했다.

A, B 배열을 정렬 후, B의 요소들을 큐에 넣는다.

for문으로 A를 탐색하면서 A<B인 B를 큐에서 제거한다. 제거할 때마다 승리 횟수를 증가한다.

이렇게하면 B를 사용여부를 저장하는 boolean 배열을 사용할 필요가 없고 / B를 앞에서부터 탐색하고 / 삭제하는 B가 중간에 위치해서 큐를 사용해도 좋을 것이라 생각했는데, 배열 B->큐로 옮기는 코드를 for문으로 적으면서 뭔가 이상해서 그만뒀다. ㅋㅋㅋ 배열>큐로 복사하는 방법이 for문 돌리면서 요소 한개씩 offer하는 방법밖엔 없나? 

근데 큐로 문제 푼 사람도 있었다... 

 

+

import java.util.*;

public int solution(int[] A, int[] B) {
        int answer = 0;
        
        Arrays.sort(A);
        Arrays.sort(B);
        
        int idxA = 0, idxB = 0;
        while (idxA < A.length) {
			if(idxB >= B.length)	break;
            if (A[idxA] < B[idxB]) {
                answer++;
                idxB++;
                idxA++;
            }else{
            	idxB++;
            	
            }
        }
        
        return answer;
    }

ㄴ 아씨  코드블럭 수정 칸이랑 내 ide에서보면 탭 정상적인데 맨날 블로그에 옮기면 ㅇㅈㄹ 남! 개짱나! (대충 화난 노란 병아리 임티)

 

이 코드는 투포인터 같이 푸는 풀이이다. 

---

 

 

레벨 3이길래 쫄아서 문제 풀었는데,, 한번에 맞아버리기~^^!

그래두 여러 경우의 수를 생각하느랴 1시간 반정도 걸림 ㅎㅅㅎ;;;