Coding Test Meeting #4

이번 문제

 

https://leetcode.com/problems/number-of-ways-to-select-buildings/

Number of Ways to Select Buildings - LeetCode

 

Code

/*

문제 파악 및 재정의

문자 '0', '1'로 구성되어있는 문자열 s가 주어진다. 3 <= s.length(); <= 10^5
0은 사무실 1은 레스토랑을 의미하는데 연속된 건물로 구성되지 않게 3개의 건물을 선택하려 한다.
즉 010 또는 101을 만족시키는 s의 조합의 수를 구하라

알고리즘 및 자료구조 선택

어떻게...?
010 / 101
s[0] ... s[1] != s[0] ... add ... s[i] == s[0]
s[0] ... function(s[0] diff s[i])

점화식?
memoization s[0]s[1] -> next s[0]s[1]다시(이미 된 상태인거 암) -> 바로 다음
어딘가에 저장 s[0]s[1]은 다른 상태라는 것을... ?
구현

회고
*/

class Solution {
  public long numberOfWays(String s) {
    long ans = 0;
    // before[i] := # of i before current char
    int[] before = new int[2];
    // after[i] := # of i after current char
    int[] after = new int[2];
    after[0] = (int) s.chars().filter(c -> c == '0').count();
    after[1] = s.length() - after[0];

    for (char c : s.toCharArray()) {
      int num = c - '0';
      --after[num];
      if (num == 0)
        ans += before[1] * after[1];
      else
        ans += before[0] * after[0];
      ++before[num];
    }

    return ans;
  }
}

https://school.programmers.co.kr/learn/courses/30/lessons/160585

프로그래머스

 

Code

/*

문제파악 및 재정의

틱택토 -> O X O X O X -> 가로, 세로, 대각선으로 완성되면 승리 3칸이 완성되지 않는다면 무승부

1.차례에 맞지 않는 진행
2.승리 후 게임 진행
O, X, .(빈칸)으로 구성된 board를 참조하여 규칙을 지킨 틱택토일 경우 1 아니라면 0을 반환

O . X
. O .
. . X

선,후공 세트 + 3칸으로 게임을 끝냈을 때 진행 여부 판별

O나 X가 가로, 세로, 3칸을 완성했는가? -> 3칸 완성 이후 게임의 진행? -> 
가로 [0][0] [0][1] [0][2]
세로 [0][0] [1][0] [2][0]
대각선 -> [0][0] [1][1] [2][2] i == j or [2][0] [1][1] [0][2] -> i + j == board.length -1


자료구조 및 알고리즘 선택
3*3 이차원 배열 -> 순회

1. get O, X Counts and isGameSet
2. isGameSet ? -> 가로 / 세로 / 대각선
3.1 isGameSet -> true -> O와 X의 갯수 불일치
3.2 isGameSet -> false -> O와 X의 갯수 일치 단 O와 X의 합이 9일 경우 불일치 가능

구현


회고

*/
import java.util.*;


class Solution {
    public int solution(String[] board){
        int result = 1;
        Map<String, Boolean> checkGame = new HashMap<>();
        String[] vertical = convertString(board,3);
        String[] cross = convertString(board, 2);

        checkGame = isGameSet(board, checkGame);
        checkGame = isGameSet(vertical, checkGame);
        checkGame = isGameSet(cross, checkGame);

        int oCnt = getCounts(board,'O');
        int xCnt = getCounts(board,'X');

        if(checkGame.containsKey("O") && checkGame.containsKey("X")) return 0;
        if(xCnt > oCnt || oCnt - xCnt > 1) return 0;
        if(checkGame.containsKey("O")) {
            if(oCnt == xCnt) return 0;
        }
        if(checkGame.containsKey("X")) {
            if(oCnt > xCnt)
                return 0;
        }
        return result;
    }
    
    public String[] convertString(String[] board, int option) {
        String[] temp = new String[option];
        StringBuilder sb = new StringBuilder();
        if(option == 3) {
            for(int idx = 0; idx < 3; idx++){
                for(int sidx = 0; sidx < 3; sidx++){
                    sb.append(board[sidx].charAt(idx));
                }
                temp[idx] = sb.toString();
                sb.delete(0,3);
            }
        } else {
            for(int idx = 0; idx < 3; idx++) {
                for(int sidx = 0; sidx < 3; sidx++){
                    if(idx == sidx) sb.append(board[idx].charAt(sidx));
                }
            }
            temp[0] = sb.toString();
            sb.delete(0,3);
            for(int idx = 0; idx < 3; idx++) {
                for(int sidx = 0; sidx < 3; sidx++){
                    if(idx+sidx == 2) sb.append(board[idx].charAt(sidx));
                }
            }
            temp[1] = sb.toString();
        }

        return temp;
    }

    public int getCounts(String[] board, char ox) {
        int count = 0;
        for(int idx = 0; idx < 3; idx ++) {
            for(int sidx = 0; sidx < 3; sidx++){
                if(ox == board[idx].charAt(sidx)) count++;
            }
        }
        return count;
    }

    public Map<String, Boolean> isGameSet(String[] board, Map<String, Boolean> map) {
        for(int idx = 0; idx < board.length; idx ++) {
            if(board[idx].equals("OOO")){
                map.put("O", true);
                
            }else if(board[idx].equals("XXX")) {
                map.put("X", true);
                
            }else {
                map.put(".", true);
            }
        }
        return map;
    }
}

---

https://github.com/Bloodevil/cote

GitHub - Bloodevil/cote

 

이번 코테 밋업에서는 이력서 첨삭에 대해 도움을 주셨다.

 

1. 프로젝트에 사용한 기술을 버전까지 명시할 것

2. pdf를 문서로 전환하여 링크를 사용하지 못할 수 있으니 짧은 설명을 병기할 것

3. 면접관은 스킬과 프로젝트 기반으로 질문한다. -> 질문을 유도할 리스트를 작성

4. 자신만의 api를 만들어 오픈소스로 제공

5. 작성한 글을 증명할 수 있는 자료를 바로 옆에 첨부 / ex) 이미지 or link or 부연설명