표 편집
문제 풀이 시간 : 1시간 14분
문제 요약
0 ~ n-1행으로 이루어진 표가 있고, 처음 선택된 행은k- 명령어 목록
cmd가 주어지며 한 번에 한 행만 선택됨, 표 범위를 벗어나는 이동은 주어지지 않음 - 지원 명령:
- 모든 명령 수행 후, 처음 표(0 ~ n-1) 기준으로 삭제되지 않은 행은
O, 삭제된 행은X로 표시한 문자열을 반환
문제 풀이
이 문제를 보고 처음 생각난 풀이 방법은 그냥 배열을 이용해서 푸는 방법이었다.
만약 n이 4라면 길이가 4인 정수 배열을 만들고 각 인덱스에 자기 자신을 넣어 두는 것이다.
그리고 삭제되면 해당 인덱스는 -1로 설정하여 삭제된 것을 표기하는 방식으로 풀려고 했다.
예를 들어, n=4라면
arr = [0, 1, 2, 3]과 같이 초기화 하고,
삭제된 행은 arr[i] = -1로 바꾸는 방식이다.
그래서 나온 방식이 아래 코드와 같다.
초기 코드
삭제 후 다음 선택된 행 찾기
public int last(int k){
//일단 삭제한 행 밑으로 이동함
for(int i=k+1;i<n;i++){
if(arr[i]!=-1)
return i;
}
//삭제한 행 밑에 남아있는 행이 없다면 위로 이동하며 처음으로 나오는 행 찾아서 반환
for(int i=k-1;i>=0;i--){
if(arr[i]!=-1)
return i;
}
return 0;
}위, 아래로 이동
public int move(int k, int num, int dir){
//dir이 -1인 경우 위로, 1인 경우 아래로 이동
for(int i=k+dir;i>=0 && i<n;i+=dir){
// 이미 삭제된 행이면 뛰어넘음
if(arr[i]==-1){
continue;
}
num--;
if(num==0)
return i;
}
return k;
}import java.util.*;
class Solution {
public int[] arr;
public int n;
public int last(int k){
for(int i=k+1;i<n;i++){
if(arr[i]!=-1)
return i;
}
for(int i=k-1;i>=0;i--){
if(arr[i]!=-1)
return i;
}
return 0;
}
public int move(int k, int num, int dir){
for(int i=k+dir;i>=0 && i<n;i+=dir){
if(arr[i]==-1){
continue;
}
num--;
if(num==0)
return i;
}
return k;
}
public String solution(int n, int k, String[] cmd) {
arr = new int[n];
this.n = n;
for(int i=0;i<n;i++)
arr[i] = i;
Deque<Integer> stack = new ArrayDeque<>();
for(int i=0;i<cmd.length;i++){
int num;
switch(cmd[i].charAt(0)){
//위로 이동
case 'U':
num = Integer.parseInt(cmd[i].substring(2).trim());
k = move(k, num, -1);
break;
//아래로 이동
case 'D':
num = Integer.parseInt(cmd[i].substring(2).trim());
k = move(k, num, 1);
break;
//삭제 후 다음 행으로 이동
case 'C':
arr[k] = -1;
stack.push(k);
k = last(k);
break;
//최근 삭제된 행 복구
case 'Z':
int redo = stack.pop();
arr[redo] = redo;
break;
}
}
StringBuilder sb = new StringBuilder();
for(int i=0;i<n;i++){
if(arr[i]!=-1)
sb.append("O");
else
sb.append("X");
}
return sb.toString();
}
}
/*
리스트로 0~n-1까지 넣어두기
idx 변수로 현재 선택된 행 번호 저장
특정 행 삭제하면 리스트에 -1로 표기, 스택에 쌓기
*/이 코드도 제대로 동작은 하고 정확성 테스트는 무사히 통과했지만, 효율성 테스트에서 시간초과가 나게된다.
왜냐하면 move()나 last()에서 매번 전체 배열을 선형 탐색하기 때문이다. 삭제된 행이 많아지면 이동할 때마다 거의 모든 행을 확인해야 하는 상황이 생긴다.
개선 방향
이 문제는 사실 이중 연결 리스트 형태로 풀어야 하는 문제였다.
각 행이 이전 행(prev)와 다음 행(next)에 대한 정보를 알고 있다면 삭제 및 복구 연산을 로 처리할 수 있기 때문이다.
이중 연결 리스트 초기화
for (int i = 0; i < n; i++) {
prev[i] = i - 1; // i행의 위쪽은 i-1
next[i] = (i == n - 1) ? -1 : i + 1; // i행의 아래쪽은 i+1 (마지막 행은 -1)
}삭제
stack.push(new Del(k, prev[k], next[k])); // 삭제 정보 저장
// 삭제된 행을 리스트에서 제거
if (prev[k] != -1) next[prev[k]] = next[k];
if (next[k] != -1) prev[next[k]] = prev[k];
// 다음 선택 행 결정 (아래가 있으면 아래, 없으면 위)
k = (next[k] != -1) ? next[k] : prev[k];
복구
Del redo = stack.pop();
// 복구된 행의 위/아래 행과 다시 연결
if (redo.prev != -1) next[redo.prev] = redo.num;
if (redo.next != -1) prev[redo.next] = redo.num;
// 복구된 행 자신의 연결 정보도 되살림
prev[redo.num] = redo.prev;
next[redo.num] = redo.next;
최종 코드
import java.util.*;
class Solution {
public class Del{
public int num;
public int prev;
public int next;
public Del(int num, int prev,int next){
this.num = num;
this.prev = prev;
this.next = next;
}
}
public String solution(int n, int k, String[] cmd) {
int[] prev = new int[n];
int[] next = new int[n];
Deque<Del> stack = new ArrayDeque<>();
for(int i=0;i<n;i++){
prev[i] = i-1;
next[i] = i == n-1 ? -1 : i+1;
}
for(String now : cmd){
char op = now.charAt(0);
if(op == 'U' || op == 'D'){
int move = Integer.parseInt(now.substring(2).trim());
if(op == 'U'){
for(;move>0;move--){
k = prev[k];
}
} else{
for(;move>0;move--){
k = next[k];
}
}
}
else if(op=='C'){
stack.push(new Del(k,prev[k], next[k]));
if(prev[k]!=-1)
next[prev[k]] = next[k];
if(next[k]!=-1)
prev[next[k]] = prev[k];
k = next[k]==-1 ? prev[k] : next[k];
}
else if(op=='Z'){
Del redo = stack.pop();
if(redo.prev!=-1)
next[redo.prev] = redo.num;
if(redo.next!=-1)
prev[redo.next] = redo.num;
prev[redo.num] = redo.prev;
next[redo.num] = redo.next;
}
}
char[] ans = new char[n];
Arrays.fill(ans, 'O');
for(Del now : stack){
ans[now.num] = 'X';
}
return new String(ans);
}
}함께 읽으면 좋은 글
택배상자
order 배열은 택배 기사님이 원하는 상자 적재 순서다 기존 컨테이너 벨트는 1번부터 순서대로만 꺼낼 수 있다 보조 벨트는 스택처럼 마지막에 넣은 것부터 꺼낼 수 있다 원하는 순서대로 최대한 실을 수 있는 상자 개수를 구하는 문제다 처음에는 기존 벨트를 실제 리스트로 만들어…
롤케이크 자르기
topping 배열은 롤케이크에 일렬로 올라간 토핑 번호다 한 지점을 잘라 두 조각으로 나눴을 때, 양쪽 토핑 종류 수가 같아야 공평하게 나눈 것이다 공평하게 자를 수 있는 방법의 수를 구하는 문제다 처음에는 자르는 위치마다 왼쪽과 오른쪽 배열을 나눠서 각각 서로 다른 토핑…
할인 행사
want, number 배열로 정현이가 원하는 제품과 수량을 표현한다 discount 배열은 XYZ 마트가 매일 할인하는 제품 목록이다 연속된 10일 동안 할인 제품 종류와 수량이 want, number와 정확히 일치해야 회원가입할 수 있다 그런 시작일이 총 몇 번 있는지…
숫자 변환하기
자연수 x를 y로 바꾸는 데 x+n, x2, x3 세 가지 연산을 쓸 수 있다 x를 y로 바꾸는 최소 연산 횟수를 구하는 문제다 만들 수 없으면 -1을 반환한다 처음에는 x에서 시작해서 세 가지 연산을 재귀적으로 다 시도해보고 y에 도달하는 경로 중 가장 짧은 걸 고르면…