본문 바로가기
Today I Learned 2024. 3. 20.

(24.03.20) 연습문제 오류 해결 도전

Article Study와 용어정리 데일리 미션을 좀 빠르게 끝내고 백준 알고리즘 연습 문제 풀고 

알고리즘 풀이 정리랑 필요한 공부를 좀 하려고 했는데..

 

이 한 문제인데 쉬운 알고리즘인데 계속 메모리가 메모리 부족 오류가 뜨면서 이걸로 하루종일을 잡아먹었다..

 

TIL양이 그래서 적긴 하지만,, 결과를 보고 살짝 아쉬운 하루이긴 하다

 


연습문제 메모리 부족 해결 도전

독기가 생겨서 내가 모르는게 대체 뭔데! 하면서 메모리 줄이려고 int 선언 수까지 줄여봤지만 정답이고 뭐고 그냥 메모리 부족만 뜬다.. IDE 에서는 계속 정상적으로 답이 반환되는데 그래서 스트레스가 이만저만이 아니었다..

  • split 을 StringTokenizer으로 교체 : 메모리부족
더보기
import java.io.*;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main {
    public static void main(String args[]) throws IOException {
        InputStreamReader st = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(st);
        //총 명수 지정
        int total_number = Integer.parseInt(br.readLine());

        //선수 배열 배열 만들기
        String[] players = new String[total_number];
        for (int i = 0; i < total_number; i++) {
            players[i] = br.readLine();
        }

        //서로 싸웠을 때 이긴 사람 앞으로 보내기
        int[] ranking = new int[total_number];
        for (int i = 0; i < total_number; i++) {
            ranking[i] = i;
        }

        //힘 겨루기 시작
        for (int i = 0; i < players.length; i++) {
            for (int j = i + 1; j < players.length; j++) {
                //힘 겨루기
                StringTokenizer st1 = new StringTokenizer(players[i], " ");
                StringTokenizer st2 = new StringTokenizer(players[j], " ");
                int playerA_power = Integer.parseInt(st1.nextToken());
                int playerA_magicring = Integer.parseInt(st1.nextToken());
                int playerB_power = Integer.parseInt(st2.nextToken());
                int playerB_magicring = Integer.parseInt(st2.nextToken());

                int playerA_totalpower = playerA_power + (playerB_power * playerA_magicring);
                int playerB_totalpower = playerB_power + (playerA_power * playerB_magicring);

                //이긴사람 앞으로
                if (playerA_totalpower < playerB_totalpower) {
                    int temp = ranking[i];
                    ranking[i] = ranking[j];
                    ranking[j] = temp;
                }
            }


        }
        for (int rank : ranking) {
            System.out.println(rank);
        }
    }

}

(위의 코드)

  1. 입력된 모든 값들을 하나하나 임의의 배열의 인덱스 값으로 지정
  2. 재귀 함수로 하나하나 비교
  3. 비교할 때마다 임의의 랭킹 배열에 순서를 인덱스 값으로 넣는 알고리즘 : 메모리 초과

→ 입력된 값 + 순서 값의 배열로 바굼 → 바꾼 값들을 문제가 원하는 식으로 비교 → 배열정렬

위의 단계를 좀더 나은 알고리즘을 위해 클래스와 compare, sort 메서드를 사용

수정 후 : 겨우 성공

더보기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static class Player implements Comparable<Player> {
        // 인스턴스 변수
        int index;
        int power;
        int magicring;

        // 생성자
        public Player(int index, int power, int magicring) {
            this.index = index;
            this.power = power;
            this.magicring = magicring;
        }

        @Override
        public int compareTo(Player other) {
            int totalPower = this.power + (other.power * this.magicring);
            int otherTotalPower = other.power + (this.power * other.magicring);
            return Integer.compare(totalPower, otherTotalPower);
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int total_number = Integer.parseInt(br.readLine());

        // 레슬러들의 순서, 힘, 마법반지 내용의 새로운 배열 만들기
        Player[] players = new Player[total_number]; // public 클래스라 새롭게 지정, 배열로 지정 가능
        for (int i = 0; i < total_number; i++) {
            String[] playerInfo = br.readLine().split(" "); //매개변수로 넣은 것
            int power = Integer.parseInt(playerInfo[0]);
            int magicring = Integer.parseInt(playerInfo[1]);
            players[i] = new Player(i, power, magicring);
        }

        Arrays.sort(players); // compareTo 반환값 기준으로 정렬

        for (int i = players.length - 1; i >= 0; i--) {
            System.out.println(players[i].index+1);
        }

        br.close();
    }
}

입력값 + 입력 순서에 대해서 변수를 지정 index power magicring

변수를 가진 배열로 지정하는 Player 클래스 정의 Player[index, power, magicring]

main클래스 정의시작

입력 값의 줄을 split으로 분리, 줄 순서 + power + magicring를 매개변수로 하는 Player클래스들을  배열로 만듬 players 배열에 저장 (Player[] players, players배열 형태를을 Player 클라스로 지정)

players안의 Player(int index, int power, int magicring) 데이터들 끼리 문제의 식대로 비교

Arrays.sort를 비교 후 올림차순으로 정렬

다시 역순으로 정렬 출력 ( 문제에서 가장 많이 이긴 사람 = compare 맨 마지막)먼저 나오라고 했기 때문에

 

 


가장 문제는 Java가 util로 어느정도 메모리를 많이 잡아 먹기 위해 내가 계속 정의하고 선언하고 이러는 작업을 대신 해준다는 것  특히 정렬은 sort 메서드를 자유롭게 사용할 수 있어야 한다고 생각했다..

 

정렬은 알고리즘 문제가 순서대론 나열하라가 나올 수 있기 떄문에 매우 중요하다고 생각..

추가로 에러가 생겼기 때문에 팀원 분과 ChatGPT에 물어본 내용을 합쳐서 

  • implements
  • @Override

에 대해서 좀더 정리할 필요가 있다