[프로그래머스(Programmers)][자바(java)] (Lv3) 표 편집 <2021 카카오 채용연계형 인턴십>

 

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

 

문제 풀이

 

import java.util.*;

public class Solution {

	class Node {
		int p, c, n; // value_pre/cur/next
		public Node(int p, int c, int n) {
			this.p = p;
			this.c = c;
			this.n = n;
		}
	}

	public String solution(int n, int k, String[] cmd) {
		int i, h = 0, t = n - 1; // h/t : row num_head/tail
		List<Node> ls = new ArrayList<>();
		for (i = 0; i < n; ++i)
			ls.add(new Node(i == 0 ? t : i - 1, i, i == n - 1 ? h : i + 1));
		StringTokenizer s; char c; // c : command
		int m = cmd.length, d, v, vp, vn; Node nd; // d : distance, v : value_cur, vp/vn : value_pre/next, nd : node_cur
		Stack<Integer> st = new Stack<>();
		for (i = 0; i < m; ++i) {
			s = new StringTokenizer(cmd[i]);
			c = s.nextToken().charAt(0);
			if (c == 'D') {
				d = Integer.parseInt(s.nextToken());
				while (d-- > 0)
					k = ls.get(k).n;
			}
			if (c == 'U') {
				d = Integer.parseInt(s.nextToken());
				while (d-- > 0)
					k = ls.get(k).p;
			}
			if (c == 'C') {
				st.push(k);
				nd = ls.get(k); vp = nd.p; vn = nd.n;
				ls.get(vp).n = vn;
				ls.get(vn).p = vp;
				if (k == t) {
					k = ls.get(k).p;
					t = k;
					continue;
				}
				if (k == h) {
					k = ls.get(k).n;
					h = k;
					continue;
				}
				k = ls.get(k).n;
			}
			if (c == 'Z') {
				v = st.pop();
				nd = ls.get(v); vp = nd.p; vn = nd.n;
				ls.get(vp).n = v;
				ls.get(vn).p = v;
				if (t < v) t = v;
				if (h > v) h = v;
			}
		}
		StringBuilder sb = new StringBuilder();
		nd = ls.get(h);
		k = nd.c;
		for (i = 0; i < n; ++i) {
			if (i == k) {
				sb.append('O');
				k = nd.n;
				nd = ls.get(k);
			} else
				sb.append('X');
		}
		return sb.toString();
	}
}

 

-   LinkedList 처럼 한 노드에 이전, 다음의 노드 값을 담을 수 있도록 Node Class 생성

-   ArrayList<Node> ls 생성( 탐색을 빠르게 하기 위함 ) 후 각 행의 값을 차례로 넣음
  ( 단, 첫 번째 행( h : head )의 이전 값( p )은 마지막 행( t : tail )의 값, 마지막 행의 다음 값( n )은 첫 번째 행의 값을 넣어 원형으로 연결되도록 함 )

-   전달받은 cmd[]에서 명령어( c : command )를 뽑아옴

• D   =>   이동해야 하는 행의 수( d : distance )만큼 k( 커서 ) 값을 현재 노드( nd = ls.get(k) )의 다음 값( nd.n )으로 변경
• U   =>   이동해야 하는 행의 수( d )만큼 k 값을 현재 노드( nd )의 이전 값( nd.p )으로 변경
• C   =>   현재 커서 값( k )을 스택( Stack<Integer> st )에 저장하고,
                이전 노드( ls.get(nd.p) )의 다음값( n )에 현재 노드( nd = ls.get(k) )의 다음값( vn = nd.n )을 넣고,
                다음 노드( ls.get(nd.n) )의 이전값( p )에 현재 노드의 이전값( vp = nd.p )을 넣는다.
              ( 단, k가 가장 마지막 행에 위치할 경우 이전 행으로 이동하고 마지막 행 값( t ) 변경.
                나머지 경우 다음 행으로 이동. k가 첫번째 행에 위치하면 첫번째 행 값( h ) 변경. )
• Z   =>   스택에서 제일 마지막에 제거한 노드의 값( v = st.pop() )을 pop 하고,
                그 노드( nd = ls.get(v) )의 이전 노드의 다음값과 다음 노드의 이전값에 그 노드의 값을 넣는다

 

 

---

오답

import java.util.*;

public class Solution {

	class Row {
		int idx, val;
		public Row(int idx, int val) {
			this.idx = idx;
			this.val = val;
		}
	}

	public String solution(int n, int k, String[] cmd) {
		int m = cmd.length, idx, val, i; char c; Row row;
		List<Integer> ls = new LinkedList<>();
		for (i = 0; i < n; ++i)
			ls.add(i);
		StringTokenizer s;
		Stack<Row> st = new Stack<>();
		boolean r[] = new boolean[n]; // is removed?
		for (i = 0; i < m; ++i) {
			s = new StringTokenizer(cmd[i]);
			c = s.nextToken().charAt(0);
			if (c == 'D') {
				k += Integer.parseInt(s.nextToken());
				if (k >= n)		k -= n;
			}
			if (c == 'U') {
				k -= Integer.parseInt(s.nextToken());
				if (k < 0)		k += n;
			}
			if (c == 'C') {
				n--;
				val = ls.remove(k);
				st.push(new Row(k, val));
				r[val] = true;
				if (k == n)		k--;
			}
			if (c == 'Z') {
				n++;
				row = st.pop(); idx = row.idx; val = row.val;
				ls.add(idx, val);
				r[val] = false;
				if (k >= idx)	k++;
			}
		}
		StringBuilder sb = new StringBuilder();
		for (i = 0; i < n; ++i)
			sb.append(r[i] ? 'X' : 'O');
		return sb.toString();
	}
}

 

import java.util.*;

public class Solution {

	public static String solution(int n, int k, String[] cmd) {
		int m = cmd.length, d, v, l = n - 1, i; // distance, value, last row num
		StringTokenizer s; char c; // command
		Stack<Integer> st = new Stack<>();
		boolean r[] = new boolean[n]; // is removed?
		for (i = 0; i < m; ++i) {
			s = new StringTokenizer(cmd[i]);
			c = s.nextToken().charAt(0);
			if (c == 'D') {
				d = Integer.parseInt(s.nextToken());
				while (d > 0) {
					do {
						k++;
						if (k >= n) k -= n;
					} while (r[k]);
					d--;
				}
			}
			if (c == 'U') {
				d = Integer.parseInt(s.nextToken());
				while (d > 0) {
					do {
						k--;
						if (k < 0) k += n;
					} while (r[k]);
					d--;
				}
			}
			if (c == 'C') {
				st.push(k);
				r[k] = true;
				if (k == l) {
					while (r[k]) {
						k--;
						if (k < 0) k += n;
					}
					l = k;
				} else {
					while (r[k]) {
						k++;
						if (k >= n) k -= n;
					}
				}
			}
			if (c == 'Z') {
				v = st.pop();
				r[v] = false;
				if (l < v) l = v;
			}
		}
		StringBuilder sb = new StringBuilder();
		for (i = 0; i < n; ++i)
			sb.append(r[i] ? 'X' : 'O');
		return sb.toString();
	}
}

효율성 non-pass