1061. Lexicographically Smallest ~

LeetCode 갤러리
마이너

자동 짤방 이미지

이미지가 없습니다.

자동 짤방으로 사용할 이미지를 등록해 주세요.

Eat, Sleep, LeetCode, Repeat

매니저

부재중입니다.(ddakgun)

부매니저

흑화뉴비(coderhs)

개설일

2022-12-26

개발뉴비

2023.01.15 01:14:12

조회 39 추천 0 댓글 0

class Solution:

    def find(self, parent, x):
        if parent[x] != x:
            return self.find(parent, parent[x])
        return parent[x]
    
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        eq = [i for i in range(26)]
        ans = ''
        for p, q in zip(s1, s2):
            p = ord(p) - ord('a')
            q = ord(q) - ord('a')
            x = self.find(eq, p)
            y = self.find(eq, q)
            if x < y:
                eq[y] = x
            elif x > y:
                eq[x] = y
        for i, z in enumerate(eq):
            eq[i] = self.find(eq, i)
        for r in baseStr:
            r = ord(r) - ord('a')
            ans += chr(ord('a')+eq[r])

return ans

어제는 술 약속 있어서 + 문제가 어려워서 탈주함

equivalence relation은 집합의 포함관계가 가장 중요한 예시고 여기엔 유니언 파인드지!

이번에 유니언 파인드를 파이썬으로 처음 구현해봤는데

C++에서는 find 값 리턴하면서 바로 배열에 반영이 가능했는데

파이썬은 그게 안 되니까 이렇게 추가로 find로 넣어줘야하네.. 귀찮다.

고정닉 0

전체 댓글 0개

등록순 최신순 답글순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	2025년 가장 기억에 남는 인터넷 이슈는?	운영자	25/12/22	-	-
86	909. Snakes and Ladders [1]	개발뉴비	23.01.24	53	0
85	909. Snakes and Ladders	이벤트ㅇㅅㅇ(219.251)	23.01.24	47	0
83	997. Find the Town Judge	이벤트ㅇㅅㅇ(219.251)	23.01.23	44	0
82	997. Find the Town Judge [1]	개발뉴비	23.01.23	74	0
81	백준 9996번	키비	23.01.23	55	0
78	마갤 입문함 [2]	키비	23.01.22	58	0
77	131. Palindrome Partitioning [1]	개발뉴비	23.01.22	56	0
75	93. Restore IP Addresses [1]	개발뉴비	23.01.21	71	0
74	Longest Palindromic Substring 5번	o오어o(14.37)	23.01.21	30	0
73	Restore IP Addresses 93번	o오어o(14.37)	23.01.21	38	0
72	안녕하세요 오늘부터 릿코 달리게씁니당 [2]	조르디(112.170)	23.01.21	52	0
71	491. Non-decreasing Subsequences [1]	개발뉴비	23.01.21	56	0
70	974. Subarray Sums Divisible by K [1]	개발뉴비	23.01.19	42	0
69	926. Flip String to Monotone Increasing [1]	개발뉴비	23.01.17	39	0
68	57. Insert Interval [1]	개발뉴비	23.01.17	36	0
66	트리 문제 두 개 개빡치네;	개발뉴비	23.01.15	47	0
	1061. Lexicographically Smallest ~	개발뉴비	23.01.15	39	0
64	여기 갤럼들은 전부 해외취업 준비중? [2]	EvenAsura	23.01.14	104	0
63	1519. Number of Nodes in the Sub-Tree~	개발뉴비	23.01.12	28	0
62	1443. Minimum Time to Collect All Apples	개발뉴비	23.01.11	40	0
59	230111 데일리	꽃지	23.01.11	67	0
58	100. Same Tree	개발뉴비	23.01.10	33	0
56	220110 데일리	꽃지	23.01.10	40	0
53	144. Binary Tree Preorder Traversal	개발뉴비	23.01.09	40	0
52	230109 데일리	꽃지	23.01.09	30	0
51	리트코드 4번 [4]	o오어o(222.121)	23.01.09	64	0
50	리트코드 3번	o오어o(222.121)	23.01.09	25	0
49	220108 데일리	꽃지	23.01.08	53	0
48	68. Text Justification	ㅇㅇ(12.50)	23.01.08	34	0
47	3번문제 코드 딱 한줄만 알려준다	ㅇㅇ(218.234)	23.01.08	36	0
46	코딩 테스트 tdd로 하시는 분 [1]	TS(119.64)	23.01.07	60	0
45	가스스테이션(데일리)	o오어o(222.121)	23.01.07	50	0
44	230107 데일리 [1]	꽃지	23.01.07	55	0
43	134. Gas Station	개발뉴비	23.01.07	47	0
42	1833. Maximum Ice Cream Bars	개발뉴비	23.01.06	56	0
41	230106 데일리	꽃지	23.01.06	50	0
38	오늘의 릿코드 Minimum Number of Arrows~	개발뉴비	23.01.05	40	0
36	230105 데일리 [3]	꽃지	23.01.05	63	0
35	2244. Minimum Rounds 이거 푸는데	TS(119.64)	23.01.05	36	0
34	데일리 문제 어떻게 알아봄...? [1]	TS(119.64)	23.01.05	39	0
33	230104 데일리 [2]	꽃지	23.01.04	86	0
31	Minimum Rounds to Complete All Task [1]	개발뉴비	23.01.04	101	0
30	944. Delete Columns to Make Sorted in TS	ㅇㅇ(119.64)	23.01.04	42	0
29	백준 17726 Inheritance	꽃지	23.01.04	57	0
28	백준 14503번 로봇 청소기	개발뉴비	23.01.04	93	0
23	오늘의 릿코드 Delete Columns to Make Sorted [2]	개발뉴비	23.01.03	78	0
22	오늘의 데일리 [3]	꽃지	23.01.03	82	0
19	리트코드 해보면서 느낀 점	ㅇㅇ(119.64)	23.01.03	90	0
18	어쨌든 TS로 대문자 판별하기 문제 풀었는데	ㅇㅇ(119.64)	23.01.03	46	0
17	저는 js로 할게요 [5]	ㅇㅇ(119.64)	23.01.03	79	0