문제 설명
NxN 격자 위에서 로봇 팔이 이동하며 선을 그린다.
초기 위치는 왼쪽 위 (0,0)이다.
이동 명령은 다음과 같다.
U : 위
D : 아래
L : 왼쪽
R : 오른쪽조건
- 격자 밖으로 나가는 명령은 무시
- 이동한 경로를 표시
출력 규칙
각 칸은 다음 기준으로 출력한다.
| 상태 | 출력 | |
|---|---|---|
| 지나지 않음 | . | |
| 수직만 지나감 | ` | ` |
| 수평만 지나감 | - | |
| 둘 다 지나감 | + |
입력 예시
5
DRDRRUU출력 예시
|..|.
++.|.
.+-+.
.....
.....문제 해결 아이디어
이 문제의 핵심은 다음이다.
한 칸이 아니라
"선(이동 경로)"을 표시하는 문제즉,
이 칸을 지나갔는가?가 아니라
이 칸에서
수평/수직 이동이 있었는가?를 따로 관리해야 한다.
내가 작성한 풀이
나는 한 배열(map)에 직접 문자(|, -, +)를 넣는 방식으로 구현했다.
하지만 이 방식에는 문제가 있다.
문제점 1 — 상태 관리가 복잡함
if(tmp == 'U' || tmp == 'D' && ...)이런 조건이 계속 등장하면서
현재 방향
이전 방향
기존 값을 모두 고려해야 한다.
→ 코드가 매우 복잡해짐
문제점 2 — 이전 상태에 의존
tmp = 'D';이렇게 이전 방향을 기억해서 처리하는 방식은
경로 문제에서 매우 취약한 방식이다.
문제점 3 — 한 배열로 처리하려고 함
현재 코드 구조
map[][] 하나로
모든 상태 처리하지만 실제로 필요한 정보는 2가지다.
수평 이동
수직 이동강의 풀이
강의에서는 이 문제를 훨씬 깔끔하게 해결했다.
핵심 아이디어는 다음이다.
수평 이동 배열
수직 이동 배열을 따로 만든다.
핵심 구조
boolean[][] passVertical
boolean[][] passHorizontal이동 처리
예: 아래로 이동
passVertical[curR][curC] = true;
passVertical[curR + 1][curC] = true;즉
선은 두 칸에 영향을 준다코드
import java.util.Scanner;
class Main
{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String command = sc.hasNext() ? sc.next() : "";
boolean[][] passVertical = new boolean[N][N];
boolean[][] passHorizontal = new boolean[N][N];
int curR = 0, curC = 0;
for (int i = 0; i < command.length(); i++) {
char cmd = command.charAt(i);
if (cmd == 'D') {
if (curR == N - 1) continue;
passVertical[curR][curC] = true;
passVertical[curR + 1][curC] = true;
curR++;
}
else if (cmd == 'U') {
if (curR == 0) continue;
passVertical[curR][curC] = true;
passVertical[curR - 1][curC] = true;
curR--;
}
else if (cmd == 'L') {
if (curC == 0) continue;
passHorizontal[curR][curC] = true;
passHorizontal[curR][curC - 1] = true;
curC--;
}
else {
if (curC == N - 1) continue;
passHorizontal[curR][curC] = true;
passHorizontal[curR][curC + 1] = true;
curC++;
}
}
for (int i = 0; i < N; i++) {
String ans = "";
for (int j = 0; j < N; j++) {
if (passHorizontal[i][j] && passVertical[i][j]) ans += "+";
else if (passVertical[i][j]) ans += "|";
else if (passHorizontal[i][j]) ans += "-";
else ans += ".";
}
System.out.println(ans);
}
}
}두 풀이 방식 비교
| 방식 | 특징 |
|---|---|
| 내 풀이 | 한 배열로 상태 처리 |
| 강의 풀이 | 수평/수직 분리 |
핵심 차이
내 코드
상태를 한 번에 처리하려고 함강의 코드
상태를 나눠서 처리핵심 개념
1. 선은 두 칸을 연결한다
이동 = 점이 아니라 선2. 상태 분리
수평 / 수직을 따로 관리이게 가장 중요하다.
3. 마지막에 합치기
| + - → +시간 복잡도
명령 길이 최대
250격자 크기 최대
10 × 10전체 시간 복잡도
O(N² + 명령수)→ 매우 빠름
정리
이 문제는 처음에는 조건이 복잡해 보이지만,
핵심은 다음 한 줄이다.
수평과 수직을 나눠서 생각하자내 코드는 한 배열에서 모든 상태를 처리하려다 보니
조건이 많아지고 오류 가능성이 높아졌다.
강의 코드처럼
수평 / 수직을 분리 → 마지막에 합치기방식이 훨씬 깔끔하고 안정적인 해결 방법이다.
아는거 없는 전공자