2020 카카오 신입사원 코딩테스트 - 자물쇠와 열쇠

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

코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스

 

오늘은 2020 카카오 신입사원 코딩 테스트 3번째 문제입니다.

이 문제는 무려 정답률 7%를 자랑하는 문제입니다.

 

설계를 생각해내기 조금 힘들수도 있습니다. 그냥 머릿속으로 시뮬레이션을 돌려보면 

꽤나 간단한게 보이는데 실제 구현에 들어가면 난해합니다.

 

이 문제에서 배울 수 있는 것을 알아보겠습니다.

 

1. 지도를 90도 돌려서 기존 코드를 재사용할 수 있는 경우가 있음을 인지하자.

2. 지도를 90도 돌리는 방법을 확실히 알자. (이뿐만 아니라 점대칭, 선대칭 도 연습해보자)

3. 2차원 배열을 부분적으로 접근하는 방법에 대해서 생각해보자.

 

 

 

1. 지도를 90도 돌려서 기존 코드 재사용할 수 있는 경우

 

(추천 문제)

사탕게임 : https://www.acmicpc.net/problem/3085

경사로 : https://www.acmicpc.net/problem/14890

 

'경사로' 문제는 삼성 기출 문제로 유명하죠. 이외에도 제가 경험했던 코딩테스트에서도 맵을 90도 돌려서

기존 코드를 재사용할 수 있는 경우를 많이 만났습니다.

 

보통 수직과 수평에 대한 로직이 똑같을 경우, 이 방법이 매우 좋습니다.

기존 코드를 재사용함으로써 디버깅이 쉬워지고, 코딩량이 줄어들게 됩니다.

 

 

 

2. n x n 2차원 배열에 대한 조작 (90도 회전 / 점대칭 / 선대칭)

 

(추천 문제)

마술사 이민혁 : https://www.acmicpc.net/problem/3023

 

위 문제에서 선대칭, 점대칭에 대해서 공부하실 수 있습니다.

난이도는 쉽지만, 좋은 문제라고 생각합니다.

 

 

(i, j) : i 행, j 열 이라고 가정.

 

(1) 90도 조작 

(i, j) => (j, n - i - 1)

 

(2) x축 대칭

(i, j) => (n - i - 1, j)

 

(3) y축 대칭

(i, j) => (i, n - j - 1)

 

(4) 점대칭

(i, j)  => (n - i - 1, n - j - 1)

 

void turn(){
    int tmp_arr[20][20];             // 임시로 배열을 생성하여 이곳에 원본을 조작한 배열을 기록해 
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++){
            tmp_arr[n - i - 1][j] = arr[i][j];          // x축 대칭
            tmp_arr[i][n - j - 1] = arr[i][j];          // y축 대칭
            tmp_arr[n - i - 1][n - j - 1] = arr[i][j];  // 점대칭
            tmp_arr[j][n - i - 1] = arr[i][j];          // 90도 회전
        }
    
    // 원본 배열에 다시 복사하는 과정
       for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            arr[i][j] = tmp_arr[i][j];
}

 

 

 

3. 2차원 배열을 부분적으로 접근

이번에는 2차원 배열을 부분적으로 접근하는 방법에 대해서 알아보겠습니다.

 

위와 같이 스도쿠가 있을 때, 프로그래밍을 통해 문제를 풀기 위해서는 두꺼운 선으로 나눠져 있는

3x3 영역을 접근할 필요가 있습니다.

 

이것을 구현하기 위해서는 시작점을 잡아주는 for문과 3x3을 접근하는 이중 for문이 필요합니다.

코드로 보시죠.

 

for(int i = 0; i < n / 3; i++){
    for(int j = 0; j < n / 3; j++){
        int sy = i * 3, sx = j * 3;            // 3x3 정사각형 왼쪽 맨 위 지점 위치를 먼저 잡아준다
        for(int k = sy; k < sy + 3; k++){    // 시작 위치에서 오른쪽, 아래쪽으로 최대 +3만큼 제한을 둔다
            for(int l = sx; l < sx + 3; l++){
                cout << mp[k][l];
            }
            cout << endl;
        }
    }
}   

 

위 코드에서 n = 9 입니다.

 

 

 

 

 

 

 

 

 

 

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
int n, m;
 
void turn_90(vector<vector<int>> &arr){
    int ret[21][21] = {};
    for(int i = 0; i < m; i++)
        for(int j = 0; j < m; j++)
            ret[j][m - i - 1] = arr[i][j];
    for(int i = 0; i < m; i++)
        for(int j = 0; j < m; j++)
            arr[i][j] = ret[i][j];
}
 
bool solution(vector<vector<int>> k, vector<vector<int>> l) {
    m = k.size(), n = l.size();
    bool result = true;
    for(int dir = 0; dir < 4; dir++){
        for(int off_y = n - 1; off_y >= -n + 1; off_y--){
            for(int off_x = n - 1; off_x >= -n + 1; off_x--){
                result = true;
                for(int i = 0; i < n; i++){
                    for(int j = 0; j < n; j++){
                        int ny = i + off_y, nx = j + off_x;
                        if(ny < 0 || ny >= m || nx < 0 || nx >= m) {
                            if(l[i][j] == 0) result = false;
                        }
                        else {
                            if((l[i][j] == 0 && k[ny][nx] == 0) || (l[i][j] == 1 && k[ny][nx] == 1)) result = false;
                        }
                    }
                }
                if(result) return true;
            }
        }
        turn_90(k);
    }
    return false;
}