월간 코드 챌린지 시즌3: 빛의 경로 사이클

코딩 테스트/Level 2 2021. 9. 15. 13:05

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

코딩테스트 연습 - 빛의 경로 사이클

각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진

programmers.co.kr

파이썬

생각의 흐름에 따라....

def solution(grid):
    answer = []
    path = set()
    for direction in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                cycle_length = 0
                point = (i, j)
                while True:
                    prev_point = point
                    point = (point[0] + direction[0], point[1] + direction[1])
                    new_path = (prev_point, point)
                    if new_path in path:
                        break
                    else:
                        cycle_length += 1
                        path.add(new_path)
                    if point[0] >= len(grid):
                        point = (0, point[1])
                    elif point[1] >= len(grid[0]):
                        point = (point[0], 0)
                    elif point[0] < 0:
                        point = (len(grid) - 1, point[1])
                    elif point[1] < 0:
                        point = (point[0], len(grid[0]) - 1)
                    direction_s = grid[point[0]][point[1]]
                    if direction_s == 'R':
                        if direction == (1, 0):
                            direction = (0, -1)
                        elif direction == (0, 1):
                            direction = (1, 0)
                        elif direction == (-1, 0):
                            direction = (0, 1)
                        elif direction == (0, -1):
                            direction = (-1, 0)
                    elif direction_s == 'L':
                        if direction == (1, 0):
                            direction = (0, 1)
                        elif direction == (0, 1):
                            direction = (-1, 0)
                        elif direction == (-1, 0):
                            direction = (0, -1)
                        elif direction == (0, -1):
                            direction = (1, 0)
                if cycle_length:
                    answer.append(cycle_length)
    return sorted(answer)

테스트 1 〉	통과 (0.34ms, 10.3MB)
테스트 2 〉	통과 (0.67ms, 10.3MB)
테스트 3 〉	통과 (0.74ms, 10.4MB)
테스트 4 〉	통과 (40.92ms, 16.2MB)
테스트 5 〉	통과 (84.63ms, 19.4MB)
테스트 6 〉	통과 (85.22ms, 20.8MB)
테스트 7 〉	통과 (2142.46ms, 175MB)
테스트 8 〉	통과 (1601.11ms, 158MB)
테스트 9 〉	통과 (2057.91ms, 176MB)
테스트 10 〉	통과 (2294.88ms, 210MB)
테스트 11 〉	통과 (2687.63ms, 222MB)

조금 줄여본다면...

def solution(grid):
    answer = []
    path = set()
    m, n = len(grid), len(grid[0])
    left = {(1, 0): (0, 1), (0, 1): (-1, 0), (-1, 0): (0, -1), (0, -1): (1, 0)}
    right = {(1, 0): (0, -1), (0, 1): (1, 0), (-1, 0): (0, 1), (0, -1): (-1, 0)}
    for direction in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        for y in range(m):
            for x in range(n):
                cycle_length = 0
                point = (y, x)
                while True:
                    prev_point = point
                    point = (point[0] + direction[0], point[1] + direction[1])
                    new_path = (prev_point, point)
                    if new_path in path:
                        break
                    cycle_length += 1
                    path.add(new_path)
                    if point[0] >= m:
                        point = (0, point[1])
                    elif point[1] >= n:
                        point = (point[0], 0)
                    elif point[0] < 0:
                        point = (m - 1, point[1])
                    elif point[1] < 0:
                        point = (point[0], n - 1)
                    direction_s = grid[point[0]][point[1]]
                    if direction_s == 'R':
                        direction = right[direction]
                    elif direction_s == 'L':
                        direction = left[direction]
                if cycle_length:
                    answer.append(cycle_length)
    return sorted(answer)

테스트 1 〉	통과 (0.29ms, 10.4MB)
테스트 2 〉	통과 (0.60ms, 10.3MB)
테스트 3 〉	통과 (0.61ms, 10.2MB)
테스트 4 〉	통과 (40.30ms, 16MB)
테스트 5 〉	통과 (79.90ms, 19.5MB)
테스트 6 〉	통과 (84.39ms, 20.7MB)
테스트 7 〉	통과 (1866.67ms, 175MB)
테스트 8 〉	통과 (1476.43ms, 158MB)
테스트 9 〉	통과 (1703.87ms, 176MB)
테스트 10 〉	통과 (2198.31ms, 210MB)
테스트 11 〉	통과 (2316.87ms, 222MB)

더 줄인다면...
하지만 느려져서...

def solution(grid):
    answer = []
    path = set()
    m, n = len(grid), len(grid[0])
    left = {(1, 0): (0, 1), (0, 1): (-1, 0), (-1, 0): (0, -1), (0, -1): (1, 0)}
    right = {(1, 0): (0, -1), (0, 1): (1, 0), (-1, 0): (0, 1), (0, -1): (-1, 0)}
    for direction in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        for y in range(m):
            for x in range(n):
                cycle_length = 0
                point = (y, x)
                while True:
                    prev_point = point
                    point = (point[0] + direction[0], point[1] + direction[1])
                    new_path = (prev_point, point)
                    if new_path in path:
                        break
                    cycle_length += 1
                    path.add(new_path)
                    point = (point[0] % m, point[1] % n)
                    direction_s = grid[point[0]][point[1]]
                    if direction_s == 'R':
                        direction = right[direction]
                    elif direction_s == 'L':
                        direction = left[direction]
                if cycle_length:
                    answer.append(cycle_length)
    return sorted(answer)

테스트 1 〉	통과 (0.28ms, 10.2MB)
테스트 2 〉	통과 (0.63ms, 10.3MB)
테스트 3 〉	통과 (0.62ms, 10.2MB)
테스트 4 〉	통과 (38.34ms, 18.1MB)
테스트 5 〉	통과 (77.17ms, 23.2MB)
테스트 6 〉	통과 (91.41ms, 24.8MB)
테스트 7 〉	통과 (2372.46ms, 252MB)
테스트 8 〉	통과 (1798.00ms, 225MB)
테스트 9 〉	통과 (1837.88ms, 226MB)
테스트 10 〉	통과 (2528.47ms, 274MB)
테스트 11 〉	통과 (2745.59ms, 290MB)

golang

티스토리의 코드 블럭 기능에서 탭은 8칸 ㅠ,.ㅠ

import "sort"

type v struct { //vortex
	y, x int
}

type p struct { //path
	from, to v
}

func solution(grid []string) (answer []int) {
	paths := map[p]bool{}
	for _, direction := range []v{v{1, 0}, v{-1, 0}, v{0, 1}, v{0, -1}} {
		for y := range grid {
			for x := range grid[0] {
				cycle_length := 0
				new_point := v{y, x}
				for true {
					prev_point := new_point
					new_point = v{prev_point.y + direction.y, prev_point.x + direction.x}
					new_path := p{prev_point, new_point}
					if _, ok := paths[new_path]; ok {
						break
					}
					cycle_length++
					paths[new_path] = true
					switch {
					case new_point.x >= len(grid[0]):
						new_point.x = 0
					case new_point.y >= len(grid):
						new_point.y = 0
					case new_point.x < 0:
						new_point.x = len(grid[0]) - 1
					case new_point.y < 0:
						new_point.y = len(grid) - 1
					}
					direction_s := grid[new_point.y][new_point.x]
					if direction_s == 'R' {
						switch direction {
						case v{1, 0}:
							direction = v{0, -1}
						case v{0, 1}:
							direction = v{1, 0}
						case v{-1, 0}:
							direction = v{0, 1}
						case v{0, -1}:
							direction = v{-1, 0}
						}
					} else if direction_s == 'L' {
						switch direction {
						case v{1, 0}:
							direction = v{0, 1}
						case v{0, 1}:
							direction = v{-1, 0}
						case v{-1, 0}:
							direction = v{0, -1}
						case v{0, -1}:
							direction = v{1, 0}
						}
					}
				}
				if cycle_length > 0 {
					answer = append(answer, cycle_length)
				}
			}
		}
	}
	sort.Sort(sort.IntSlice(answer))
	return
}

테스트 1 〉	통과 (0.12ms, 4.29MB)
테스트 2 〉	통과 (0.23ms, 4.29MB)
테스트 3 〉	통과 (0.23ms, 3.6MB)
테스트 4 〉	통과 (11.86ms, 8.27MB)
테스트 5 〉	통과 (23.83ms, 12.1MB)
테스트 6 〉	통과 (24.49ms, 12.1MB)
테스트 7 〉	통과 (563.42ms, 133MB)
테스트 8 〉	통과 (317.01ms, 77.6MB)
테스트 9 〉	통과 (381.91ms, 84.8MB)
테스트 10 〉	통과 (663.26ms, 156MB)
테스트 11 〉	통과 (537.09ms, 159MB)

구조체를 쓰지 않으면 어떻게 될까?
더 느려짐...

import (
	"fmt"
	"sort"
)

func solution(grid []string) (answer []int) {
	paths := map[string]bool{}
	directions := [][]int{[]int{1, 0}, []int{-1, 0}, []int{0, 1}, []int{0, -1}}
	for d := range directions {
		for y := range grid {
			for x := range grid[0] {
				cycle_length := 0
				new_point := []int{y, x}
				for true {
					prev_point := new_point
					new_point = []int{prev_point[0] + directions[d][0], prev_point[1] + directions[d][1]}
					new_path := fmt.Sprintf("%d-%d-%d", prev_point[0], prev_point[1], d)
					if _, ok := paths[new_path]; ok {
						break
					}
					cycle_length++
					paths[new_path] = true
					switch {
					case new_point[0] >= len(grid):
						new_point[0] = 0
					case new_point[1] >= len(grid[0]):
						new_point[1] = 0
					case new_point[0] < 0:
						new_point[0] = len(grid) - 1
					case new_point[1] < 0:
						new_point[1] = len(grid[0]) - 1
					}
					direction_s := grid[new_point[0]][new_point[1]]
					if direction_s == 'R' {
						switch d {
						case 0:
							d = 3
						case 1:
							d = 2
						case 2:
							d = 0
						case 3:
							d = 1
						}
					} else if direction_s == 'L' {
						switch d {
						case 0:
							d = 2
						case 2:
							d = 1
						case 1:
							d = 3
						case 3:
							d = 0
						}
					}
				}
				if cycle_length > 0 {
					answer = append(answer, cycle_length)
				}
			}
		}
	}
	sort.Sort(sort.IntSlice(answer))
	return
}

테스트 1 〉	통과 (0.25ms, 3.71MB)
테스트 2 〉	통과 (0.49ms, 4.21MB)
테스트 3 〉	통과 (0.52ms, 3.53MB)
테스트 4 〉	통과 (26.08ms, 7.5MB)
테스트 5 〉	통과 (54.69ms, 10.9MB)
테스트 6 〉	통과 (68.05ms, 12MB)
테스트 7 〉	통과 (967.70ms, 117MB)
테스트 8 〉	통과 (737.75ms, 82.9MB)
테스트 9 〉	통과 (762.55ms, 92MB)
테스트 10 〉	통과 (1011.53ms, 136MB)
테스트 11 〉	통과 (1146.17ms, 145MB)

ABOUT ME

ComDoc ComDoc

티스토리툴바

ABOUT ME

관련글 관련글 더보기

티스토리툴바