[프로그래머스] 삼각 달팽이 - C++

문제

 

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

프로그래머스

 

• 소요 시간 : 44분                                                                                                 
• 난이도 : LV 2

 

접근 방법

 

직접 달팽이를 그렸다.

1. 하, 우, 좌상 방향을 반복한다.

2. 범위를 넘어가거나, 가고자 하는 방향에 이미 숫자가 채워져있으면 방향을 전환한다.

3. 가장 마지막 숫자를 판별하는 것은 하, 우, 좌상에 더 갈 수 있는 곳이 있는지 체크하여 모두 못가면 반복문을 종료한다.

나의 풀이

1차

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int map[1001][1001];

// 하, 우, 좌상
int dy[3] = {1, 0, -1};
int dx[3] = {0, 1, -1};

bool isEnd(int x, int y, int n) {
    int cnt = 0;
    
    for(int i=0; i<3; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if (ny < 0 || ny >= n || nx < 0 || nx >= n || map[ny][nx]) {
            cnt++;
        }
    }
    
    return cnt == 3;
}


vector<int> solution(int n) {
    vector<int> answer;
    
    int num = 1;
    int dir = 0;
    int x = 0, y = 0;
    
    while(true) {
            
        // 채우고 
        map[y][x] = num++;
    
        // 더 갈 수 있는 곳이 있는지 확인 후 없으면 끝내기
        if (isEnd(x, y, n)) break;
    
        // 이동 시켜보기 
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        
        // 닿았으면 방향 바꿈 
        if (ny < 0 || ny >= n || nx < 0 || nx >= n || map[ny][nx]) {
            dir = (dir+1) % 3;
        } 
        
        y = y + dy[dir];
        x = x + dx[dir];   
    }
    
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<=i; j++) {
            answer.push_back(map[i][j]);
        }
    }
    
    return answer;
}

 

결과 : 테스트 케이스 3번 실패

 

 

n = 3일때 

1

2 6

3 4 5 

 

대각선 변에서 끝나는 경우 우측이 무조건 비어있으므로 더 갈 수 있다고 판별하여 반복문이 종료되지 않았다.

반례)
입력값 => 3
기댓값 => [1, 2, 6, 3, 4, 5]
출력값 => [1, 2, 6, 3, 7, 5]

 

https://school.programmers.co.kr/questions/14175

프로그래머스

 

2차

대각선 변 && 우측이 빈 케이스를 추가로 처리해주었다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int map[1001][1001];

// 하, 우, 좌상
int dy[3] = {1, 0, -1};
int dx[3] = {0, 1, -1};

bool isEnd(int x, int y, int n) {
    int cnt = 0;
    
    for(int i=0; i<3; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if (ny < 0 || ny >= n || nx < 0 || nx >= n || map[ny][nx]) {
            cnt++;
        } else  if (i == 1 && y == x) { // 모서리 대각선 변에 걸친 경우 우측은 무조건 비어있으므로 이를 처리
            cnt++;
        }
    }
    
    return cnt == 3;
}


vector<int> solution(int n) {
    vector<int> answer;
    
    int num = 1;
    int dir = 0;
    int x = 0, y = 0;
    
    while(true) {        
        // 채우고 
        map[y][x] = num++;
    
        // 더 갈 수 있는 곳이 있는지 확인 후 없으면 끝내기
        if (isEnd(x, y, n)) break;
    
        // 이동 시켜보기 
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        
        // 닿았으면 방향 바꿈 
        if (ny < 0 || ny >= n || nx < 0 || nx >= n || map[ny][nx]) {
            dir = (dir+1) % 3;
        } 
        
        y = y + dy[dir];
        x = x + dx[dir];   
    }
    
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<=i; j++) {
            answer.push_back(map[i][j]);
        }
    }
    
    return answer;
}

 

결과 : 정답

정리

삼각형이라 처음에 조금 당황했지만 다른 달팽이 문제와 비슷하다고 생각된다. 

반례를 찾아보지 않고 직접 생각해보는 연습을 해야겠다.