https://www.acmicpc.net/problem/2493

 

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1

www.acmicpc.net

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        Stack<int[]> stack = new Stack<>();
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) { // 탑은 0번부터가 아닌 1번부터 시작
            int top = Integer.parseInt(st.nextToken()); // 현재 확인중인 탑
            while (!stack.isEmpty()) {
                if (stack.peek()[1] >= top) {
                    bw.write(stack.peek()[0] + " ");
                    break;
                }
                stack.pop();
            }
            if (stack.isEmpty()) {
                bw.write("0 ");
            }
            stack.push(new int[]{i, top});
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

[설명]

제일 왼쪽 탑부터 스택에 담긴 값들과 비교해가면 로직을 반복한다.

스택에는 높이가 작은 순서부터 큰순으로 오름차순으로값이 담기게 된다.

 

높은 6탑은 첫번째 탑이기 때문에 비교할 스택들이 없어 0을 bw.write 한 후 {탑의 위치, 탑의 높이}를 스택에 담는다.

 

높이 9탑은 스택에 담긴 6보다 높이가 높다. 그 뜻은 앞으로 확인할 탑들은 모두 높이 9 탑 때문에 스택에 담겼던 높이 6 탑을 만날 수 없다. 그러므로 높이 6 스택은 pop해준다. 높이 9 탑을 스택에 담는다.

 

높이 5탑과 스택에 담긴 높이9 탑과 비교해준다. 높이9 탑에 신호가 닿기 때문에 높이9의 위치를 출력해준 후 스택에 높이 5 스택을 담아준다.

 

높이 7탑과 스택에 담긴값과 비교해준다. 스택의 가장 위의 값인 높이 5와 비교를 해본다. 스택에 담겼던 스택 5탑은 현재 확인중인 높이 7탑 때문에 앞으로 모든신호를 못받게된다. 그러므로 스택에서 pop 해준다. 그 다음 스택에 담긴 값 높이 9랑 비교 하면 신호가 9에 닿는다. 9의 위치를 출력후 높이7 탑을 스택에 담는다.

 

높이 4탑과 스택에 담긴 값을 비교해본다. 스택의 top에 있는값 높이 7인탑과 비교해보니 바로 신호가 닿는다. 높이 7탑의 위치를 출력해준다.

https://www.acmicpc.net/problem/7682

 

7682번: 틱택토

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입

www.acmicpc.net

 

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    static char[][] board;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        String input = "";
        board = new char[3][3];
        while (true) {
            st = new StringTokenizer(br.readLine(), " ");
            input = st.nextToken();
            if (Objects.equals(input, "end")) {
                break;
            }
            int index = 0;
            int xCount = 0;
            int oCount = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    board[i][j] = input.charAt(index);
                    if (board[i][j] == 'O') {
                        oCount++;
                    } else if (board[i][j] == 'X') {
                        xCount++;
                    }
                    index++;
                }
            }
            //게임판이 꽉 채워졌을 때
            //X가 먼저 말을 놓았음으로 O보다 1개 무조건 많아야 한다.
            if (xCount + oCount == 9 && xCount - oCount == 1) {
                //한 명이 빙고를 완성하면 게임이 끝나기 때문에
                //둘 다 빙고가 성립될 수 없다.
                if (isValid('X') && isValid('O')) {
                    bw.write("invalid\n");
                } else if (isValid('O')) {//말이 꽉 채워진 경우에는 O가 이길 수 없다
                    bw.write("invalid\n");
                } else { // X 가 이긴경우
                    bw.write("valid\n");
                }
            } else { // 게임판이 꽉 채워지지 않았을 경우
                //한 명이 빙고를 완성하면 게임이 끝나기 때문에
                //둘 다 빙고가 성립될 수 없다.
                if (isValid('X') && isValid('O')) {
                    bw.write("invalid\n");
                } else if (isValid('X') && xCount - oCount == 1) { //X가 이겼을 땐, X가 선공이어서 무조건 O보다 하나 많아야 한다
                    bw.write("valid\n");
                } else if (isValid('O') && xCount == oCount) { //O가 이겼을 땐, O가 후공이여서 X와 O의 개수가 같아야 한다
                    bw.write("valid\n");
                } else { // 아직 게임판이 덜채워졌는데 게임이 끝날 수는 없다
                    bw.write("invalid\n");
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static boolean isValid(char c) {
        //가로가 성립할 때
        for (int i = 0; i < 3; i++) {
            int count = 0;
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == c) {
                    count++;
                }
            }
            if (count == 3) {
                return true;
            }
        }

        //세로가 성립할 때
        for (int i = 0; i < 3; i++) {
            int count = 0;
            for (int j = 0; j < 3; j++) {
                if (board[j][i] == c) {
                    count++;
                }
            }
            if (count == 3) {
                return true;
            }
        }

        // 대각선이 성립할 때
        if (board[0][0] == c && board[1][1] == c && board[2][2] == c) {
            return true;
        }
        if (board[0][2] == c && board[1][1] == c && board[2][0] == c) {
            return true;
        }

        return false;
    }
}

 

[설명]

단순 구현 문제이다. 크게 봤을 때는 게임판에 말이 가득 찼을 경우와 가득차지 않았을 경우로 나눌수 있다.

 

  1. 말이 가득찼을 경우(X가 무조건 O보다 한개 많다)
    • X와 O둘다 동시에 이길 수는 없다
    • O가 이길수는 없다
    • X가 이긴다
    • 둘다 못 이긴다
  2. 말이 가득차지 않았을 경우
    • X와 O둘다 동시에 이길 수는 없다
    • X가 이겼을 땐 X가 선공이라 X가 O보다 1개 많아야 한다
    • O가 이겼을 땐 O가 후공이라 X와 O는 같아야 한다
    • 아직 게임판이 덜 채워졌는데 게임이 끝날 수는 없다

 

'코딩테스트' 카테고리의 다른 글

백준 16234번: 인구 이동[JAVA]  (1) 2024.03.13
백준 2493번: 탑[JAVA]  (0) 2024.03.12
백준 9372번: 상근이의 여행[JAVA]  (0) 2024.03.09
백준 2668번: 숫자고르기[JAVA]  (0) 2024.03.07
백준 5972번: 택배 배송[JAVA]  (0) 2024.03.07

try-finally 사용 예시 (비효율적)

import java.io.*;

public class TryFinallyExample {
    public static String firstLineOfFile(String path) throws IOException {
        BufferedReader br = null;
        try {
            br = new BufferedReader(new FileReader(path));
            return br.readLine();
        } finally {
            if (br != null) {
                br.close(); // 자원을 명시적으로 해제해야 함
            }
        }
    }
}

이 예시에서는 finally 블록을 사용해 파일 리더를 명시적으로 닫아야한다. 번거로울 뿐만 아니라 close 메서드에서 예외가 발생하면 원래의 예외가 가려질 수도 있어서 문제가 된다.

 

try-with-resources 사용 예시 (권장)

import java.io.*;

public class TryWithResourcesExample {
    public static String firstLineOfFile(String path) throws IOException {
        // try-with-resources 구문 사용
        try (BufferedReader br = new BufferedReader(new FileReader(path))) {
            return br.readLine(); // 자동으로 리소스를 해제해 줍니다.
        }
    }
}

이 예시에서는 BufferedReader의 인스턴스를 자동으로 관리한다. 구문이 끝나면 자동으로 BufferedReader가 닫히므로 명시적으로 자원을 해제하는 코드를 작성할 필요가 없다. 또한 try 블록 내에서 예외가 발생하더라도 자원은 안전하게 해제된다. close메서드에서 예외가 발생하는 경우에도 원래 예외를 숨기지 않고 보조 예외(suppressed exception)로 처리한다.

 

결론 : 꼭 회수해야하는 자원을 다룰 때는 try-finally 말고, try-with-resources를 사용하자.

반드시 사용하자. 예외는 없다.

코드를 더 간결하고 안정하게 만들고 자원 해제 과정에서 발생할 수 있는 잠재적인 문제를 방지한다.

혹시나 코드가 더 길어지더라도 try-with-resources를 사용하자.

자바는 두 가지 객체 소멸자를 제공한다.

finalizer는 예측할 수 없고, 상황에 따라 위험할 수 있어 일반적으로 불필요하다.

cleaner는 finalizer보다는 덜 위험하지만, 여전히 예측할 수 없고, 느리고, 일반적으로 불필요하다.

사용 예시 : 

public class ProblematicResourceHolder {
    private SomeResource resource;

    public ProblematicResourceHolder(String resourceName) {
        this.resource = new SomeResource(resourceName);
    }

    // Finalizer를 사용한 자원 해제 시도 - 사용을 피해야 함!
    @Override
    protected void finalize() throws Throwable {
        try {
            if (resource != null) {
                resource.release(); // 자원 해제 시도
            }
        } finally {
            super.finalize();
        }
    }
}

finalizer를 사용하는 간단한 예시 이다.

안전망 역할이나 중요하지 않은 네이티브 자원 회수용으로만 finalizer 혹은 cleaner를 사용하는게 좋다.

하지만 그냥 둘다 사용 자체를 하지않는게 좋은것 같다.

 

 

 

결론 : finalizer, cleaner 둘다 사용하지말자

자바의 가비지 컬렉션(garbage collection) 메커니즘이 자동으로 메모리 관리를 해주더라도, 더 이상 사용하지 않는 객체에 대한 참조를 계속 유지하는 것은 메모리 누수(memory leak)를 일으킬 수 있다. 특히, 컬렉션 객체 같은 경우는 개발자가 명시적으로 객체 참조를 해제하지 않으면, 의도치 않게 메모리 누수가 발생할 수 있다.

 

스택 구현에서의 메모리 누수 방지 예시 : 

public class Stack {
    private Object[] elements;
    private int size = 0;
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    public Stack() {
        elements = new Object[DEFAULT_INITIAL_CAPACITY];
    }

    public void push(Object e) {
        ensureCapacity();
        elements[size++] = e;
    }

    public Object pop() {
        if (size == 0)
            throw new EmptyStackException();
        Object result = elements[--size];
        elements[size] = null; // 다 쓴 참조 해제
        return result;
    }

    /**
     * 스택이 커질 필요가 있을 때 크기를 늘려준다.
     */
    private void ensureCapacity() {
        if (elements.length == size) {
            elements = Arrays.copyOf(elements, 2 * size + 1);
        }
    }
}

여기서 핵심은 pop 메서드에서 스택에서 제거된 객체(Object result = elements[--size])에 대한 참조를 null로 설정하여 명시적으로 해제하는 부분이다. 이제 가비지 컬렉터가 필요할 때 이전에 스택에 저장되었던 객체를 회수할 수 있다. 만약

pop 메서드에서 객체 참조를 null로 설정하지 않는다면 스택이 그 객체에 대한 참조를 계속 유지하게 된다. 더 이상 사용되지 않는 객체임에도 불구하고 가비지 컬렉터가 회수하지않아 장시간 동안 어플이 실행될 경우 메모리 누수가 일어난다. 

 

결론 : 다 쓴 객체 참조를 해제하는 것은 메모리 관리와 애플리케이션 성능에 있어 중요한 사항이다.

+ Recent posts