🐌🐌🐌🐌후기: 달팽이 문제 아니랄까봐 풀이가 달팽이마냥 느렸음. 이것도 수학문제 느낌 낭낭^^....
문제 설명
정수 n이 매개변수로 주어집니다.
다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.
제한사항
- n은 1 이상 1,000 이하입니다.
입출력 예
n | result |
4 | [1,2,9,3,10,8,4,5,6,7] |
5 | [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] |
6 | [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] |
내 풀이>> 와,, 그림으로 이해하니까 훨씬 쉬웠다. 알고리즘 생각해내고 코딩다하는데 3시간 걸린건 안비밀^_^
근데 풀이에 올리려고 마우스로 그림그리는건 제일 어려웠음ㅋㅋㅋㅋ
1. 그냥 직관적으로 생각하면 n행의 삼각형 위에서 화살표 진행 방향이 세군데임. "아래↙" "오른쪽→" "위↖"
또한 n행인 삼각형은 총 n번의 화살표를 긋는다!!!
그런데 프로그래밍은 '0'번이 시작 순서이기 때문에 0~n-1번의 화살표가 생김.
☞ for i in range(n):
2. 또한 i번째 화살표에 들어가는 숫자의 갯수를 j라고 하면, j = n-i개 이다. 처음에 이중 for문으로 작성하자
☞ for j in range(i, n):
3. 화살표는 아래방향을 첫번째 시작으로 오른쪽, 위쪽이 반복됨 & 패턴은 3이 주기
그러므로 i % 3 == 0이면 아래, 1이면 오른쪽, 2이면 위쪽
☞ if i % 3 == 0 : ↙조건
elif i % 3 == 1: →조건
elif i % 3 == 2: ↖조건
4. 행렬에서 좌표로 움직여야하므로, 좌표를 (row, col)이 움직이는 규칙은
↙조건: row +1
→조건: col +1
↖조건: row -1, col -1
(((단, 화살표 시작하고 움직인 첫칸이 (0,0)으로 시작해야해서 초기값을 row = -1, col = 0 으로 시작한다.)))
5. 이렇게 진행되는 좌표마다 N=1, N+=1인 정수를 넣어줍시다.
6. 만들어진 2차원 행렬을 1차원 list로 풀어냅시다 (chain함수 사용)
from itertools import chain
def solution(n):
triangle= [[0]* i for i in range(1, n+1)] #총n행을 가지고, n번째 행에는 n칸인 삼각형 틀 정의하기.
row = -1
col = 0 #초기 좌표값 설정
N = 1 #빈칸에 들어갈 숫자 초기 N정의해주기
for i in range(n): #n행인 삼각형에서 화살표의 순서 i를 인덱싱, 화살표는 0번부터 n-1번
for j in range(i,n): #한 화살표에 들어가는 숫자갯수 (n-i)개를 인덱싱
if i % 3 == 0: #화살표 순서가 0,3,6... 이면 아래로가는 화살표
row += 1
elif i % 3 == 1: #화살표 순서가 1,4,7... 이면 오른쪽으로 가는 화살표
col += 1
elif i % 3 == 2: #화살표 순서가 2,5,8... 이면 위로가는 화살표
row -=1
col -=1
triangle[row][col] = N #위 조건에 맞는 칸에 N을 저장해 줌.
N += 1
return list(chain(*triangle)) #결과값 2차원행렬을 1차 배열list로 반환.
끗....
오래걸렸다....
힘들다.........
얘를 java로 변형해 보고 싶은데.. 그건 내일 해서 추가해야 겠다.
Java풀이>>
다른 것들을 java식으로 코딩하는것은 일찍 했는데
2차원 배열을 1차원 배열(list)로 반환하는 방법을 찾는데 힘들어서,, 다른 분의 정답을 참고함.
파이썬에는 chain함수로 list로 풀어낼 수 있었으나, java에서는
일단 return해줄 결과값 answer을 1차원 배열(list)으로 선언해 준다.
이때 list의 길이는 n행 삼각형의 총 숫자 갯수, 즉 n*(n+1))/2으로 선언해 준다.
(예) 4행 삼각형이면 총 숫자 갯수 = 1+2+3+4 = 4(4+1)/2
class Solution {
public int[] solution(int n) {
int[] answer = new int[(n*(n+1))/2]; //return해줄 1차원 배열 list선언
int[][] triangle = new int[n][n]; //n행삼각형(사실 이거는 사각형)의 틀인 2차배열 선언하기
/*
우리가 선언한 2차원 배열중에 사용될 부분을 그려보면 다음과 같음.
[/]부분이 사용되는 부분, [0]부분이 사용 안되는 부분
ex. n=5일때
[/][0][0][0][0]
[/][/][0][0][0]
[/][/][/][0][0]
[/][/][/][/][0]
[/][/][/][/][/]
*/
int N = 1; //배열에 들어갈 숫자 시작점
int row = -1; //배열의 첫 행 시작점
int col = 0; //배열의 첫 열 시작점
for (int i = 0; i < n; i++) { //화살표의 순서뽑기.
for (int j = i; j < n; j++) { //화살표안의 숫자 갯수 뽑기
if (i % 3 == 0) {
row++;
} else if (i % 3 == 1) {
col++;
} else if (i % 3 == 2) {
row--;
col--;
}
triangle[row][col] = N++;
}
}
//출력과정
int k = 0; //1차원 배열(list)에 들어갈 배열 넘버
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(triangle[i][j] == 0) break;
//2차원 배열이고 우리는 삼각형 모양만 썼고, 위 설명처럼 안쓰인 반쪽이 있다.
//그래서 그런 부분을 만나면 break해서 1차원 배열에 저장 안되게 한다.
answer[k++] = triangle[i][j];
}
}
return answer;
}
}
찐으로 끝!!!!!!!!
'매일매일 코딩연습! > 프로그래머스' 카테고리의 다른 글
[코딩연습 13일차] 프로그래머스 : 프린터 / python & java (0) | 2021.02.16 |
---|---|
[코딩연습 12일차] 프로그래머스 : 신규아이디 / python (0) | 2021.02.16 |
[코딩연습10일차] 프로그래머스 : 다리를 지나는 트럭 / python (0) | 2021.02.10 |
[코딩연습 9일차] 프로그래머스 : 모든 레코드 조회하기 / MySQL / Select연습 (0) | 2021.02.06 |
[코딩연습9일차] 프로그래머스 : 멀쩡한 사각형 / python (0) | 2021.02.06 |