[Codetree] 흰검 칠하기 (Hard)

[luke0408]

링크

흰검 칠하기

풀이

주의: 다른 참여자의 학습을 위해 풀이는 반드시 아래 토글 기능을 사용하여 가려주세요!

풀이 확인하기 (클릭)

1. 접근 방식 (논리적 흐름)

[문제 해석]

• 음수로도 무한한 인덱스를 가져야 한다.
  • Array는 사용 불가
• 각 타일은 4가지 상태 값을 가진다.
  • 0 - un, 1 - w, 2 - b, 3 - g
• 각 타일을 객체로 관리한다.
  • {w_count: number, b_count: number, state: number}
• 회색이 된 (state == 3) 타일은 더 이상 바뀌지 않는다.
• 각 타일은 고유한 위치를 가진다.
  • Key - Value 로 접근하자. => map 선택

[문제 계획]

• 타일의 색 변화를 추적하기 위해 좌표(정수 인덱스) 기반으로 관리한다.
• 각 타일에 대해 “흰색으로 칠한 횟수”, “검은색으로 칠한 횟수”, “최종 상태(흰/검/회색)”를 관리한다.
• 명령 x L/x R 처리 시 현재 위치 포함 x칸을 순회하며 칠한다.
• 타일마다 흰/검 칠 횟수를 갱신한 뒤, 두 색이 각각 2회 이상인 순간부터는 회색으로 고정한다.
• 명령 처리 후 현재 위치를 마지막 칠한 타일로 갱신한다.
• 모든 명령 종료 후 흰/검/회색 타일 개수를 출력한다.

2. 해결 코드 (또는 Pseudocode)

const fs = require("fs");
const input = fs.readFileSync(0).toString().trim().split('\n');

const n = Number(input[0]);
const commands = input.slice(1).map(line => line.split(' '));

// Please Write your code here.
const tiles = new Map(); // {key: position, value: {w, b, state}}
let pos = 0;

const getTile = (p) => {
    let t = tiles.get(p);

    if (!t) {
        t = { w: 0, b: 0, state: 0 };
        tiles.set(p, t);
    }

    return t;
}

for (let i = 0; i < n; i++) {
    const step = commands[i][1] === 'L' ? -1 : 1;

    for (let j = 0; j < commands[i][0]; j++) {
        const p = pos + step * j;
        const t = getTile(p);

        if (t.state !== 3) {
            if (commands[i][1] === 'L') t.w += 1;
            else t.b += 1;

            if (t.w >= 2 && t.b >= 2) {
                t.state = 3; // gray, fixed
            } else {
                t.state = commands[i][1] === 'L' ? 1 : 2;
            }
        }
    }

    pos = pos + step * (commands[i][0] - 1);
}

let w = 0, b = 0, g = 0;
for (const t of tiles.values()) {
    if (t.state === 1) w++;
    else if (t.state === 2) b++;
    else if (t.state === 3) g++;
}

console.log(`${w} ${b} ${g}`);

[yeongin-ji]

풀이 확인하기 (클릭)

1. 접근 방식 (논리적 흐름)

[풀이 계획]

• 방향이 왼, 오 둘다 가능해서 배열로는 까다롭겠다고 느낌 -> 양방향 리스트를 사용하자!
• 타일 구조체 만들어서 필요한 상태값들을 정의
  • 덧칠하는 경우 최근 색으로 표시되기 때문에 현재 색을 나타내는 상태값(curr)도 필요
• 순차적으로 명령 처리
  • dir에 따라서 방향과 색을 미리 지정
  • x만큼 반복
• 리스트 순회하며 최종 카운트
  • 우선 리스트 한쪽 끝으로 이동
  • 반대쪽 끝으로 이동하며 현재 색을 카운트 (단, 회색 조건을 충족하면 회색을 카운트)

[아쉬운 점]

• 소요시간: 120~150분
• 초기에 방향 체크하는 로직을 줄여보려고 미리 세팅하고 가자는 계획을 세웠는데, 구현하고 디버깅하는 과정에서 오히려 더 중복이 많아졌다.
• 따라서 아래 코드의 dst, cnt는 불필요해짐
• 양방향 리스트의 노드를 만들고 연결하는 부분이 디버깅하는데 상당한 시간을 소요함
• 내장 리스트 라이브러리(container/list) 사용했으면 어땠을까. 이런거 써도 되나?

2. 해결 코드 (또는 Pseudocode)

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	readString := func() string {
		scanner.Scan()
		return scanner.Text()
	}

	readInt := func() int {
		num, _ := strconv.Atoi(readString())
		return num
	}

	N := readInt()
	commands := make([]struct {
		x   int
		dir string
	}, N)
	for i := 0; i < N; i++ {
		commands[i].x = readInt()
		commands[i].dir = readString()
	}

	// Please write your code here.
	// B: Black
	// W: White
	// G: Gray
	const (
		B int = iota + 1
		W
		G
	)

	// (1)Tile 구조체 정의
	// - 양방향 Linked list 활용
	// - White, Black 색칠 횟수 카운트 포함
	// - curr: 현재 타일 색깔
	type Tile struct {
		wCnt, bCnt, curr int
		prev, next *Tile
	}

	cursor := &Tile{} // cursor: 현재 가리키고 있는 타일 위치
	for _, cmd := range commands {
		var dst *Tile // 가고자 하는 방향의 다음 칸 타일을 가리킴
		var color int // 어떤 색으로 칠할 것인지
		var cnt *int // 증가시킬 색의 cnt에 직접 접근하기 위함

		// (2)방향에 따라 dst, color, cnt를 세팅
		if cmd.dir == "L" { 
			dst = cursor.prev
			cnt = &cursor.wCnt
			color = W
		} else if cmd.dir == "R" {
			dst = cursor.next
			cnt = &cursor.bCnt
			color = B
		}

		// (3)x 만큼 이동하며 색칠 시작
		for i := range cmd.x {
			// 색칠하기: 방향에 따라 색칠 및 cnt++
			cursor.curr = color
			(*cnt)++

			// 타일 옮기기:
			// - 마지막 반복이라면 건너뛰기
			if i == cmd.x-1 {
				continue
			}
			// - 이미 노드가 있다면 이동하기
			if dst != nil {
				// cursor, dst, cnt는 함께 움직인다
				cursor = dst
				if cmd.dir == "L" {
					dst = cursor.prev
					cnt = &cursor.wCnt
				} else if cmd.dir == "R" {
					dst = cursor.next
					cnt = &cursor.bCnt
				}
			} else { // - 가고자 하는 방향이 nil이라면 새로운 노드 만들기
				tmp := &Tile{}
				if cmd.dir == "L" {
					// 노드 만들고 연결하기
					tmp.next = cursor
					cursor.prev = tmp
					cursor = cursor.prev

					// dst, cnt도 따라간다
					dst = cursor.prev
					cnt = &cursor.wCnt
				} else if cmd.dir == "R" {
					tmp.prev = cursor
					cursor.next = tmp
					cursor = cursor.next

					dst = cursor.next
					cnt = &cursor.bCnt
				}	
			}
		}
	}
	// (4)순회하며 개수 새기
	// - 왼쪽 끝으로 이동
	for cursor.prev != nil { 
		cursor = cursor.prev
	}
	// - 오른쪽 끝으로 이동하며 개수 새기
	var w, b, g int
	for cursor != nil {
		// count가 둘다 2 이상이면 현재 색과 상관없이 회색 카운트 증가
		if cursor.wCnt>=2 && cursor.bCnt>=2 {
			g++
		} else if cursor.curr == W {
			w++
		} else if cursor.curr == B {
			b++
		}
		cursor = cursor.next
	}

	// (5)출력하기
	fmt.Print(w, b, g)
}