문제 : 틱택토에서 실수를 했던, 안했던 그 결과가 규칙에 맞는지 아닌지 판단하기

해결 방법 :

1. 9칸짜리 보드에서 'O'의 개수, 'X'의 개수, '.'의 개수 검사
2. 9칸짜리 보드에서 가로/세로/대각선으로 "OOO", "XXX"인지 검사
3. 선공인 'O'가 이겼을 때와 후공인 'X'가 이겼을 때로 구분

• 선공과 후공이 동시에 이겼다면 규칙에 안맞음
• 선공이 이겼을 때 후공의 개수는 선공보다 하나 적어야 함
• 후공이 이겼을 때 선공의 개수는 후공보다 하나 많거나 똑같아야 함
• 둘다 이기지 못했을 때 선공의 개수는 후공보다 하나 많거나 똑같아야 함

4.예외로 빈칸이 9개일 때는 규칙에 맞고 굳이 다 검사할 필요 없어서 바로 리턴

class Solution {
    public int solution(String[] board) {
        int answer = -1;
        int onum = 0, xnum = 0, empty = 0;
        boolean owin = false, xwin = false;

        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(board[i].charAt(j) =='O'){
                    onum++;
                }else if(board[i].charAt(j) =='X'){
                    xnum++;
                }else{
                    empty++;
                }
            }
        }


        if(empty == 9){
            answer = 1;
            return answer;
        }

        // 가로 세로 승자 확인
        for(int i=0;i<3;i++){
            if(board[i].equals("OOO")){
                owin = true;
            }
            if(board[0].charAt(i) == 'O' && board[1].charAt(i) == 'O'){
                if(board[2].charAt(i) == 'O'){
                    owin = true;
                }
            }
            if(board[i].equals("XXX")){
                xwin = true;
            }
            if(board[0].charAt(i) == 'X' && board[1].charAt(i) == 'X'){
                if(board[2].charAt(i) == 'X'){
                    xwin = true;
                    System.out.println("is");
                }
            }
        }
        //대각선 승자 확인
        if(board[0].charAt(0) == 'O' && board[1].charAt(1) == 'O'){
            if(board[2].charAt(2) == 'O'){
                owin = true;
            }
        }
        if(board[0].charAt(2) == 'O' && board[1].charAt(1) == 'O'){
            if(board[2].charAt(0) == 'O'){
                owin = true;
            }
        }
        if(board[0].charAt(0) == 'X' && board[1].charAt(1) == 'X'){
            if(board[2].charAt(2) == 'X'){
                xwin = true;
            }
        }  
        if(board[0].charAt(2) == 'X' && board[1].charAt(1) == 'X'){
            if(board[2].charAt(0) == 'X'){
                xwin = true;
            }
        }


        if(owin == true && xwin == true){
            answer = 0;
        } else if(owin == true && xwin == false){
            if(onum - xnum == 1){
                answer = 1;
            }else{
                answer = 0;
            }
        } else if(owin == false && xwin == true){
            if(onum - xnum == 0){
                answer = 1;
            } else {
                answer = 0;
            }
        } else{
            if(onum - xnum == 0 || onum - xnum == 1){
                answer = 1;
            } else{
                answer = 0;
            }
        }

        return answer;
    }
}

• 여기서 한참 헤맨 이유. 세로 체크할 때 코드를 아래와 같이 잘못 짬. 그래서 뭐가 틀린건 지 한참 고민하다가 테스트 케이스 추가하면서 확인해봤다.

  if(board[i].charAt(0) == 'O' && board[i].charAt(0) == 'O'){
       if(board[i].charAt(2) == 'O'){
           owin = true;
       }
  }

우선 BFS 문제를 백준에서 푼 적이 있었고 단순하게 방문 노드만 체크하면 된다고 생각했다. 하지만 여기서의 포인트는 BFS의 level을 따지는 것이었다.

백준에서 풀었던 과거 코드까지 되돌아보게 된 계기가 되었다.

우선 나의 원래 코드는 아래와 같다

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

public class Main{
    static Queue<Integer> bq = new LinkedList<>();
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void print_bq(Queue<Integer> bq) throws Exception{
        while(!bq.isEmpty()) {
            bw.write(bq.poll() + " ");
        }
        bw.write("\n");
    }

    public static void bfs(ArrayList<ArrayList<Integer>> adj, boolean[] visited, Queue<Integer> q, int N, int M) {
        //종료조건
        if(N <= M) {
            if(bq.size() == N) return ;
        } else {
            if(bq.size() == M+1) return ;
        }

        int front = q.peek();
        //예외처리 : 시작점이 간선이 없는 정점일 때 
        if(adj.get(front).size() == 0) {
            bq.add(front);
            return ;
        }

        if(visited[front] != true) {
            q.poll();
            bq.add(front);
            visited[front] = true;

            for(int i=0;i<adj.get(front).size();i++) {
                if(visited[adj.get(front).get(i)] != true) {
                    q.add(adj.get(front).get(i));
                }
            }
        } 
        else {
            q.poll();
        }

        bfs(adj, visited, q, N, M);
    }



    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());
        boolean[] visited = new boolean[N+1];
        Queue<Integer> q = new LinkedList<>();

        //인접리스트
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
        //인접리스트 생성
        for(int i=0;i<=N;i++) {
            adj.add(new ArrayList<Integer>());
        }
        //인접리스트 구현
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            int val1 = Integer.parseInt(st.nextToken());
            int val2 = Integer.parseInt(st.nextToken());
            adj.get(val1).add(val2);
            adj.get(val2).add(val1);
        }


        //인접리스트 정렬
        for(int i=0;i<=N;i++) {
            Collections.sort(adj.get(i));
        }

        //call bfs
        q.add(V);
        bfs(adj, visited, q, N, M);
        print_bq(bq);

        br.close();
        bw.flush();
        bw.close();
    }
}

이 코드에서 레벨을 구해주면 된다고 생각했지만, 나의 코드 자체가 레벨을 구하기에 상당히 지저분한 코드였다ㅋ..

그래서 결국은 q에 추가된 크기만큼 레벨을 구해주면 된다는 아이디어엔 접근했지만 내 코드를 수정하는 걸론 불가능했다. 구글링 결과 매우 심플한 bfs 코드를 봤고 정말 배우는 시간이었다.

열심히 알고리즘 공부해야겠다. 정말 공부된다.

뿌 듯

몇 개의 테스트 코드에서 시간 제한에 걸렸기 때문이다.

코드를 바꿔서 다시 도전해봤지만 계속 시간 제한에 걸림.

구글링 결과 -> 자료구조의 문제. https://developyo.tistory.com/114 https://www.baeldung.com/java-hashset-arraylist-contains-performance

List.contains와 Set.contains는 시간 복잡도에서 크게 차이가 난다. List.contains -> O(n) Set.contains -> O(1)

자료구조를 set으로 바꾸면 해결된다.

일단 결론적으로 구글링을 했다. https://walk-through-me.tistory.com/66

매우 심플한 문제

필요한 변수는 기름양과 주유소이다.

for문으로 주유소들을 따라간다. 각 주유소에서 기름을 채우고 그 후 다음 주유소를 갈 때 필요한 양만큼 뺀다. 이 때 -가 되면 갈 수 없으므로 기름양을 0으로 초기화한다. 그리고 이 때, 주유소 변수를 i+1로 세팅해준다. 다음 주유소부터 새롭게 시작하는 것이다. 새로 시작한 주유소에서부터 기름양이 0으로 안떨어진다면 문제 없이 갈 수 있다는 뜻이 된다.

우선 결론적으로 말하자면 이 문제에서 40/105점을 획득했다.

코드를 짜면서도 시간 제한에 걸릴 것 같다고 생각했는데 역시나 걸렸다.

내가 생각한 방식은 아래와 같다.

1. 펠린드롬 여부 검사
2. 아니라면 인덱스를 0에서부터 증가시켜가며 스트링 전체를 다시 펠린드롬 검사

구글링 해본 결과 접근 방식은 비슷했으나 훨씬 간결한 방식으로 할 수 있었다. https://ifuwanna.tistory.com/464 https://medium.com/geekculture/optimize-palindrome-index-hackerrank-solution-ceeb5bc91e1d

1. 펠린드롬 여부 검사 나 : 스트링 길이가 홀수/짝수인지 구분하여 mid 인덱스를 둔다. mid 앞 스트링 == 역순(mid 뒤 스트링) -> 펠린드롬 구글링 결과 : 앞, 뒤 인덱스를 조정해가며 각 캐릭터별로 같은지 비교하는 방식. (펠린드롬의 의미를 생각해보니 매우 명쾌한 풀이였다.)

구글링 후 나만의 코드를 작성해보았는데 여전히 틀리는 케이스가 있음

왤케 어려운건지.. 일단 패스..