씅의 기록하는 개발노트

문제출처

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

문제풀이

문자열을 처리하는 문제이다. 문제에서 남극언어는 "anta"로 시작되고 "tica"로 끝난다고 주어졌다. 즉 모든 언어를 읽기 위해서는 "a", "n", "t", "i", "c"는 무조건 배워야 한다는 것이다. 즉 k가 주어졌을때 이 5개는 배웠다 생각하고 처리했다. 주어진 n개의 단어에서 replaceAll 메서드를 활용해 5개 문자를 제외시켰고 문자를 배웠음을 의미하는 visit배열을 true처리해줬다.

이후 dfs를 이용해서 k개의 단어를 배울때까지 모든 방법을 전체 탐색해 k개의 단어를 배웠다면 읽을 수 있는 단어의 갯수를 카운팅해주는 방식으로 풀이했다.

지금 생각해보니 visit배열대신 비트마스크를 사용해도 될것같다. 아래글처럼 visit배열대신 비트마스크를 사용할 수 있다. 

프로그래머스 64064] - 카카오 불량 사용자

소스코드

https://github.com/sw93/algorithm/blob/master/BOJ_PS/BOJ_1062.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1062 {
    private static int n, k, ans;
    private static String[] words = new String[51];
    private static boolean[] visit = new boolean[26];
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;

    private static void init() throws Exception {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            String word = st.nextToken();

            // a n t i c 필수
            word = word.replaceAll("a" , "");
            word = word.replaceAll("n" , "");
            word = word.replaceAll("t" , "");
            word = word.replaceAll("i" , "");
            word = word.replaceAll("c" , "");
            words[i] = word;
        }
        visit['a'-'a'] = true;
        visit['n'-'a'] = true;
        visit['t'-'a'] = true;
        visit['i'-'a'] = true;
        visit['c'-'a'] = true;

    }
    private static void checkString() {
        int count = 0;

        for (int i=0; i<n; i++) {
            boolean isRead = true;
            for (int j=0; j<words[i].length(); j++) {
                if (!visit[words[i].charAt(j) - 'a']) {
                    isRead = false;
                    break;
                }
            }

            if (isRead) {
                count++;
            }
        }
        ans = Math.max(ans, count);
    }

    private static void dfs(int index, int depth) {
        if (depth == k) {
            checkString();
            return;
        }

        for (int i=index; i<26; i++) {
            if (visit[i]) continue;

            visit[i] = true;
            dfs(i, depth+1);
            visit[i] = false;
        }
    }

    public static void main(String[] args) throws Exception {
        init();
        // a n t i c 필수
        if (k < 5) {
            System.out.println(0);
            return;
        } else if (k == 26) {
            System.out.println(n);
            return;
        }
        k -= 5;
        dfs(0, 0);
        System.out.println(ans);
    }
}

문제출처

https://programmers.co.kr/learn/courses/30/lessons/1829

문제풀이

삼성 역량테스트를 준비할때 많이 풀어본 유형이다. 기본적인 BFS문제로 완전탐색을 했다. BFS탐색을 할때마다 영역의 개수가 1개씩 증가하고 각 영역의 크기를 구하면 되는 문제다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%B9%B4%EC%B9%B4%EC%98%A4%ED%94%84%EB%A0%8C%EC%A6%88%20%EC%BB%AC%EB%9F%AC%EB%A7%81%EB%B6%81.cpp

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int dy[] = { 0, -1, 0, 1 };
const int dx[] = { 1, 0, -1, 0 };
bool visit[100][100] = { 0, };
int bfs(int sy, int sx, int m, int n, vector<vector<int>> picture) {
    int color = picture[sy][sx];
    int size = 1;
    queue<pair<int, int> > q;
    q.push(make_pair(sy, sx));
    visit[sy][sx] = 1;
    
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        for (int i=0; i<4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny<0 || nx<0 || ny>=m || nx>=n || visit[ny][nx] || picture[ny][nx] != color) continue;
            visit[ny][nx] = 1;
            q.push(make_pair(ny, nx));
            size++;
        }
    }
    return size;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    for (int y=0; y<m; y++) {
        for (int x=0; x<n; x++) {
            visit[y][x] = 0;
        }
    }
    int areaCount = 0;
    int maxAreaCount = 0;
    for (int y=0; y<m; y++) {
        for (int x=0; x<n; x++) {
            if (visit[y][x] || picture[y][x] == 0) continue;
            maxAreaCount = max(maxAreaCount, bfs(y, x, m, n, picture));
            areaCount++;
        }
    }
    vector<int> answer(2);
    answer[0] = areaCount;
    answer[1] = maxAreaCount;   
    return answer;
}

문제 출처

https://programmers.co.kr/learn/courses/30/lessons/49994

문제 풀이

문제가 엄청 직관적이라 금방 풀었다. 방향문자열을 1개씩 받아와 동,서,남,북 방향을 결정하고 위치를 이동하면 됩니다.

visit배열이 4차원배열인 이유는 방향성그래프가 아니기 때문입니다. 즉 (y, x) -> (ny, nx)로 이동했다면 (ny, nx) -> (y, x)의 길을 걸었기 때문에 이를 체크하기 위함입니다.

삼성 역량테스트 기출과 유형이 비슷한 문제

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EB%B0%A9%EB%AC%B8%20%EA%B8%B8%EC%9D%B4.java

class Solution {
    private static int dy[] = { 0, 1, 0, -1 };
    private static int dx[] = { 1, 0, -1, 0 };
    private static boolean visit[][][][] = new boolean[11][11][11][11];
    
    public int solution(String dirs) {
        int answer = 0;
        int y = 5;
        int x = 5;
        
        int dirIndex = 0;
        for (int i=0; i<dirs.length(); i++) {
            char dir = dirs.charAt(i);
            if (dir == 'U') {
                dirIndex = 3;
            } else if (dir == 'D') {
                dirIndex = 1;
            } else if (dir == 'R') {
                dirIndex = 0;
            } else if (dir == 'L') {
                dirIndex = 2;
            }
            
            int ny = y + dy[dirIndex];
            int nx = x + dx[dirIndex];
            
            // 지도를 벗어난 경우는 제외
            if (ny<0 || nx<0 || ny>=11 || nx>=11) continue;
            
            // (y,x) => (ny, nx)로 가는 길을 처음 걸을때
            if (!visit[y][x][ny][nx] == true && !visit[ny][nx][y][x] == true) {
                visit[y][x][ny][nx] = true;
                visit[ny][nx][y][x] = true;   
                answer++;            
            }
            
            // 현재 좌표 갱신
            y = ny;
            x = nx;
        }
        return answer;
    }
}