# 문제
https://school.programmers.co.kr/learn/courses/30/lessons/68645
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
정수 n이 매개변수로 주어집니다.
다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.
# 풀이 (자바)
import java.util.Arrays;
class Solution {
public int[] solution(int n) {
int[][] triangle = new int[n][n];
int x = 0; // x 좌표
int y = 0; // y 좌표
int num = 1; // 셀 안에 들어갈 수
int k = 0; // answer 의 인덱스를 저장할 수
int count = n - 1; // 방향이 바뀔 때 마다 달팽이가 움직여야하는 칸 수
int sellNum = 0; // 전체 셀의 개수
// 전체 셀의 개수 계산
for (int i = 1; i < n + 1; i++) {sellNum += i;}
int[] answer = new int[sellNum];
while(true) {
if (count == 0) {count = 1;} // n = 4 의 10 처럼, count가 0이 되는 상황에도 한 번은 달팽이가 움직여야하기 때문에 1로 선언해준다.
for (int i = 0; i < count; i++) {
if(sellNum == 0) { break; }
triangle[x][y] = num;
x++;
num++;
sellNum--;
}
for (int i = 0; i < count; i++) {
if(sellNum == 0) { break; }
triangle[x][y] = num;
y++;
num++;
sellNum--;
}
for (int i = 0; i < count; i++) {
if(sellNum == 0) { break; }
triangle[x][y] = num;
x--;
y--;
num++;
sellNum--;
}
x = x + 2;
y = y + 1;
count -= 3; // 한 바퀴 돌 때 마다, 채우는 칸의 개수가 3개씩 줄음
}
// triangle 2차원 배열을 1차원 배열인 answer 로 옮기기
while (k < answer.length) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < i + 1; j++) {
answer[k] = triangle[i][j];
k++;
}
}
}
return answer;
}
}
#느낀점
알고리즘 짜는 게 참 알듯말듯 했다. 내가 풀이한 방법은
1. 전체 셀의 개수를 계산한 뒤,
2. 각 방향마다 count 개수에 맞게 셀을 채우고
3. 한 바퀴를 돌아올 때 count 수를 조정해서 계속 채워나가는 방식으로 생각했다.
n = 5 일 경우, 시작점인 [0][0]을 기준으로 count 의 수는 4이다.
↓ | ||||
↓ | ↖ | |||
↓ | ↖ | |||
↓ | ↖ | |||
→ | → | → | → | ↖ |
먼저 첫번째 테두리는 이렇게 4칸씩 이동하게 된다.
한 바퀴를 돌았으니 count - 3 을 통해 count 는 1이 되게 된다.
여기서 주의할 점은 보라색 방향이 4칸을 이동했을 때, for 문 안의 x--; y--;로 인해 최종 도착지는 [0][0] 이 된다.
안쪽의 비어있는 셀을 채우기 위한 달팽이의 시작점은 [2][1]이 되어야 하기때문에 x 에는 +2 를, y에는 +1 을 해준다.
이것은 달팽이 한 바퀴가 다 도는 모든 경우에 해당되므로 while 문이 끝나기 전 for 문 밖에서 입력해주었다.
↓ | ||||
↓ | ↖ | |||
↓ | ↓ | ↖ | ||
↓ | → | ↖ | ↖ | |
→ | → | → | → | ↖ |
두번째 바퀴의 count 는 1이므로, 안쪽은 이렇게 1칸씩 채워진다.
또 하나 생각해야 하는 점은, n = 4 의 경우와 같이 count 가 3일 경우 , 그 다음 count 0 이 되게 되는데,
이렇게 되면 채우지 못한 한 개의 셀이 정 중앙에 남게된다 (아래 표 참고).
↓ | |||
↓ | ↖ | ||
↓ | 이곳! | ↖ | |
→ | → | → | ↖ |
따라서, count 가 0일 때, 1로 변경해주는 조건 : if (count == 0) {count = 1;} 을 추가해주었다.
테스트를 통과하고 다른 사람들의 풀이를 보는데...
if (i % 3 == 0) {
++x;
} else if (i % 3 == 1) {
++y;
} else if (i % 3 == 2) {
--x;
--y;
}
matrix[x][y] = num++;
이렇게 3으로 나눠서 딱 나누어 떨어질 때, 나머지가 1일 때, 2일 때로 푼 사람이 있더라!!! 홀리몰리...
이 알고리즘이 나는 제일 깔끔한 것 같았다. 불필요한 포문과 반복들을 지워주는 게 정말 깔끔하더라.
다음에는 이런 코드를 짤 수 있도록 더 생각하면 좋겠다!
'𝑪𝒐𝒅𝒊𝒏𝒈 𝑻𝒆𝒔𝒕' 카테고리의 다른 글
[Codility] Binary Gap (0) | 2022.10.24 |
---|---|
[프로그래머스] 쿼드압축 후 개수 세기 (0) | 2022.10.22 |
[프로그래머스] 두 개 뽑아서 더하기 (0) | 2022.10.19 |
[프로그래머스] 3진법 뒤집기 (0) | 2022.10.16 |
[프로그래머스] 약수의 합 (0) | 2022.10.13 |