배열: 실패율 | 방문 길이

실패율 -> 1차 실패

https://school.programmers.co.kr/learn/courses/30/lessons/42889?language=java

프로그래머스

 

[실패 코드]

/*
[문제나누어 생각하기]

실패율을 직접 구하고 저장할 필요가 없는 문제
-> 아니다 실패율이 그저 카운트가 아니구나..

실패율을 각각 구하는 공식 부터 세워야 겠구나

그 실패율을 가지고 크기별 정렬을 하긴 할건데 
그 실패율 정렬가지고 스테이지를 어떻게 환산하여 반환하지?

2중 배열을 ㅈ나 노가다 돌려?

[예외 생각 하기]
딱히 없어 보임

[입력 크기]
스테이지 길이 = 200000 = nlogn =sort() 사용 가능
스테이지 개수 =  500 = n^3 사용가능

[데이터 흐름]
해시맵도 좋을거 같고, 배열도 좋을거 같다.
===========================================
[의사코드]
1. 먼저 스케이지스 저열부터 하자.
    1-1. 스테이지의 현재 길이 구해야함. 계속 빠질거임.
    1-2. 카운트 추가
    
2. 반복문 1부터 스테이지 개수인 n만큼 반복한다. 
    2-1. int i 랑 같을때만 계속해서 stages에서 뽑아냄 해당 회수 기억해
    2-2. 해당 카운트 / stages.length
    2-3. 2차원배열에 {스테이지, 값} 형태로 계속 저장

3. 정리된거 저장할때 comparator 재정의 하여 2번째값 기준으로 내림차순 정렬
4. 첫번째 인덱스만 출력
    

*/
import java.util.*;

class Solution {
    public int[] solution(int N, int[] stages) {
//         [의사코드]
// 1. 먼저 스케이지스 저열부터 하자. 
        Arrays.sort(stages);
    // 1-1. 스테이지의 현재 길이 구해야함. 계속 빠질거임.
        int leaveLength = stages.length;
    // 1-2. 카운트 추가
        int cnt = 0;
        
        ArrayList<ArrayList<Double>> repo = new ArrayList<>();
// 2. 반복문 1부터 스테이지 개수인 n만큼 반복한다. 
        for(int i=1; i<=N; i++){
//     2-1. int i 랑 같을때만 계속해서 stages에서 뽑아냄 해당 회수 기억해
            int idx=0;
            ArrayList<Double> inner = new ArrayList<>();
            inner.add(i+0.0);
            while(true){
                if(stages[idx] == i){
                    cnt++;
                    idx++;
                }
                else{
                    double res = cnt/leaveLength;
                    leaveLength -= cnt;
                    cnt = 0;
                    inner.add(res);
                    repo.add(inner);
                    break;
                }
            }
        }
        
        Collections.sort(repo, new Comparator<ArrayList<Double>>() {
            @Override
            public double compare(ArrayList<Double> o1, ArrayList<Double> o2) {
                return o1.get(1) - o2.get(1); 
            };
        });
        
        int[] firstColumn = repo.stream()
            .filter(row -> !row.isEmpty())
            .mapToInt(row -> (int) Math.floor(row.get(0))) // double -> int 변환
            .toArray();
            
        return firstcolumn;
    }

//     2-2. 해당 카운트 / stages.length
//     2-3. 2차원배열에 {스테이지, 값} 형태로 계속 저장

// 3. 정리된거 저장할때 comparator 재정의 하여 2번째값 기준으로 내림차순 정렬
// 4. 첫번째 인덱스만 출력
    
    //결국 막히네 못풀겠어 ㅠㅠ 뭔 에러가 이리 많이 뜨는거야
}

 

[답안과 나의 차이 비교]

1. 나는 키와 밸류를 알기 위해 이중 리스트를 사용하려 했다. <->답안은 키와 밸류니까 바로 HashMap으로 깔끔하게 사용

-> 원인분석: Java HashMap에 익숙하지 않으니 손이 안갔다. 그쪽으로

 

2. 도전자 배열의 사용유무: 나는 사용 안함

-> 원인 분석: 내부에 조건으로 반복횟수를 동적으로 결정하는 반복문을 넣어서 도전자 수를 카운트하고 초기화하려고 했는데

이렇게 하니까 더 더러워진거 같다.

 

3. int[] challenger = new int[N+2];

-> 5개의 스테이지가 있으면 1 2 3 4 5 가 끝이 아님. 5+1 즉 모든 스테이지를 다 깬 사람이 있음. 그래서 N+1

근데 앞에 0부터 시작하니까 그냥 거를려고 N+2

 

[답지 주의]

import java.util.HashMap;

class Solution {
	public int[] solution(int N, int[] stages) {
		
        // 1 스테이지별 도전자 수를 구함
    	int[] challenger = new int[N + 2];
		for (int i = 0; i < stages. length; i++) {
        	challenger [stages[i]] += 1;
        }
    
    	// 2 스테이지별 실패한 사용자 수 계산
    	HashMap<Integer, Double> fails = new HashMap<>();
		double total = stages.length;
		
		// 3 각 스테이지를 순회하며, 실패율 계산
		for (int i = 1; i <= N; i++) {
    		if (challenger[i] == 0) { // 4 도전한 사람이 없는 경우, 실패율은 0
    			fails.put(i, 0.);
    		}
       		else {
       			fails.put(i, challenger[i] / total); // 5 실패율 구함
       		    total -= challenger[i]; // 6 다음 스테이지 실패율을 구하기 위해 현재 스테이지의 인원을 뺌
			}
    	}
    	// 7 실패율이 높은 스테이지부터 내림차순으로 정렬
		return fails.entrySet().stream().sorted(
        	(o1, 02) -> Double.compare(o2.getValue(), 01.getValue())).mapToInt(
            HashMap. Entry :: getKey).toArray();
    }
}

 

의사코드

1. 스테이지별 도전자 수를 미리 구함

2. 스테이지별 실패한 사용자 수 계산

3. 각 스테이지 순회하며, 실패율 계산

4. 도전한 사람 없으면 0

5. 실패율 저장

6. 다음 스테이지 실패율에 바로 영향하게 총인원 조정

7. 실패율이 높은 스테이지부터 내림차순 정렬

 

HashMap.entrySet().stream()

---

방문길이 -> 1차실패(권장시간 초과)

저자 권장시간 40분

 

[실패 코드]

/*
문제 나누어 생각하기
1. t r b l = [U R D L] 배열을 이용하여 캐릭터 이동시킴

2. 그와중에 좌표 평면에 밟았는지 안밟았는지를 계산하는 용 값 추가

3. 그 다음 전체 탐색해서 밟힌 값 개수 카운트 반환 

4. 벽에 부딪히는 경우의 수에선 해당 명령 무시!

5. dirs 문자열로 명령이 주어지면 파싱해서 명령 실행

6. 명령을 받았을때 올바르게 동작시키코드도 필요

7. 나중에 카운팅하는 코드도 필요


제한 조건 확인
dirs는 500 이하. 따라서 dirs는 n^2 널널
전체 맵의 총 개수는 100 따라서 맵탐색은 근데 선형탐색할거니까 100말곤 없음.


의사코드 작성하기

1. ground 배열 생성: 2차원배열로 평면을 나타내고 내부값은 boolean

2. character 현재 좌표를 표현할 변수 cx, cy를 0, 0으로 할당

3. up 매서드 구현: cy가 최대값 5가 아닌이상은 cy를 +1 함
right left down 매서드도 이와 같은 맥락

4. step 매서드 구현: cx cy 값을 바탕으로 ground 내부값을 true 로 바꿈

5. action 매서드 구현: dirs를 char 단위로 반복하며 switch case로 u r l d 매서드를 호출

6. action은 answer를 반환


*/
import java.util.*;

class Solution {
            
// 1. ground 배열 생성: 2차원배열로 평면을 나타내고 내부값은 boolean
    // boolean[][] ground = new boolean[6][6];
    //참으로 멍청하구나
    boolean[][] ground = new boolean[11][11];

// 2. character 현재 좌표를 표현할 변수 cx, cy를 0, 0으로 할당
    // int cx=0, cy=0;
    // 참으로 멍청하구나
    int cx=5, cy=5;

// 3. up 매서드 구현: cy가 최대값 5가 아닌이상은 cy를 +1 함
// right left down 매서드도 이와 같은 맥락
    public boolean up(){
        if(this.cy == 10) return false;
        this.cy++;
        return true;
    }
    public boolean right(){
        if(this.cx == 10) return false;
        this.cx++;
        return true;
    }
    public boolean down(){
        if(this.cy == 0) return false;
        this.cy--;
        return true;
    }
    public boolean left(){
        if(this.cx == 0) return false;
        this.cx--;
        return true;
    }

// 4. step 매서드 구현: cx cy 값을 바탕으로 ground 내부값을 true 로 바꿈
    public int step(int cnt){
        if(!ground[cy][cx]){
            ground[cy][cx] = true;
            cnt++;
        }
        //System.out.println(cnt);
        //아하 현재 좌표를 밟았냐가 중요한게 아니라 
        //직전좌표에서 직후 좌표로 가는 길을 밟았냐를 추적해야되는구나.. 뭐 이런
        return cnt;
    }

// 5. action 매서드 구현: dirs를 char 단위로 반복하며 switch case로 u r l d 매서드를 호출    
    public int solution(String dirs) {
        int answer = 0;
        
        for(int i=0; i<dirs.length(); i++){
            char c = dirs.charAt(i);
            switch (c){
                case 'U': 
                    if(up()) answer = step(answer);
                    break;
                case 'R': 
                    if(right()) answer = step(answer);
                    break;
                case 'D': 
                    if(down()) answer = step(answer);
                    break;
                case 'L': 
                    if(left()) answer = step(answer);
                    break;
                default:
                    break;
            }
        }
// 6. action은 answer를 반환    
        return answer;
    }
}

 

[저자 풀이]

주의

1. 중복좌표가 아닌 중복 경로를 카운팅 하지 않는 다는 점 충분히 고민 -> 결론 HashSet<String> 으로 중복 제거

2. 개념상 음수좌표가 있음을주의 -> 중점을 0,0이 아닌 5,5로 음수는 0으로 양수는 +5만큼 더해서 구현

 

import java.util.HashMap;
import java.util.HashSet;

class Solution {

	// 1 좌표평면을 벗어나는지 체크하는 메서드
	private static boolean isValidMove(int nx, int ny) {
		return 0 <= nx && nx < 11 && 0 <= ny && ny < 11;
    }
    
    // 2 다음 좌표 결정을 위한 해시맵 생성
	private static final HashMap<Character, int[]> location = new HashMap<>();

	private static void initLocation() {
		location.put('U', new int[]{0, 1});
		location.put('D', new int[]{0, -1});
		location.put('L', new int[]{-1, 0});
		location.put('R', new int[]{1, 0});
    }

	public int solution(String dirs) {
		initLocation();
		int x = 5, y = 5;
		HashSet<String> answer = new HashSet<>(); // 3 겹치는 좌표는 1개로 처리하기 위함
		// 4 주어진 명령어로 움직이면서 좌표 저장
		for (int i = 0; i < dirs. length(); i++) {
			int[] offset = location.get(dirs.charAt(i));
			int nx = x + offset[0];
			int ny = y + offset[1];
			if (!isValidMove(nx, ny)) // 5 벗어난 좌표는 인정하지 않음
				continue;
		//A에서 B로 간 경우 B에서 A도 추가해야 함(총 경로의 개수는 방향성이 없음)
		answer.add(x + " " + y + " " + nx + " " + ny);
		answer.add(nx + " " + ny + " " + x + " " + y);

		// 7 좌표를 이동했으므로 업데이트
		x = nx;
		y = ny;
		return answer.size() / 2;
    }
}